Loading...
Please wait, while we are loading the content...
Similar Documents
Best-case complexity of asynchronous Byzantine consensus (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Vukolić, Marko Guerraoui, Rachid Dutta, Partha |
| Abstract | Abstract. This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods of asynchrony as in the Internet. The measure expresses the ability of processes to reach a consensus decision in a minimal number of rounds of information exchange, as a function of (a) the ability to use authentication and (b) the number of actual process failures, in those rounds, as well as of (c) the total number of failures tolerated and (d) the system configuration. The measure holds for a framework where the different roles of processes are distinguished such that we can directly derive a meaningful bound on the time complexity of implementing robust general services in practical distributed systems. To prove our theorem, we establish certain lower bounds and we give algorithms that match these bounds. The algorithms are all variants of the same generic asynchronous Byzantine consensus algorithm, which is interesting in its own right. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Round Complexity System Configuration Actual Process Failure Minimal Number Asynchronous Byzantine Consensus Meaningful Bound Robust General Service Arbitrary Long Period Exact Measure Time Complexity Best-case Complexity Consensus Algorithm Information Exchange Consensus Decision Generic Asynchronous Byzantine Consensus Algorithm First Theorem Distributed Computing Different Role Practical Distributed System Byzantine Failure |
| Content Type | Text |
| Resource Type | Article |
