Guaranteeing fair service to persistent dependent tasks

Amotz Bar-Noy, Alain Mayer, Baruch Schieber, Madhu Sudan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)0898713498
StatePublished - Jan 22 1995
Externally publishedYes
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: Jan 22 1995Jan 24 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Guaranteeing fair service to persistent dependent tasks'. Together they form a unique fingerprint.

Cite this