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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Self-stabilizing Mutual Exclusion in Dynamic Networks with Bounded Temporal Diameter

  • Stéphane Devismes,
  • Swan Dubois,
  • François Malenfer,
  • Franck Petit,
  • Mouna Safir

摘要

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).