Abstract | ||
---|---|---|
Consensus is one of the key problems in fault-tolerant distributed computing. Although the solvability of consensus is now a well-understood problem, comparing different algorithms in terms of efficiency is still an open problem. In this paper, we address this question for round-based consensus algorithms using communication predicates, on top of a partial synchronous system that alternates between good and bad periods (synchronous and nonsynchronous periods). Communication predicates together with the detailed timing information of the underlying partially synchronous system provide a convenient and powerful framework for comparing different consensus algorithms and their implementations. This approach allows us to quantify the required length of a good period to solve a given number of consensus instances. With our results, we can observe several interesting issues, such as the number of rounds of an algorithm is not necessarily a good metric for its performance. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/TDSC.2011.48 | IEEE Trans. Dependable Sec. Comput. |
Keywords | Field | DocType |
different algorithm,key problem,open problem,synchronous system,communication predicate,round-based consensus,consensus instance,partial synchronous system,good period,quantitative analysis,consensus algorithms,different consensus algorithm,consensus,real time systems,system modeling,distributed algorithm,distributed algorithms,algorithm design and analysis,synchronization,distributed processing,distributed systems,computer model,algorithm design,fault tolerant system,computational modeling,distributed system,fault tolerance,distributed computing | Synchronization,Open problem,Algorithm design,Computer science,Real-time computing,Implementation,Theoretical computer science,Distributed algorithm,Fault tolerance,Systems modeling,Uniform consensus,Distributed computing | Journal |
Volume | Issue | ISSN |
9 | 2 | 1545-5971 |
Citations | PageRank | References |
1 | 0.37 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fatemeh Borran | 1 | 10 | 2.23 |
Martin Hutle | 2 | 141 | 10.14 |
Nuno Santos | 3 | 189 | 24.08 |
André Schiper | 4 | 514 | 35.63 |