You are looking at a specific version 20060301:093222 of this paper. See the latest version.

Paper 2006/082

Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast

HariGovind V. Ramasamy and Christian Cachin

Abstract

Atomic broadcast is a communication primitive that allows a group of n parties to deliver a common sequence of payload messages despite the failure of some parties. We address the problem of asynchronous atomic broadcast when up to t < n/3 parties may exhibit Byzantine behavior. We provide the first protocol with an amortized expected message complexity of O(n) per delivered payload. The most efficient previous solutions are the BFT protocol by Castro and Liskov and the KS protocol by Kursawe and Shoup, both of which have message complexity O(n^2). Like the BFT and KS protocols, our protocol is optimistic and uses inexpensive mechanisms during periods when no faults occur; when network instability or faults are detected, it switches to a more expensive recovery mode. The key idea of our solution is to replace reliable broadcast in the KS protocol by consistent broadcast, which reduces the message complexity from O(n^2) to O(n) in the optimistic mode. But since consistent broadcast provides weaker guarantees than reliable broadcast, our recovery mode incorporates novel techniques to ensure that safety and liveness are always satisfied.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. An shorter version of this paper appears in the proceedings of OPODIS 2005.
Keywords
atomic broadcastbyzantine agreement
Contact author(s)
cca @ zurich ibm com
History
2006-03-01: received
Short URL
https://ia.cr/2006/082
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.