Jump label

Service navigation

Main navigation

You are here:

Sub navigation

Main content


Horst F. Wedde
A Graph-Theoretic Model for Designing Fair Distributed Scheduling Algorithms
Graph-theoretic concepts in computer science - international workshop WG ’86, proceedings, Hrsg.: Gottfried Tinhofer und Gunther Schmidt, Nr. 246, S. 186-205, Springer-Verlag, Bernried, Federal Republic of Germany, 1987-06-17


Using the Theory of Interaction Systems a fair solution for a generalized mutual exclusion problem had been published. In this paper, its formal mechanism is analyzed in detail from an extended perspective. As a result, we derive the formal specification of a fair solution for the most general resource scheduling problem under completely distributed control. The particular point is that our formal approach allows for a stepwise construction procedure in which each step models a solution for a special case of the problem. The formal specification is then broken down into an algorithm in a procedural language. It is shown how each formal construction step is decomposable into a deadlock-free algorithm and an additional part which then guarantees fairness. Besides discussing the flexibility of our theoretical tools for approaching such general problems we also mention a practical application (resource management in the completely distributed operating system DRAGON SLAYER).