Return to search

Simple Bivalency Proofs of the Lower Bounds in Synchronous Consensus Problems

A fundamental problem of fault-tolerant distributed computing is for the reliable processes to reach a consensus. For a synchronous distributed system of n processes with up to t crash failures and f failures actually occur, we prove using a straightforward bivalency argument that the lower bound for reaching uniform consensus is (f + 2)-rounds in the case of 0 < f ≤ t −2, and a new lower bound for early-stopping consensus is min (t + 1, f + 2)-rounds where 0 ≤ f ≤ t. Both proofs are simpler and more intuitive than the traditional methods such as backward induction. Our main contribution is that we solve the open problem of proving that bivalency can be applied to show the (f + 2)-rounds lower bound for synchronous uniform consensus. / Singapore-MIT Alliance (SMA)

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/3873
Date01 1900
CreatorsWang, Xianbing, Teo, Yong Meng, Cao, Jiannong
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
TypeArticle
Format158064 bytes, application/pdf
RelationComputer Science (CS);

Page generated in 0.0023 seconds