A unified proof of minimum time complexity for reaching consensus and uniform consensus - an oracle-based approach

Author

Xu, Jun

Author_Institution

Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA, USA

fYear

2002

fDate

2002

Firstpage

102

Lastpage

108

Abstract

In this paper, we offer new proofs to two lower bound results in distributed computing: a minimum of f+1 and f+2 rounds for reaching consensus and uniform consensus respectively when at most f fail-stop faults can happen. Here the computation model is synchronous message passing. Both proofs are based on a novel oracle argument. These two induction proofs are unified in the following sense: the induction steps are the same and only the initial step (f=0) needs to be proved separately. The techniques used in the proof offer new insights into the lower bound results in distributed computing.

Keywords

computational complexity; concurrency control; fault tolerant computing; message passing; consensus; distributed computing; fault tolerance; induction proofs; lower bounds; oracle argument; synchronous message passing; time complexity; uniform consensus; Algorithm design and analysis; Computational modeling; Computer crashes; Context; Delay systems; Distributed computing; Educational institutions; Fault tolerance; Message passing; Mobile computing;

fLanguage

English

Publisher

ieee

Conference_Titel

Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on

ISSN

1060-9857

Print_ISBN

0-7695-1659-9

Type

conf

DOI

10.1109/RELDIS.2002.1180178

Filename

1180178