A general approach to real-time message scheduling over distributed broadcast channels
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 191-204
- https://doi.org/10.1109/etfa.1995.496774
Abstract
We introduce a class of real-time scheduling problems as they arise in distributed multiaccess broadcast communication channels. This class of problems is more general, hence more realistic, than the problems considered when assuming periodic or sporadic releases of messages. The authors examine the most popular algorithms and protocols, such as STDMA, polling and bus/ring token-passing. Contrary to widespread belief, the authors demonstrate that they cannot solve the class of real-time problems they are interested in. Adversary arguments are used for this purpose. The class of pure on-line distributed deadline-driven non-preemptive contention detection-and-resolution algorithms, referred to as D-NP-EDF/CDR, is shown to dominate any other class of algorithms for the problems considered. Consequently, optimal algorithms for the authors' problems can only belong to this class. The authors then show how to establish the desired timeliness properties as well as feasibility conditions for algorithms in the class D-NP-EDF/CDR.Keywords
This publication has 10 references indexed in Scilit:
- A theory of competitive analysis for distributed algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On non-preemptive scheduling of period and sporadic tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Hard real-time communication in multiple-access networksReal-Time Systems, 1995
- TTP-a protocol for fault-tolerant real-time systemsComputer, 1994
- A systematic approach to designing distributed real-time systemsComputer, 1993
- Virtual Time CSMA Protocols for Hard Real-Time CommunicationIEEE Transactions on Software Engineering, 1987
- Virtual Time CSMA: Why Two Clocks Are Better than OneIEEE Transactions on Communications, 1985
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Tree algorithms for packet broadcast channelsIEEE Transactions on Information Theory, 1979
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973