Name
Abstract | ||
|---|---|---|
We address the Leader Election (LE) problem in networks of anonymous sensors sharing no kind of common coordinate system. Leader Election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign value 1 (leader) to one of the entities and value 0 (non-leader) to all others. In this paper, assuming n > 1 disoriented anonymous sensors, we provide a complete charac- terization on the sensors positions to deterministically elect a leader, provided that all the sensors' positions are known by every sensor. More precisely, our contribution is twofold: First, assuming n anonymous sensors agreeing on a common handedness (chirality) of their own coordinate system, we provide a complete characterization on the sensors positions to deterministically elect a leader. Second, we also provide such a complete chararacterization for sensors devoided of a common handedness. Both characterizations rely on a particular object from combinatorics on words, namely the Lyndon Words. |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Leader election,Coordinate system,Symmetry breaking,Computer science,Theoretical computer science,Artificial intelligence,Lyndon words,Combinatorics on words,Distributed computing |
DocType | Volume | Citations |
Journal | abs/1202.4486 | 0 |
PageRank | References | Authors |
0.34 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoann Dieudonné | 1 | 221 | 19.88 |
| Florence Levé | 2 | 51 | 10.20 |
| Franck Petit | 3 | 736 | 60.02 |
| Vincent Villain | 4 | 544 | 45.77 |