论文标题
人口协议的良好比较
Robust Comparison in Population Protocols
论文作者
论文摘要
最近，人们对人口模型的计算和复杂性特性引起了人们的兴趣，该模型假设$ n $ noby，计算结合的节点，随机交互，并试图共同计算全球谓词。在此模型中，重要的工作旨在调查多数和共识动态：假设每个节点最初都在两个状态之一$ x $或$ y $中，则确定哪个州的初始计数较高。 在本文中，我们考虑了多数/共识的自然概括，我们称之为比较。我们得到了两个基线状态，$ x_0 $和$ y_0 $，以任何初始配置中的固定，可能很小的计数中存在。重要的是，其中一个状态的数量高于另一个状态：我们将假设$ | x_0 | \ ge c | y_0 | $对于某些常数$ c $。挑战是设计一个可以快速可靠地决定哪个基线状态$ x_0 $和$ y_0 $的协议的初始计数。 我们提出了一个简单的算法求解比较：基线算法使用$ o（\ log n）$状态，并在$ o（\ log n）$（\ log n）$（平行时间）中收敛，并具有很高的可能性，以一种状态为$ x $或$ y $以$ x $或$ y $以初始$ y $ y $ y $ y $ | x_0 | $ | x_0 | $ vs. $ vs. $ vs. $ vs. $ vs. $ | $ | y |然后，我们描述如何使用此类输出来解决比较。该算法正在自动化，从某种意义上说，即使基线的相对计数$ x_0 $和$ y_0 $在执行过程中动态变化，并且泄漏boblust，即使它可以承受虚假的错误反应，因此它会收敛到正确的决策。我们的分析依赖于新的Martingale集中结果，该结果将人口方案的演变与其预期（稳态）分析有关，该分析应广泛适用于人口协议和意见动态的背景。
There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes $n$ anonymous, computationally-bounded nodes, interacting at random, and attempting to jointly compute global predicates. Significant work has gone towards investigating majority and consensus dynamics in this model: assuming that each node is initially in one of two states $X$ or $Y$, determine which state had higher initial count. In this paper, we consider a natural generalization of majority/consensus, which we call comparison. We are given two baseline states, $X_0$ and $Y_0$, present in any initial configuration in fixed, possibly small counts. Importantly, one of these states has higher count than the other: we will assume $|X_0| \ge C |Y_0|$ for some constant $C$. The challenge is to design a protocol which can quickly and reliably decide on which of the baseline states $X_0$ and $Y_0$ has higher initial count. We propose a simple algorithm solving comparison: the baseline algorithm uses $O(\log n)$ states per node, and converges in $O(\log n)$ (parallel) time, with high probability, to a state where whole population votes on opinions $X$ or $Y$ at rates proportional to initial $|X_0|$ vs. $|Y_0|$ concentrations. We then describe how such output can be then used to solve comparison. The algorithm is self-stabilizing, in the sense that it converges to the correct decision even if the relative counts of baseline states $X_0$ and $Y_0$ change dynamically during the execution, and leak-robust, in the sense that it can withstand spurious faulty reactions. Our analysis relies on a new martingale concentration result which relates the evolution of a population protocol to its expected (steady-state) analysis, which should be broadly applicable in the context of population protocols and opinion dynamics.
