Colloquium

• July 18, 2024, Thursday, 17:00–
• AFSA Teramachi Lab, Kyoto University

State-efficient self-stabilizing population protocols for the ranking problem

• Leszek Gąsieniec (University of Liverpool)

We investigate the ranking problem within self-stabilizing population protocols. In this scenario, the agent's state space comprises n rank states and x extra states. The initial configuration of n agents consists of arbitrary arrangements of rank and extra states, with the objective of self-ranking. Specifically, each agent is tasked with stabilizing in a unique rank state silently, implying that after stabilization, each agent remains in its designated state indefinitely.

We present several new self-stabilizing ranking protocols. All protocols ensure self-stabilization time with high probability (whp). We delve into three scenarios, from which we derive stable (always correct), either state-optimal or almost state-optimal, silent ranking protocols that self-stabilize within a time frame of o(n²) whp, including:

1. Utilising a novel concept of an agent trap, we derive a state-optimal ranking protocol that achieves self-stabilization in time O(min(kn^3/2, n² log^⁡2 n)), for any k-distant starting configuration, i.e., when at most k rank states are absent in the initial setup.
2. Furthermore, we show that the incorporation of a single extra state ensures a ranking protocol that self-stabilizes in time O(n^7/4 log^⁡2 n) = o(n²), regardless of the initial configuration.
3. Lastly, we show that extra O(log ⁡n) states admit self-stabilizing ranking with the best currently known stabilization time O(n log ⁡n), when whp and x = O(log n) guarantees are imposed.

Joint work with Tytus Grodzicki and Grzegorz Stachowiak.