Horst F. Wedde
A Graph-Theoretic Approach for Designing Fair Distributed Resource Scheduling Algorithms
Graph-theoretic Concepts in Computer Science, Hrsg.: Gottfried Tinhofer und Gunther Schmidt, Nr. 246, S. 204-226, Spr, Bernried, Germany, 1987
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).