A bivalency proof of the lower bound for uniform consensus

Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ipl.2005.08.002

Title:	A bivalency proof of the lower bound for uniform consensus
Authors:	Wang, X. Teo, Y.M. Cao, J.
Keywords:	Bivalency argument Distributed computing Synchronous distributed systems Uniform consensus
Issue Date:	2005
Citation:	Wang, X., Teo, Y.M., Cao, J. (2005). A bivalency proof of the lower bound for uniform consensus. Information Processing Letters 96 (5) : 167-174. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ipl.2005.08.002
Abstract:	Bivalency argument is a widely-used technique that employs forward induction to show impossibility results and lower bounds related to consensus. However, for a synchronous distributed system of n processes with up to t potential and f actual crash failures, applying bivalency argument to prove the lower bound for reaching uniform consensus is still an open problem. In this paper, we address this problem by presenting a bivalency proof that the lower bound for reaching uniform consensus is (f+2)-rounds where 0≤f≤t-2. © 2005 Elsevier B.V. All rights reserved.
Source Title:	Information Processing Letters
URI:	http://scholarbank.nus.edu.sg/handle/10635/39571
ISSN:	00200190
DOI:	10.1016/j.ipl.2005.08.002
Appears in Collections:	Staff Publications

There are no files associated with this item.

Check