Swift Algorithms for Repeated Consensus

We introduce the notion of a swift algorithm. Informally, an algorithm that solves the repeated consensus is swift if, in a partial synchronous run of this algorithm, eventually no timeout expires, i.e., the algorithm execution proceeds with the actual speed of the system. This definition differs from other efficiency criteria for partial synchronous systems. Furthermore, we show that the notion of swiftness explains the reason why failure detector based algorithms are typically more efficient than round-based algorithms, since the former are naturally swift while the later are naturally non-swift. We show that this is not an inherent difference between the models, and provide a round structure implementation that is swift, therefore performing similarly to failure detector algorithms while maintaining the advantages of the round model.

Published in:
Proceedings of the 29th IEEE International Symposium on Reliable Distributed Systems
Presented at:
29th IEEE International Symposium on Reliable Distributed Systems, New Delhi, India, October 31 – November 3
Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa

 Record created 2010-10-29, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)