International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast

HariGovind V. Ramasamy
Christian Cachin
Search ePrint
Search Google
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.
  title={Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / atomic broadcast, byzantine agreement},
  note={An shorter version of this paper appears in the proceedings of OPODIS 2005. 13208 received 1 Mar 2006},
  author={HariGovind V. Ramasamy and Christian Cachin},