An optimal self-stabilizing strarvation-free alternator

摘要

System refinements from a strong to a weaker model are highly desirable because they allow designers to reason effectively in the strong model. Semantics and fairness refinements are often implemented by alternators preserving the property of stabilization. The existing alternators [Gouda and Haddix, Proceedings of the Third Workshop on Self-Stabilizing Systems (published in association with ICDCS99) The 19th IEEE International conference on Distributed Computing System), IEEE Computer Society Silver Spring, MD, 1999, pp. 48–53; Nesterenko and Arora, Disc99 Distributed Computing 13th International symposium springer, Berlin, 1999, pp. 254–268] provide semantics refinement but fail to implement starvation-freedom. Starvation-freedom requires that no two neighboring processes are scheduled simultaneously; along any interleaved execution, each action is executed infinitely often; no action is infinitely often enabled but never executed; and the number of enabled actions scheduled by the alternator is maximal. In this paper, we first establish the relationships between various mutual exclusion assumptions and the starvation-free alternators (SFAs) under various execution models.Then, as a remedy for the deficiencies of the existing alternators, we propose a fairness refinement for self-stabilizing distributed systems based on a state–space optimal self-stabilizing a (SFA) for arbitrary topologies and verify its correctness.