Home > Research > Publications & Outputs > On the latency efficiency of message-parsimonio...


Text available via DOI:

View graph of relations

On the latency efficiency of message-parsimonious asynchronous atomic broadcast

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review



We address the problem of message-parsimonious asynchronous atomic broadcast when a subset t out of n parties may exhibit Byzantine behavior. Message parsimony involves using only the optimal O(n) message exchanges per atomically delivered payload in the normal case. Message parsimony is desirable for Internet-like deployment environments in which message loss rates are non-negligible. Protocol PABC, the only previously-known message-parsimonious solution, suffered from two limitations vis-à-vis the solutions with O(n2) message complexity: more communication steps and the use of digital signatures. We present a protocol termed AMP that for the first time provides signature-free message parsimony while at the same time reducing the number of communication steps to the minimum necessary. In contrast to many previous atomic broadcast solutions, our protocol satisfies both safety and liveness in the asynchronous model. © 2007 IEEE.