Name
Abstract | ||
|---|---|---|
Consider a network made of n nodes scattered in the 2-dimensional space. Nodes are anonymous and disoriented devices being unable to communicate. Anonymous refers to systems made of a priori indistinguishable nodes. By disoriented, we mean that the nodes share no kind of coordinate system nor common sense of direction. Such systems are typically wireless sensor networks or swarms of robots endowed with localization capabilities, for instance visibility sensors or pattern formation maps. We address the Geoleader Election (GE) problem which is to ensure that, solely based on their positions, the nodes deterministically agree on the same position of a single node, called the leader. We provide a complete characterization on the node positions, both for systems with common handedness (chirality) and for systems devoid of a common handedness. The characterization is based on a particular object from combinatorics on words, namely the Lyndon words. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2013.07.033 | Theor. Comput. Sci. |
Keywords | Field | DocType |
n node,indistinguishable node,disoriented device,common handedness,single node,nodes share,node position,disoriented anonymous system,nodes deterministically,Deterministic geoleader election,complete characterization,common sense | Leader election,Discrete mathematics,Sense of direction,A priori and a posteriori,Theoretical computer science,Wireless sensor network,Lyndon words,Mathematics | Journal |
Volume | ISSN | Citations |
506, | 0304-3975 | 5 |
PageRank | References | Authors |
0.47 | 18 | 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 |