时间与空间最优的无声自稳定精确多数协议在群体协议中的研究
Time- and Space-Optimal Silent Self-Stabilizing Exact Majority in Population Protocols
摘要 Abstract
我们研究了由Angluin、Aspnes、Diamadi、Fischer和Peralta(2004)引入的群体协议模型中的自稳定精确多数问题。在这个模型中,有$n$个状态机,称为代理,它们构成一个网络。在每个时间步长中,只有两个代理相互交互并更新其状态。在自稳定精确多数问题中,每个代理有一个固定意见,$\mathtt{A}$或$\mathtt{B}$,并且从任何初始配置开始,所有代理都会稳定到一个安全配置,在该配置下所有代理都输出多数意见。本文证明了在不知道$n$的情况下,任何协议都无法解决自稳定精确多数问题。我们提出了一种无声的自稳定精确多数协议,该协议期望在$O(n)$并行时间内稳定,并且以高概率在$O(n \log n)$并行时间内稳定,使用$O(n)$状态,并且需要知道$n$。这里,无声协议意味着在稳定后,每个代理的状态不会改变。我们还建立了下界,证明任何无声协议达到安全配置都需要$\Omega(n)$状态,$\Omega(n)$期望并行时间和$\Omega(n \log n)$高概率并行时间。因此,所提出的协议在时间和空间上都是最优的。
We address the self-stabilizing exact majority problem in the population protocol model, introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta (2004). In this model, there are $n$ state machines, called agents, which form a network. At each time step, only two agents interact with each other, and update their states. In the self-stabilizing exact majority problem, each agent has a fixed opinion, $\mathtt{A}$ or $\mathtt{B}$, and stabilizes to a safe configuration in which all agents output the majority opinion from any initial configuration. In this paper, we show the impossibility of solving the self-stabilizing exact majority problem without knowledge of $n$ in any protocol. We propose a silent self-stabilizing exact majority protocol, which stabilizes within $O(n)$ parallel time in expectation and within $O(n \log n)$ parallel time with high probability, using $O(n)$ states, with knowledge of $n$. Here, a silent protocol means that, after stabilization, the state of each agent does not change. We establish lower bounds, proving that any silent protocol requires $\Omega(n)$ states, $\Omega(n)$ parallel time in expectation, and $\Omega(n \log n)$ parallel time with high probability to reach a safe configuration. Thus, the proposed protocol is time- and space-optimal.