Quantitative Analysis of Consensus Algorithms

Consensus is one of the key problems in fault-tolerant distributed computing. Although the solvability of consensus is now a well-understood problem, comparing different algorithms in terms of efficiency is still an open problem. In this paper, we address this question for round-based consensus algorithm using communication predicates, on top of a partial synchronous system that alternates between good and bad periods (synchronous and non synchronous periods). Communication predicates together with the detailed timing information of the underlying partial-synchronous system provide a convenient and powerful framework for comparing different consensus algorithms and their implementations. This approach allows us to quantify the required length of a good period to solve a given number of consensus instances. With our results, we can observe several interesting issues, e.g., that the number of rounds of an algorithm is not necessarily a good metric for its performance.


Year:
2011
Publisher:
EPFL
Keywords:
Laboratories:




 Record created 2010-07-30, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)