DIMACS Discrete Math/Theory of Computing Seminar


Guaranteeing Fair Service to Persistent Dependent Tasks


Baruch Schieber
IBM T.J. Watson Research Center


DIMACS Center, CoRE Building, Seminar Room 431
Rutgers University


4:30 PM
Tuesday, December 10, 1996

We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control in high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled ``as often as possible''. There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. These conflicts are presented in the form of a conflict graph. We define parameters which quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters, and present fair and efficient scheduling algorithms for the case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.

Joint work with:

Amotz Bar-Noy (Tel Aviv Univ.)
Alain Mayer (Bell Labs.)
Madhu Sudan (IBM T.J. Watson Research Center)

Document last modified on December 9, 1996