loading...
A Unified Proof of Minimum Time Complexity for Reaching Consensus and Uniform Consensus — An Oracle-Based Approach
Osaka University, Suita, Japan October 13-October 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/RELDIS.2002.118017821st IEEE Symposium on Reliable Distr ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Jun Xu, "A Unified Proof of Minimum Time Complexity for Reaching Consensus and Uniform Consensus — An Oracle-Based Approach," Reliable Distributed Systems, IEEE Symposium on, pp. 102, 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/RELDIS.2002.1180178,
author = {Jun Xu},
title = {A Unified Proof of Minimum Time Complexity for Reaching Consensus and Uniform Consensus — An Oracle-Based Approach},
journal ={Reliable Distributed Systems, IEEE Symposium on},
volume = {0},
year = {2002},
issn = {1060-9857},
pages = {102},
doi = {http://doi.ieeecomputersociety.org/10.1109/RELDIS.2002.1180178},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Reliable Distributed Systems, IEEE Symposium on
TI - A Unified Proof of Minimum Time Complexity for Reaching Consensus and Uniform Consensus — An Oracle-Based Approach
SN - 1060-9857
SP
EP
A1 - Jun Xu,
PY - 2002
KW - Consensus
KW - uniform consensus
KW - lower bounds
KW - fault tolerance
VL - 0
JA - Reliable Distributed Systems, IEEE Symposium on
ER -
 
Jun Xu, Georgia Institute of Technology
In this paper, we offer new proofs to two lower bound results in distributed computing: a minimum of f +1 and f +2 rounds for reaching consensus and uniform consensus respectively when at most f fail-stop faults can happen. Here the computation model is synchronous message passing. Both proofs are based on a novel oracle argument. These two induction proofs are unified in the following sense: the induction steps are the same and only the initial step (f=0) needs to be proved separately. The techniques used in the proof offer new insights into the lower bound results in distributed computing.
Index Terms:
Consensus, uniform consensus, lower bounds, fault tolerance
Citation:
Jun Xu, "A Unified Proof of Minimum Time Complexity for Reaching Consensus and Uniform Consensus — An Oracle-Based Approach," srds, pp.102, 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.