Return to search

Lower Bounds for Achieving Synchronous Early Stopping Consensus with Orderly Crash Failures

In this paper, we discuss the consensus problem for synchronous distributed systems with orderly crash failures. For a synchronous distributed system of n processes with up to t crash failures and f failures actually occur, first, we present a bivalency argument proof to solve the open problem of proving the lower bound, min (t + 1, f + 2) rounds, for early-stopping synchronous consensus with orderly crash failures, where t < n - 1. Then, we extend the system model with orderly crash failures to a new model in which a process is allowed to send multiple messages to the same destination process in a round and the failing processes still respect the order specified by the protocol in sending messages. For this new model, we present a uniform consensus protocol, in which all non-faulty processes always decide and stop immediately by the end of f + 1 rounds. We prove that the lower bound of early stopping protocols for both consensus and uniform consensus are f + 1 rounds under the new model, and our proposed protocol is optimal. / Singapore-MIT Alliance (SMA)

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

Page generated in 0.002 seconds