论文标题
$ O（\ log^{3/2} n）$以$ o（\ log n）$状态为多数的并行时间总体协议
An $O(\log^{3/2}n)$ Parallel Time Population Protocol for Majority with $O(\log n)$ States
论文作者
论文摘要
在人口协议中，基础分布式网络由$ n $ nodes（或代理）组成，用$ v $表示，以及连续选择均匀随机的节点对交互的调度程序。当两个节点相互作用时，它们的状态将通过应用一个仅取决于交互之前两个节点的状态的状态过渡函数来更新。人口协议的效率是根据两个时间来衡量的（这是节点共同具有有效输出的相互作用数量）和协议使用的可能的节点的可能状态数。按照惯例，我们考虑并行时间成本，这是分配$ n $的时间。 在本文中，我们考虑了大多数问题，每个节点都会接收到黑色或白色的颜色，目标是使所有节点输出大多数输入颜色的颜色。我们设计了一个人口协议，该协议在$ o（\ log^{3/2} n）$并行时间中解决多数问题，既有很高的概率又有预期，同时使用$ o（\ log n）$状态。我们的协议改进了Berenbrink等人的最新协议。使用$ O（\ log n）$状态，以$ o（\ log^{5/3} n）$并行时间运行。
In population protocols, the underlying distributed network consists of $n$ nodes (or agents), denoted by $V$, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by $n$. In this paper we consider the majority problem, where each node receives as input a color that is either black or white, and the goal is to have all of the nodes output the color that is the majority of the input colors. We design a population protocol that solves the majority problem in $O(\log^{3/2}n)$ parallel time, both with high probability and in expectation, while using $O(\log n)$ states. Our protocol improves on a recent protocol of Berenbrink et al. that runs in $O(\log^{5/3}n)$ parallel time, both with high probability and in expectation, using $O(\log n)$ states.
