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 -