Topology Aware Leader Election Algorithm for Dynamic Networks

Arnaud Favier (1) , Nicolas Guittonneau (1) , Luciana Arantes (1) , Anne Fladenmuller (2) , Jonathan Lejeune (1) , Pierre Sens (1)

1 DELYS - DistributEd aLgorithms and sYStems
2 NPA - Networks and Performance Analysis

This paper proposes an algorithm that eventually elects a leader for each connected component of a dynamic network where nodes can move or fail by crash. A node only communicates with nodes in its transmission range and locally keeps a global view, denoted topological knowledge, of the communication graph of the network and its dynamic evolution. Every change in the topology or in nodes membership is detected by one or more nodes and propagated over the network, updating thus the topological knowledge of the nodes. As the choice of the leader has an impact on the performance of applications that use an eventual leader election service, our algorithm, thanks to nodes topological knowledge, exploits the closeness centrality as the criterion for electing a leader. Experiments were conducted on top of PeerSim simulator, comparing our algorithm to a representative flooding algorithm. Performance results show that our algorithm outperforms the flooding one when considering leader choice stability, number of messages, and average distance to the leader.

Mots clés: Distributed systems; Dynamic networks; Connected graphs; Leader election; Topology; Centrality

Domaines: Informatique [cs]; Calcul parallèle, distribué et partagé [cs.DC]

Arnaud Favier, Nicolas Guittonneau, Luciana Arantes, Anne Fladenmuller, Jonathan Lejeune, et al.. Topology Aware Leader Election Algorithm for Dynamic Networks. PRDC 2020 - 25th IEEE Pacific Rim International Symposium on Dependable Computing, Dec 2020, Perth, Australia. pp.1-10, ⟨10.1109/PRDC50213.2020.00011⟩. ⟨hal-02954037⟩