Generic construction of consensus algorithms for benign and Byzantine faults

The paper proposes a generic consensus algorithm that highlights the basic and common features of known consensus algorithms. The parameters of the generic algorithm encapsulate the core differences between various consensus algorithms, including leader-based and leader-free algorithms, addressing benign faults, authenticated Byzantine faults and Byzantine faults. This leads to the identification of three classes of consensus algorithms. With the proposed classification, Paxos and PBFT indeed belong to the same class, while FaB Paxos belongs to a different class. Interestingly, the classification allowed us to identify a new Byzantine consensus algorithm that requires n>4b, where b is the maximum number of Byzantine processes.


Presented at:
Proceedings of the 40th International Conference on Dependable Systems and Networks (DSN)
Year:
2010
ISSN:
0368-4466
Keywords:
Laboratories:




 Record created 2010-03-01, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

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