“Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity in Normal Conditions”

From Navigators

(Difference between revisions)
Jump to: navigation, search
 
Line 8: Line 8:
|year=2012
|year=2012
|abstract=Randomized Byzantine Consensus can be an interesting building block in the implementation of asynchronous distributed systems. Despite its exponential worst-case complexity, which would make it less appealing in practice, a few experimental works have argued quite the opposite. To bridge the gap between theory and practice, we analyze a well-known state-of-the-art algorithm in normal system conditions, in which crash failures may occur but no malicious attacks, proving that it is fast on average. We then leverage our analysis to improve its best-case complexity from three to two phases, by reducing the communication operations through speculative executions. Our findings are confirmed through an experimental validation.
|abstract=Randomized Byzantine Consensus can be an interesting building block in the implementation of asynchronous distributed systems. Despite its exponential worst-case complexity, which would make it less appealing in practice, a few experimental works have argued quite the opposite. To bridge the gap between theory and practice, we analyze a well-known state-of-the-art algorithm in normal system conditions, in which crash failures may occur but no malicious attacks, proving that it is fast on average. We then leverage our analysis to improve its best-case complexity from three to two phases, by reducing the communication operations through speculative executions. Our findings are confirmed through an experimental validation.
-
|journal=31st Symposium on Reliable and Distributed Systems (SRDS)
+
|booktitle=Proceedings of the 31st IEEE Symposium on Reliable and Distributed Systems (SRDS)
|url=http://www.cs.cmu.edu/~bvavala/pub/srds2012.pdf
|url=http://www.cs.cmu.edu/~bvavala/pub/srds2012.pdf
}}
}}

Latest revision as of 11:08, 5 September 2017

Bruno Vavala, Nuno Neves

in Proceedings of the 31st IEEE Symposium on Reliable and Distributed Systems (SRDS), Oct. 2012.

Abstract: Randomized Byzantine Consensus can be an interesting building block in the implementation of asynchronous distributed systems. Despite its exponential worst-case complexity, which would make it less appealing in practice, a few experimental works have argued quite the opposite. To bridge the gap between theory and practice, we analyze a well-known state-of-the-art algorithm in normal system conditions, in which crash failures may occur but no malicious attacks, proving that it is fast on average. We then leverage our analysis to improve its best-case complexity from three to two phases, by reducing the communication operations through speculative executions. Our findings are confirmed through an experimental validation.

Download paper

Download Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity in Normal Conditions

Export citation

BibTeX

Project(s): Project:MASSIF

Missing ResearchLine

Personal tools
Navigators toolbox