Optimally simulating crash failures in a byzantine environment

Rida Bazzi, Gil Neiger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


The difficulty of designing of fault-tolerant distributed algorithms increases with the severity of failures that an algorithm must tolerate. Researchers have simplified this task by developing methods that automatically translate protocols tolerant of “benign” failures into ones tolerant of more “severe” failures. In addition to simplifying the design task, these translations can provide insight into the relative impact of different models of faulty behavior on the ability to provide fault-tolerant applications. Such insights can be gained by examining the properties of the translations. The roundcomplexity of a translation is such a property; it is the number of rounds of communication that the translation uses to simulate one round of the original algorithm. This paper considers synchronous systems and examines the problem of developing translations from simple stopping (crash) failures to completely arbitrary behavior with round-complexities 2, 3, and 4, respectively. In each case, we show a lower bound on the number of processors that must remain correct. We show matching upper bounds for all of these by developing three new translation techniques that are each optimal in the number of processors required. These results fully characterize the optimal translations between crash and arbitrary failures.

Original languageEnglish (US)
Title of host publicationDistributed Algorithms - 5th International Workshop, WDAG 1991, Proceedings
EditorsPaul G. Spirakis, Lefteris Kirousis, Sam Toueg
PublisherSpringer Verlag
Number of pages21
ISBN (Print)9783540552369
StatePublished - 1992
Externally publishedYes
Event5th International Workshop on Distributed Algorithms, WDAG 1991 - Delphi, Greece
Duration: Oct 7 1991Oct 9 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume579 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th International Workshop on Distributed Algorithms, WDAG 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Optimally simulating crash failures in a byzantine environment'. Together they form a unique fingerprint.

Cite this