TY - JOUR
T1 - A self-stabilizing ring orientation algorithm with a smaller number of processor states
AU - Umemoto, Narutoshi
AU - Kakugawa, Hirotsugu
AU - Yamashita, Masafumi
N1 - Funding Information:
The authors wish to thank the anonymous referees for their helpful comments on an earlier version of this paper. This work was supported in part by the Ministry of Education, Science and Culture under Grant 09780289, Research for the Future Program from the Japan Society for the Promotion of Science (JSPS): Software for Distributed and Parallel Super Computing (JSPS-RFTF 96P60505), and the Telecommunication Advancement Foundation. Earlier versions of results contained in this paper appear in “A Self-Stabilizing Ring Orientation Algorithm with Finite Number of States,” by N. Umemoto, H. Kakugawa, and M. Yamashita, RIMS Kokyuroku 906, pp. 257–263, Research Institute of Mathematical Science at Kyoto University, April 1995 (in Japanese).
PY - 1998
Y1 - 1998
N2 - A distributed system is said to be self-stabilizing if it will eventually reach a legitimate system state regardless of its initial state. Because of this property, a self-stabilizing system is extremely robust against failures; it tolerates any finite number of transient failures. The ring orientation problem for a ring is the problem of all the processors agreeing on a common ring direction. This paper focuses on the problem of designing a deterministic self-stabilizing ring orientation system with a small number of processor states under the distributed daemon. Because of the impossibility of symmetry breaking, under the distributed daemon, no such systems exist when the number n of processors is even. Provided that n is odd, the best known upper bound on the number of states is 256 in the link-register model, and eight in the state-reading model. We improve the bound down to 63 = 216 in the link-register model.
AB - A distributed system is said to be self-stabilizing if it will eventually reach a legitimate system state regardless of its initial state. Because of this property, a self-stabilizing system is extremely robust against failures; it tolerates any finite number of transient failures. The ring orientation problem for a ring is the problem of all the processors agreeing on a common ring direction. This paper focuses on the problem of designing a deterministic self-stabilizing ring orientation system with a small number of processor states under the distributed daemon. Because of the impossibility of symmetry breaking, under the distributed daemon, no such systems exist when the number n of processors is even. Provided that n is odd, the best known upper bound on the number of states is 256 in the link-register model, and eight in the state-reading model. We improve the bound down to 63 = 216 in the link-register model.
UR - http://www.scopus.com/inward/record.url?scp=0032098052&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032098052&partnerID=8YFLogxK
U2 - 10.1109/71.689445
DO - 10.1109/71.689445
M3 - Article
AN - SCOPUS:0032098052
SN - 1045-9219
VL - 9
SP - 579
EP - 584
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 6
ER -