Topology Aware Leader Election Algorithm for Dynamic Networks

During my PhD in Computer Sciences at Sorbonne University in Paris, I worked on a new algorithm to elect a leader based on the topology of a dynamic network. The research article was accepted at the 25th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2020) in September 2020, and will be presented in Perth, Australia in December 2021 (postponed due to Covid-19).

Abstract

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.

Research Article

Download the article with the following link or find it on HAL (archives-ouvertes.fr):
–> Topology Aware Leader Election Algorithm for Dynamic Networks.pdf