TERMINATING ALTERNATOR
Abstract
In this paper, we present an program that enables the transformation of a non-terminating alternator into a terminating alternator. Our solution is stabilization preserving and has the potential to preserve maximal concurrency (if available) provided by the non-terminating alternator. It can also be used to transform a program that is stabilizing in interleaving semantics into a program that is stabilizing in powerset semantics. We also discuss how the terminating alternator can be used to enable a process to gain an understanding of system stability.
This work was partially sponsored by NSF CAREER CCR-0092724, DARPA Grant OSURS01-C-1901, ONR Grant N00014-01-1-0744, NSF grant EIA-0130724, and a grant from Michigan State University.
References
G. Antonoiu and P. Srimani , Mutual exclusion between neighboring nodes in an arbitary system graph that stabilizes using read/write atomicity, EuroPar,Lecture Notes in Computer Science (1999) pp. 823–830. Google Scholar- IEEE Transactions on Computers 43(9), 1026 (1994), DOI: 10.1109/12.312126. Crossref, ISI, Google Scholar
- IEEE Transactions on Software Engineering 19(11), 1015 (1993), DOI: 10.1109/32.256850. Crossref, ISI, Google Scholar
-
J. Beauquier , Self-stabilizing local mutual exclusion and daemon refinement , Proceedings of the Thirteenth International Symposium on Distributed Computing ( 2000 ) . Google Scholar - Communications of the ACM 17(ll), 643 (1974), DOI: 10.1145/361179.361202. Crossref, ISI, Google Scholar
-
S. Dolev , Self-Stabilization ( The MIT Press , 2000 ) . Crossref, Google Scholar - Felix C. Gartner. A survey of self-stabilizing spanning tree construction algorithms. Technical Report IC/2003/38, Swiss Federal Institute of Technology (EPFL), 2003 . Google Scholar
-
M. G. Gouda and F. F. Haddix , The linear alternator , Workshop on Self-Stabilizing Systems ( 1997 ) . Google Scholar -
M. G. Gouda and F. F. Haddix , The alternator , Workshop on Self-Stabilizing Systems ( 1999 ) . Google Scholar - M. G. Gouda and F. F. Haddix. Three embedded alternators. Presentation at Seminar on Self-stablization, Lumini, Marseille, France, 2002 . Google Scholar
- T. Herman. Adaptivity Through Distributed Convergence. PhD thesis, University of Texas at Austin, 1991 . Google Scholar
- Lisa Higham and Colette Johnen. Self-stabilizing implementation of atomic register by regular register in network framework. Technical Report 1449, LRI, 2006 . Google Scholar
- Information Processing Letters (2005). Google Scholar
-
M. Mizuno and H. Kakagawa , A timestamp based transformation of self-stabilizing program for distributed computing environments , Workshop on Distributed Algorithms ( 1996 ) . Google Scholar - Information Processing Letters 66(6), 285 (1998), DOI: 10.1016/S0020-0190(98)00069-6. Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing (2002). Google Scholar


