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
Source: 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

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

5
checked on Dec 13, 2017

Page view(s)

78
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.