“Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity in Normal Conditions”
From Navigators
(Difference between revisions)
(Created page with "{{Publication |type=inproceedings |document=Document for Publication-VavalaSRDS2012.pdf |title=Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity...") |
|||
| Line 3: | Line 3: | ||
|document=Document for Publication-VavalaSRDS2012.pdf | |document=Document for Publication-VavalaSRDS2012.pdf | ||
|title=Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity in Normal Conditions | |title=Robust and Speculative Byzantine Randomized Consensus with Constant Time Complexity in Normal Conditions | ||
| - | |author=Bruno Vavala, Nuno Neves, | + | |author=Bruno Vavala, Nuno Neves, |
| - | |Project=Project:MASSIF, | + | |Project=Project:MASSIF, |
|month=oct | |month=oct | ||
|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) | |journal=31st 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 | ||
}} | }} | ||
Revision as of 11:07, 5 September 2017
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
