2012/02/20 by Yoann dieudonné, Yoann Dieudonné, Florence Levé +6
Computer Science · Engineering · #Distributed systems and fault tolerance #Modular Robots and Swarm Intelligence #Optimization and Search Problems #cs.DC #cs.MA
paper · pdf · doi:10.48550/arxiv.1202.4486
arxiv created 2012/02/20 · arxiv updated 2012/02/22
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.