论文标题
催化输入的大约多数
Approximate Majority With Catalytic Inputs
论文作者
论文摘要
人口协议是一类算法，用于建模有限状态代理网络中通过成对相互作用进行通信的分布式计算。它们用于分析众多化学过程的适用性激发了原始人口协议框架的适应，以更好地对这些化学系统进行建模。在本文中，我们在解决大约多数的背景下进一步研究了两个这样的适应：持续状态的药物（或催化剂）和自发状态变化（或泄漏）。 基于最新协议中对具有持续状态代理商的人群的模型，我们假设一个人口具有$ n $催化输入代理和$ m $工人的代理商，而工人代理的目标是计算催化输入状态的一些谓词。我们将此模型称为催化输入（CI）模型。对于$ m =θ（n）$，我们表明，计算具有较高概率的确切大多数输入总体需要至少$ω（n^2）$总交互作用，这表明CI模型与标准种群协议模型之间存在很强的分离。另一方面，我们证明了Angluin等人的简单第三态动力学。对于标准模型中的大约多数，可以自然地适应CI模型：我们为CI模型提供了这样的恒定状态协议，该协议在$ O（n \ log n）$总数中求解了大约多数的总数。当输入保证金为$ω（\ sqrt {n \ log n}）$时。 然后，我们向Alistarh等人引入的瞬态泄漏事件显示了第三状态动力学方案的鲁棒性。在原始模型和CI模型中，这些协议在每个步骤出现泄漏的情况下成功地计算了大约多数，概率$β\ leq o \ left（\ sqrt {n \ log n}/n}/n \ right）$，表现出类似于以前的工具中类似于Byzantine Agenter的泄漏的弹性。
Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents, we assume a population with $n$ catalytic input agents and $m$ worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For $m = Θ(n)$, we show that computing the exact majority of the input population with high probability requires at least $Ω(n^2)$ total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics of Angluin et al. for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in $O(n \log n)$ total steps w.h.p. when the input margin is $Ω(\sqrt{n \log n})$. We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by Alistarh et al. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability $β\leq O\left(\sqrt{n \log n}/n\right)$, exhibiting a resilience to leaks similar to that of Byzantine agents in previous works.
