Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / atomic broadcast, byzantine agreement

Publication Info: An shorter version of this paper appears in the proceedings of OPODIS 2005.

Date: received 1 Mar 2006

Contact author: cca at zurich ibm com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060301:093222 (All versions of this report)

Short URL: ia.cr/2006/082

Discussion forum: Show discussion | Start new discussion