Mouna Safir (ENS Lyon)
Title: Self-Stabilizing Mutual Exclusion in Dynamic Networks with Bounded Temporal Diameter
Abstract:
We consider distributed systems subject to frequent topological changes. Specifically, we assume the network topology evolves as a dynamic graph in which, at any point in time, the temporal distance between any two processes is at most Δ.
In this setting, where processes have unique identifiers and know both Δ and an upper bound N on the system size n, we introduce a self-stabilizing solution to the mutual exclusion problem.
Our algorithm stabilizes in O(NΔ) rounds, uses bounded memory, and once converged guarantees an optimal waiting time of n−1 rounds before a process can enter its critical section.
The solution is built from three self-stabilizing algorithms: Leader Election, Unison, and Ranking. We contribute new self-stabilizing algorithms for Unison and Ranking, and we combine them with a recent leader election protocol from Altisen et al. (TCS 2023).