Self-stabilizing Mutual Exclusion in Dynamic Networks with Bounded Temporal Diameter
摘要
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 \(\varDelta \) . Under a synchronous message-passing model where processes have unique identifiers and know both \(\varDelta \) and an upper bound N on the number of processes n, we provide a distributed self-stabilizing mutual exclusion algorithm working in that class of dynamic graphs. Our solution stabilizes in \(\mathcal{O}(\varDelta .N)\) rounds using bounded local memories. Moreover, it achieves optimal waiting time: once stabilized, the maximum delay before a process enters its critical section is at most \(n-1\) rounds. Our algorithm is actually a composition of several self-stabilizing building blocks that respectively achieve Leader Election, Unison, and Ranking. We also provide original self-stabilizing solutions for the latter two problems; for the self-stabilizing leader election, we use a solution given by Altisen et al. (Theoretical Computer Science, 2023).