Journal article
Fault-containing self-stabilizing distributed protocols
Distributed computing, Vol.20(1), pp.53-73
07/01/2007
DOI: 10.1007/s00446-007-0032-2
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.
Details
- Title: Subtitle
- Fault-containing self-stabilizing distributed protocols
- Creators
- Sukumar Ghosh - University of IowaArobinda Gupta - Indian Institute of Technology IndoreTed Herman - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Distributed computing, Vol.20(1), pp.53-73
- Publisher
- Springer Nature
- DOI
- 10.1007/s00446-007-0032-2
- ISSN
- 0178-2770
- eISSN
- 1432-0452
- Number of pages
- 21
- Language
- English
- Date published
- 07/01/2007
- Academic Unit
- Computer Science; Internal Medicine
- Record Identifier
- 9984259489302771
Metrics
7 Record Views