自我穩定 k 個意見精準多數

Abstract

群體協議[3]是一個被廣泛研究的分散式模型，它能夠描述由被動個體組成之系統的行為。領導者選舉和精準多數是在群體協議模型中兩個最重要的研究問題。此外，自我穩定這件事在最近越來越重要，因為他的容錯性質，可以使得系統從任意狀態收斂至要求的狀態。我們研究了自我穩定k個意見精準多數問題，它要求所有個體最終皆能獲k個相異初始意見中，具備最大初始支持度的那個意見，無論從任何初始的狀態下。 在本文中，我們提出了一種能夠解決自我穩定k個意見精準多數的群體協議。給定群體協議中規模n的知識，該協議能夠在O(k^3n)的狀態和O(kn^2)的平行時間內，高機率地決定精準多數。藉由修改令牌的傳遞方式，協議能在改善至在 O(knlogn) 平行時間內高機率地決定精準多數。並且我們給出了一種能夠在O(n)的狀態和O(n)的期望平行時間內，解決沈默自我穩定k=3個意見精準多數的群體協議。

The population protocols [3] are a widely studied distributed model that describes the behavior of a system composed of passively mobile agents. Leader election and majority are two of the most important research problems in population protocols. Additionally, self-stabilization has become increasingly important recently due to its fault-tolerant property, which allows a system to stabilize to a desired configuration from any arbitrary configuration. We study the self-stabilizing exact k-majority problem, which requires all agents to obtain the opinion with the largest initial support among k distinct opinions, regardless of the initial configuration. In this paper, we propose a self-stabilizing population protocol for the exact majority problem with k opinions. Given knowledge of the population size n, the protocol determines the majority opinion using O(k^3n) states within O(kn^2) parallel time with high probability. By modifying the token propagation method, the protocol can be enhanced to determine the majority within O(knlogn) parallel time with high probability. Furthermore, we introduce a silent self-stabilizing protocol that solves the problem for k = 3 opinions using O(n) states within O(n) expected parallel time.