Byzantine Fault-Tolerance with Commutative Commands
Pavel Raykov, Nicolas Schiper, and Fernando Pedone
State machine replication is a popular approach to increasing the availability of computer services. While it has been largely studied in the presence of crash-stop failures and malicious failures, all existing state machine replication protocols that provide byzantine fault-tolerance implement some variant of atomic broadcast. In this context, this paper makes two contributions. First, it presents the first byzantine fault-tolerant generic broadcast protocol. Generic broadcast is more general than atomic broadcast, in that it allows applications to deliver commutative commands out of order—delivering a command out of order can be done in fewer communication steps than delivering a command in the same order. Second, the paper presents an efficient SMR protocol that tolerates byzantine failures. Our protocol requires fewer message delays than the best existing solutions under similar conditions. Moreover, processing of commutative commands on replicas requires only two MAC operations. The protocol is speculative in that it may rollback non-commutative commands.
BibTeX Citation
@inproceedings{RaScPe11,
author = {Pavel Raykov and Nicolas Schiper and Fernando Pedone},
title = {Byzantine Fault-Tolerance with Commutative Commands},
editor = {Fernàndez Anta, Antonio and Lipari, Giuseppe and Roy, Matthieu},
booktitle = {Principles of Distributed Systems --- OPODIS 2011},
pages = 329--342,
series = {Lecture Notes in Computer Science},
volume = 7109,
year = 2011,
month = 12,
publisher = {Springer},
}