Name
Abstract | ||
|---|---|---|
We give a linear time algorithm to elect a leader. This problem originated in networking and distributed computing research. Given a graph, its vertices represent processors (here finite state machines), and its edges communication lines (here synchronous). The leader election problem consists in finding a protocol for a family of graphs which, upon iteration, distinguishes a vertex, edge or cycle by a special state called leader. Here, the graphs are only required to be connected, and without holes. We describe the algorithm on a special class of planar graphs, prove its correctness and show how it extends to other classes. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.tcs.2004.02.009 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Graph automata,Leader election,Euclidean cellular automata,Hyperbolic cellular automata,Distributed algorithms | Journal | 319 |
Issue | ISSN | Citations |
1-3 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Codrin Nichitiu | 1 | 49 | 5.73 |
| Christophe Papazian | 2 | 14 | 2.70 |
| Eric Rémila | 3 | 329 | 45.22 |