Paper 2006/082

Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast

HariGovind V. Ramasamy and Christian Cachin


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. An shorter version of this paper appears in the proceedings of OPODIS 2005.
atomic broadcastbyzantine agreement
Contact author(s)
cca @ zurich ibm com
2006-03-01: received
Short URL
Creative Commons Attribution


      author = {HariGovind V.  Ramasamy and Christian Cachin},
      title = {Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2006/082},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.