论文标题
前爆发算术的快速，简洁的人口协议
Fast and Succinct Population Protocols for Presburger Arithmetic
论文作者
论文摘要
在其在分布式计算中的2006年开创性论文中，Angluin等人。呈现一个结构，鉴于任何作为输入的前爆发谓词，它会输出决定谓词的无领导人群协议。大小$ m $的谓词的协议（当表示为阈值和剩余系数的布尔组合时，二进制中的系数）以$ \ Mathcal {o}（M \ cdot n^2 \ log n）$预期的交互作用数，在$ n $中几乎是最佳的。但是，协议的状态数在$ m $中为指数。 Blondin等。在Stacs 2020中描述了另一种结构，该结构产生了具有多项式状态数量但预期相互作用数量的协议。我们提出了一种结构，该结构以$ \ MATHCAL {o}（m）$状态生产协议，该状态以预期的$ \ MATHCAL {O}（M^{7} \ cdot n^2）$ noctootions（M^{7} \ cdot n^2）$ n $中的所有输入，对于所有尺寸$ω（m）$。为此，我们介绍了人口计算机，对人口协议的精心制作的概括更容易编程，并表明我们用于前灌注谓词的计算机可以转化为快速，简洁的人口协议。
In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate as input, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size $m$ (when expressed as a Boolean combination of threshold and remainder predicates with coefficients in binary) runs in $\mathcal{O}(m \cdot n^2 \log n)$ expected number of interactions, which is almost optimal in $n$. However, the number of states of the protocol is exponential in $m$. Blondin et al. described in STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with $\mathcal{O}(m)$ states that run in expected $\mathcal{O}(m^{7} \cdot n^2)$ interactions, optimal in $n$, for all inputs of size $Ω(m)$. For this we introduce population computers, a carefully crafted generalization of population protocols easier to program, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.
