“Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity in Normal Conditions”
From Navigators
in Missing booktitle, 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
Export citation
Project(s): Project:MASSIF
Missing ResearchLine
