Distributed consensus with general omission failures and timing uncertainty

Author

Bharali, Anupam A. ; Berman, Piotr

Author_Institution

Dept. of Comput. Sci., Pennsylvania State Univ., University Park, PA, USA

fYear

1993

fDate

23-26 Mar 1993

Firstpage

168

Lastpage

174

Abstract

In a distributed concensus protocol, a number of processors communicating by message passing start with some initial values. The protocol terminates with all nonfaulty processors agreeing on one of these values. The authors investigate the time needed to reach consensus in partially synchronous systems under various classes of processor failures. They provide the first asymptotically optimal distributed consensus protocol for semi-synchronous systems that tolerates general omission failures. When the failures occurring are restricted to omission and crash failures, the protocol terminates faster, matching the best known protocols for these failure classes

Keywords

distributed databases; fault tolerant computing; message passing; protocols; crash failures; distributed concensus protocol; general omission failures; message passing; nonfaulty processors; omission; partially synchronous systems; timing uncertainty; Clocks; Computer crashes; Computer science; Delay; Message passing; Protocols; Timing; Uncertainty;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers and Communications, 1993., Twelfth Annual International Phoenix Conference on

Conference_Location

Tempe, AZ

Print_ISBN

0-7803-0922-7

Type

conf

DOI

10.1109/PCCC.1993.344468

Filename

344468