TY - GEN

T1 - Guaranteeing fair service to persistent dependent tasks

AU - Bar-Noy, Amotz

AU - Mayer, Alain

AU - Schieber, Baruch

AU - Sudan, Madhu

N1 - Funding Information:
$Dept. of Computer Science, Columbia University, New York, NY 10027. Email: mayerQcs .columbia.edu. Part of this work was done while the author was at the IBM T. J. Watson Research Center. Partially supported by an IBM Graduate Fellowship, NSF grant CCR-93-16209, and CISE Institutional Infrastructure Grant CDA-90-24735
Funding Information:
Part of this work was done while the author was at the IBM T. J. Watson Research Center. Partially supported by an IBM Graduate Fellowship, NSF grant CCR-93-16209, and CISE Institutional Infrastructure Grant CDA-90-24735

PY - 1995/1/22

Y1 - 1995/1/22

N2 - We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control of 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 gets imposed implicitly by the fact that some tasks are in conflict and cannot be scheduled simultaneously. The conflicts are presented in the form of a conflict graph. We define parameters that 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 special 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.

AB - We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control of 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 gets imposed implicitly by the fact that some tasks are in conflict and cannot be scheduled simultaneously. The conflicts are presented in the form of a conflict graph. We define parameters that 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 special 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.

UR - http://www.scopus.com/inward/record.url?scp=85030060536&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030060536&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85030060536

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 243

EP - 252

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

Y2 - 22 January 1995 through 24 January 1995

ER -