Welcome to the resource topic for 2006/082
Title:
Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast
Authors: HariGovind V. Ramasamy, 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.
ePrint: https://eprint.iacr.org/2006/082
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .