AN ORDER DEGREE ALTERNATOR FOR ARBITRARY TOPOLOGIES
Abstract
An alternator is an arbitrary set of interacting processes that satisfies three conditions. First, if a process executes its critical section, then no neighbor of that process can execute its critical section at the same state. Second, along any infinite sequence of system states, each process will execute its critical section, an infinite number of times. Third, along any maximally concurrent computation, the alternator will stabilize to a sequence of states in which the processes will execute their critical sections in alternation. A principal reason for interest in alternators is their ability to transform systems correct under serial execution semantics to systems that are correct under concurrent execution semantics. An earlier alternator for arbitrary topology required 2q states where q is the dependency graph circumference and after stabilization would wait 2q steps between critical section executions. In a synchronous environment, this alternator requires only 2d+1 states where d is the degree of the graph of process dependencies for the system and after stabilization will require a wait of 2d+1 steps between critical section executions. In an asynchronous environment, the synchronization properties of this alternator must be supplemented with an asynchronous unison algorithm. The asynchronous unison algorithm requires expansion of the required number of states to dt, where t is the longest chordless cycle in the dependency graph; however, the required wait between critical section executions remains O(d).
References
Mohamed G. Gouda and Furman Haddix , The Linear Alternator, Proceedings of 2nd Workshop on Self-Stabilizing Systems (1997) pp. 31–47. Google ScholarMohamed G. Gouda and Furman Haddix , The Alternator, Proceedings of 3rd Workshop on Self-Stabilizing Systems (1999) pp. 48–53. Google ScholarTzong-Jye Liu and Chia-Lin Lee , 2-state alternator for uniform rings with arbitrary size, 19th International Conference on Advanced Information Networking and Applications1 (2005) pp. 847–852. Google ScholarColette Johnen , Self-Stabilizing Neighborhood Synchronizer in Tree Networks, International Conference on Distributed Computing Systems (1999) pp. 487–494. Google ScholarColette Johnen and Luc O. Alima , Parallel Processing Letters6 (2002) pp. 327–340. Google Scholar-
Mohamed G. Gouda and Furman Haddix , Tree-Embedded Alternators: Trees, Rings, Grids, and Hypercubes , International Seminar about Self-Stabilizing Systems ( Luminy , 2004 ) . Google Scholar - Journal of Parallel and Distributed Computing 52, 766 (2002). Google Scholar
- Information Processing Letters 93, 207 (2005), DOI: 10.1016/j.ipl.2004.11.009. Crossref, ISI, Google Scholar
C. Boulinier , F. Petit and V. Villain , When Graph Theory Helps Self-Stabilization, Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing (2004) pp. 150–159. Google Scholar- Furman Haddix, "Chapter 3. Tree and Grid Alternators", Alternating Parallelism and the Stabilization of Distributed Systems, Dissertation, Department of Computer Sciences, The University of Texas at Austin, (1999), pp. 27-50 . Google Scholar
Shlomi Dolev , Amos Israeli and Shlomo Moran , Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing (1990) pp. 103–117. Google Scholar- ACM Transactions on Programming Languages and Systems 20, 1171 (1998), DOI: 10.1145/295656.295659. Crossref, ISI, Google Scholar
J. Couvreur , N. Francez and M. Gouda , Asynchronous Unison, Proceedings of the 12th International Conference on Distributed Computing Systems (1992) pp. 486–493. Google Scholar


