環形的群體協議中，快速且空間高效的自我穩定領導者選舉

Abstract

在本文中，我們提出了一種能夠在有向環上解決自穩定領導者選舉問題的群 體協議。給定對群體規模 n 的知識 ψ = ⌈log log n⌉ + O(1)，該協議能夠以高機率 在步內選出唯一的領導者。此後，群體將永遠保持這個唯一的領導者。該協議使 用 polyloglog(n) 個狀態。與現有文獻相比，我們的協議保持了快速收斂速度，並 進一步減少了所使用的狀態數量。

In this paper, we propose a population protocol that solves self-stabilizing leader election on directed rings. Given a knowledge ψ = ⌈log log n⌉ + O(1) about the popu- lation size n, the protocol elects a unique leader within O(n2 log n log log n) steps with high probability. Thereafter, the population keeps the unique leader forever. The protocol uses polyloglog(n) states. Compared to the current literature, our protocol maintains a fast convergence speed and further reduces the number of states used.