In this talk, I will discuss distributed leader election algorithms in weak distributed communication models such as the beeping model and the stone-age model. Unlike most previous works, our algorithm operates with only six states, does not require unique identifiers, and makes no assumptions about prior knowledge of the network’s size or topology. We show that, under our randomized protocol, the system almost surely converges to a configuration in which a single node enters the leader state, in O(D² log n) rounds, where D is the network diameter. Moreover, if an approximation of D is known, the convergence time can be improved to O(D log n).
The algorithm is not self-stabilizing, as it requires all nodes to start from the same initial state. I will also present a generalization of the algorithm in the state-based computation model, aiming to achieve a self-stabilizing solution.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne