Uniform self-stabilizing ring orientation

DOI10.1006/INCO.1993.1029MaRDI QIDQ2366560zbMATH OpenOpenAlexFDO

Authors Amos Israeli, Marc Jalfon

Publication date 30 August 1993

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1993.1029

zbMATH Keywords

distributed systemsrandomized protocolring orientationself-stabilization

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Formal languages and automata (68Q45) Distributed algorithms (68W15)

Review text

The paper deals with a class of uniform protocols that ensure the self- stabilization of ring type distributed systems. The self-stabilization means that a system with this property once started regains its consistency by itself, without any outside intervention. The authors discuss the problem of existence of uniform self-stabilizing protocols for ring orientation and show that the problem cannot be entirely solved by using deterministic protocols. In particular, they prove that there is not deterministic protocol for orienting rings of even size. Next, they present and prove the correctness of a randomized self-stabilizing protocol for ring orientation. The proposed protocol is composed of two levels, with a randomized lower level protocol. In the analysis it is assumed that all processors are randomized finite state machines that can communicate with their neighbours by using atomic registers. The authors find the expected stabilization time as well as the parallel complexity of the protocol, i.e., the maximal time over all possible initial configurations when every enables processor is activated.

Recommendations

• Self-stabilizing ring orientation using constant space
• scientific article; zbMATH DE number 1332660
• scientific article; zbMATH DE number 871956
• Probabilistic self-stabilization
• Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings

Cited in

(23)

• Self-stabilization: Randomness to reduce space
• Self-stabilizing ring orientation using constant space
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
• Self-stabilization with path algebra
• Labeled versus unlabeled distributed Cayley networks
• Randomized three-state alternator for uniform rings
• Minimal sense of direction in regular networks
• Randomized uniform self-stabilizing mutual exclusion
• OPTIMAL CONSTRUCTION OF SENSE OF DIRECTION IN A TORUS BY A MOBILE AGENT
• scientific article; zbMATH DE number 1332660 (Why is no real title available?)
• scientific article; zbMATH DE number 871956 (Why is no real title available?)
• scientific article; zbMATH DE number 7249603 (Why is no real title available?)
• Self-stabilizing \(2^m\)-clock for unidirectional rings of odd size
• Torus orientation
• Universal dynamic synchronous self-stabilization
• TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION
• Distributed Computing
• Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings
• Self-stabilization of wait-free shared memory objects
• Message terminating algorithms for anonymous rings of unknown size
• Analysis of toggle protocols
• Probabilistic self-stabilization

This page was built for publication: Uniform self-stabilizing ring orientation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366560)