On the Message Complexity of Indulgent Consensus

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.

Published in:
Proceedings of the 21st International Symposium on Distributed Computing (DISC'07), 283-297
Presented at:
Symposium on Distributed Computing (DISC'07), Lemesos, Cyprus, September 24-26

 Record created 2007-07-24, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)