Conference paper
A continuum of failure models for distributed computing
Distributed Algorithms, pp.153-165
International Symposium on Distributed Computing (Israel, Haifa, 02/Nov/1992 - 04/Nov/1992)
1992
Abstract
A range of models of distributed computing is presented in which processors may fail either by crashing or by exhibiting arbitrary (Byzantine) behavior. In these models, the total number of faulty processors is bounded from above by a constant t subject to the proviso that no more than b less-than-or-equal-to t of these processors are Byzantine. At the two extremes of the range (i.e., b = 0 or b = t) we get models that are equivalent to the traditional models of either pure crash failures or pure Byzantine failures. For 0 <b <t, the models that we introduce accommodate ''real-world'' experience that shows that the overwhelming majority of failures are crashes but occasionally some number of less-restrictive failures occur. We examine the Reliable Broadcast and Consensus problems within this new family of models and prove lower bounds on the relationship required between the number of processors, t, and b. We also present protocols to solve these problems, which match the lower bounds. In presenting the protocols, we emphasize new algorithmic techniques that are fruitful to use in the new models but which have limited value in either of the pure models.
Details
- Title
- A continuum of failure models for distributed computing
- Creators
- Juan A. Garay (null) - The Weizmann Institute of ScienceKenneth J. Perry (null) - 41___IBM_RESEARCH_-_THOMAS_J._WATSON_RESEARCH_CENTER_(YORKTOWN_HEIGHTS)
- Resource Type
- Conference paper
- Publication Details
- Distributed Algorithms, pp.153-165; 1992
- Number of pages
- 13
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Verlag
- Language
- English
- DOI
- https://doi.org/10.1007/3-540-56188-9_11
- Conference
- International Symposium on Distributed Computing (Israel, Haifa, 02/Nov/1992 - 04/Nov/1992)
- Grant note
- NA
- ISBN
- 978-3-540-56188-0
- Record Identifier
- 993265330803596
Metrics
15 Record Views