Abstract
|
Byzantine consensus in asynchronous messag … Byzantine consensus in asynchronous message-passing systems has been shown to require at least 3f + 1 processes to be solvable in several system models (e.g., with failure detectors, partial synchrony or randomization). Recently a couple of solutions to implement Byzantine fault-tolerant state-machine replication using only 2f + 1 replicas have appeared. This reduction from 3f + 1 to 2f + 1 is possible
with a hybrid system model, i.e., by extending the system model with trusted/trustworthy components that constrain the power of faulty processes to have certain behaviors. Despite these important results, the problem of solving Byzantine consensus with only 2f + 1 processes is still far from being well understood. In this paper we present a methodology to transform crash consensus algorithms into Byzantine consensus algorithms with different characteristics, with the assistance of a reliable broadcast primitive that requires trusted/trustworthy components to be implemented. We exemplify
the methodology with two algorithms, one that uses failure detectors and one that is randomized. We also define a new flavor of consensus and use it to solve atomic broadcast, showing the practical interest of the transformations. practical interest of the transformations.
|
Author
|
Miguel Correia +
, Giuliana Santos Veronese +
, Lau Cheuk Lung +
|
Booktitle
|
Proceedings of the 25th Annual ACM Symposium on Applied Computing, March 2010. +
|
Key
|
Correia10a +
|
Month
|
mar +
|
NumPubDate
|
2,010.03 +
|
Project
|
Project:REGENESYS +
, Project:DIVERSE +
|
ResearchLine
|
Fault And Intrusion Tolerance in Open Distributed Systems (FIT) +
|
Title
|
Asynchronous Byzantine Consensus with 2f+1 Processes +
|
Type
|
inproceedings +
|
Url
|
http://www.navigators.di.fc.ul.pt/archive/papers/consensus2f11.pdf +
|
Year
|
2010 +
|
Categories |
Publication +
|
Modification dateThis property is a special property in this wiki.
|
14 January 2013 14:40:59 +
|