We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Fault-containing self-stabilizing distributed protocols.
- Authors
Ghosh, Sukumar; Gupta, Arobinda; Herman, Ted; Pemmaraju, Sriram
- Abstract
Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol, in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly simplifies the task of fault-containment.
- Subjects
SELF-stabilization (Computer science); COMPUTER network protocols; FAULT-tolerant computing; ELECTRIC transformers; ELECTRONIC data processing; COMPUTER algorithms
- Publication
Distributed Computing, 2007, Vol 20, Issue 1, p53
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-007-0032-2