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)
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/7425 |
| Date | 01 1900 |
| Creators | Wang, Xianbing, Teo, Yong Meng, Cao, Jiannong |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Article |
| Format | 434519 bytes, application/pdf |
| Relation | Computer Science (CS); |
Page generated in 0.0022 seconds