Name
Abstract | ||
|---|---|---|
We resolve two long-standing open problems in dis- tributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a non- adaptive malicious adversary. All past protocols for asynchronous Byzantine Agreement had been exponen- tial, and no protocol for asynchronous leader election had been known. Our protocols tolerate up to n 6+ǫ faulty processors, for any positive constant ǫ. They are Monte Carlo, succeeding with probability 1 − o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our paper is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1824777.1824788 | ACM Transactions on Algorithms (TALG) |
Keywords | DocType | Volume |
monte carlo,information model,distributed algorithms,asynchronous communication,leader election,probabilistic method,monte carlo algorithm,distributed algorithm,distributed computing | Journal | 6 |
Issue | ISSN | Citations |
4 | 1549-6325 | 29 |
PageRank | References | Authors |
0.96 | 26 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruce M. Kapron | 1 | 308 | 26.02 |
| David Kempe | 2 | 5891 | 403.41 |
| Valerie King | 3 | 1276 | 99.39 |
| Jared Saia | 4 | 1019 | 96.95 |
| Vishal Sanwalani | 5 | 140 | 6.70 |