Name
Abstract | ||
|---|---|---|
The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the deterministic leader election problem with an asymptotically optimal round complexity. Using this result, we obtain an asymptotically optimal randomized leader election algorithm for anonymous networks, as well as improved algorithms for symmetry-breaking and communication primitives. The techniques that we introduce give a new insight as to how local constraints on the exchangeable messages can result in efficient algorithms, when dealing with the beeping model.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3212734.3212779 | PODC '18: ACM Symposium on Principles of Distributed Computing
Egham
United Kingdom
July, 2018 |
Keywords | Field | DocType |
distributed algorithms, leader election, beeping model, time complexity, deterministic algorithms | Leader election,Round complexity,Computer science,Theoretical computer science,Distributed algorithm,Time complexity,Asymptotically optimal algorithm,Broadcast communication network | Conference |
ISBN | Citations | PageRank |
978-1-4503-5795-1 | 0 | 0.34 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabien Dufoulon | 1 | 1 | 0.70 |
| Janna Burman | 2 | 123 | 13.55 |
| Joffroy Beauquier | 3 | 448 | 53.52 |