Two-state self-stabilizing algorithms
M Flatebo, AK Datta - Proceedings Sixth International Parallel …, 1992 - ieeexplore.ieee.org
M Flatebo, AK Datta
Proceedings Sixth International Parallel Processing Symposium, 1992•ieeexplore.ieee.orgA distributed system consists of a set of loosely connected state machines which do not
share a global memory. All the possible global states of the system can be split up into legal
and illegal states. A self-stabilizing system is a network of processors, which, when started
from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite
number of steps. One issue in designing self-stabilizing algorithms is the number of state
required by each machine. The paper presents algorithms which will be self-stabilizing while …
share a global memory. All the possible global states of the system can be split up into legal
and illegal states. A self-stabilizing system is a network of processors, which, when started
from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite
number of steps. One issue in designing self-stabilizing algorithms is the number of state
required by each machine. The paper presents algorithms which will be self-stabilizing while …
A distributed system consists of a set of loosely connected state machines which do not share a global memory. All the possible global states of the system can be split up into legal and illegal states. A self-stabilizing system is a network of processors, which, when started from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite number of steps. One issue in designing self-stabilizing algorithms is the number of state required by each machine. The paper presents algorithms which will be self-stabilizing while only requiring each machine in the network to have two states. Probability is used in some of the algorithms in order to make this possible. The algorithms are given along with correctness proofs.< >
ieeexplore.ieee.org