TY - GEN
T1 - On the message complexity of indulgent consensus
AU - Gilbert, Seth
AU - Guerraoui, Rachid
AU - Kowalski, Dariusz R.
PY - 2007
Y1 - 2007
N2 - Many recommend planning for the worst and hoping for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well-behaved, synchronous executions with few failures. We present two such algorithms: In synchronous executions, the first has optimal message complexity, using only O(n) messages, but runs in superlinear time of O(n1+ε). The second has a message complexity of O(n polylog(n)), but has an optimal running time, completing in O(f) rounds in synchronous executions with at most f failures. Both of these results improve significantly over the most message-efficient of previous indulgent consensus algorithms which have a message complexity of at least Ω(n2) in well-behaved executions.
AB - Many recommend planning for the worst and hoping for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well-behaved, synchronous executions with few failures. We present two such algorithms: In synchronous executions, the first has optimal message complexity, using only O(n) messages, but runs in superlinear time of O(n1+ε). The second has a message complexity of O(n polylog(n)), but has an optimal running time, completing in O(f) rounds in synchronous executions with at most f failures. Both of these results improve significantly over the most message-efficient of previous indulgent consensus algorithms which have a message complexity of at least Ω(n2) in well-behaved executions.
UR - http://www.scopus.com/inward/record.url?scp=38049011966&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38049011966&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-75142-7_23
DO - 10.1007/978-3-540-75142-7_23
M3 - Conference contribution
AN - SCOPUS:38049011966
SN - 9783540751410
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 283
EP - 297
BT - Distributed Computing - 21st International Symposium, DISC 2007, Proceedings
PB - Springer Verlag
T2 - 21st International Symposium on Distributed Computing, DISC 2007
Y2 - 24 September 2007 through 26 September 2007
ER -