Centrality-Based Leader Election
Many distributed algorithms require a specific role to be played by a leader, a single node in the system. Leaders are often used to provide such varied services as time synchronization, message routing, etc. The choice of this node often has a direct impact on the performance. In particular, selecting a central node as the leader can significantly improve algorithm efficiency by reducing the network traffic or the time of convergence, especially in LMRs that form large-average-distance and large-diameter networks. In time-master-based synchronization protocols, placing the time-master at a central node leads to more synchronization precision in large-diameter networks as the precision of remote clock readings tends to decrease with the hop distance. In our work, we focus on the center and the centroid, i.e., the sets of nodes which respectively minimize the maximum and the average network distance to all the others. Classical distributed algorithms require global information about the connectivity network to elect a node that belongs to the exact center or centroid. Thus, they are not suitable for large-scale distributed embedded systems with scarce computation, memory and energy resources.
We proposed a two distributed algorithms to elect approximate-centroid and approximate-center nodes in asynchronous distributed systems. We introduced the ABC-Center algorithm and the Effective and Efficient Approximate-Centroid Election (E2ACE) algorithm . Our algorithms do not require any prior knowledge of the network, have a well-defined termination criterion, converge in a reasonable amount of time.
ABC-Center
ABC-Center extends the sequential Minimax [Handler, 1973] and 4-Sweep [Crescenzi et al., 2013] algorithms. ABC-Center identifies an extreme path and recursively isolates midpoints on it until electing a single node. The main idea of ABC-Center is that central nodes lie in the middle of a diameter path.
Videos
Effective and Efficient Approximate-Centroid Election algorithm
The Effective and Efficient Approximate-Centroid Election (E2ACE) algorithm is based on the Effective Closeness (ECL) input-graph analysis algorithm [Kang et al., 2011] which uses low-memory-footprint probabilistic counters (e.g., Flajolet-Martin [Flajolet et al., 1985]) to estimate node centrality measures. In E2ACE, an estimated centrality value is computed for all nodes. E2ACE tends to be approximately equivalent to running a BFS from every node but at less expense in terms of memory, computations and communications.
Results
We evaluate the proposed algorithms on the Blinky Blocks modular robotic system, using both hardware prototypes and simulations. Results show that our algorithms scale well in terms of accuracy, execution time and number of messages. As a consequence, our algorithms are suitable for large-scale embedded distributed systems with scarce resources.
Publications
Naz, A. (2017). Distributed Algorithms for Large-scale Robotic Ensembles: Centrality, Synchronization and Self-Reconfiguration. FEMTO-ST Institute, Univ. Bourgogne Franche-Comté, CNRS.
Naz, A., Piranda, B., Goldstein, S. C., & Bourgeois, J. (2016, March). Approximate-centroid election in large-scale distributed embedded systems. In Advanced Information Networking and Applications (AINA), 2016 IEEE 30th International Conference on (pp. 548-556). IEEE.
Naz, A., Piranda, B., Goldstein, S. C., & Bourgeois, J. (2015, September). ABC-Center: Approximate-center election in modular robots. In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on (pp. 2951-2957). IEEE.