2008-12-06

Self-stabilizing protocol design

The number of processors and the sometimes noisy communication media in a distributed system impose the need for a fault tolerant design. One strong notion of fault tolerance is self-stabilization. Roughly speaking, a self-stabilizing protocol can cope with any kind of faults in the history. A distributed system is self-stabilizing if it can be started in any possible global state. Once started, the system runs for a while until it reaches a legitimate global state in which the system is consistent. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period between one recovery and the next faulty period is long enough, the system stabilizes.
(c) Shlomi Dolev, Amos Israeli, and Shlomo Moran; Uniform Dynamic Self-Stabilizing Leader Election

No comments: