Timing Analysis of Leader-based and Decentralized Byzantine Consensus Algorithms

We compare in an analytical way two leader-based and decentralized algorithms (that is, algorithms that do not use a leader) for Byzantine consensus with strong validity. We show that for the algorithms we analyzed, in most cases, the decentralized variant of the algorithm shows a better worst-case execution time. Moreover, for the practically relevant case t <= 2 (t is the maximum number of Byzantine processes), this worst-case execution time is even at least as good as the execution time of the leader-based algorithms in fault-free runs.


Year:
2010
Publisher:
EPFL
Keywords:
Laboratories:




 Record created 2010-07-30, last modified 2018-09-13

n/a:
Download fulltext
PDF

Rate this document:

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