An O(log3/2 n) Parallel Time Population Protocol for Majority with O(log n) States
An O(log3/2 n) Parallel Time Population Protocol for Majority with O(log n) States
复制标题
具有 O(log n) 状态的多数的 O(log3/2 n) 并行时间填充协议
DOI：
10.1145/3382734.3405747
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
E. Porat
中科院分区：
文献类型：
--
作者：
Stav Ben;T. Kopelowitz;Matan Kraus;E. Porat
在种群协议中，底层分布式网络由n个节点(或代理)(用V表示)和一个调度器组成，该调度器连续选择均匀随机的节点对进行交互。当两个节点交互时，通过应用仅依赖于交互之前两个节点的状态的状态转移函数来更新它们的状态。种群协议的效率是根据时间(这是在节点共同具有有效输出之前的交互次数)和协议使用的节点的可能状态的数量来衡量的。按照惯例，我们考虑并行时间开销，即时间除以n。在本文中，我们考虑多数问题，其中每个节点接收黑色或白色作为输入，目标是让所有节点输出的颜色是输入颜色的大多数。我们设计了一个种群协议，该协议在O(log3/2n)个并行时间内以较高的概率和期望解决了大多数问题，同时使用O(Logn)个状态。我们的协议改进了Berenbrink等人最近的协议。其运行时间为O(log5/3n)个并行时间，使用O(Logn)个状态，具有很高的概率和期望值。
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(log3/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(log5/3 n) parallel time, both with high probability and in expectation, using O(log n) states.
DOI：
10.1137/1.9781611974782.169
发表时间：
2016-02
期刊：
ArXiv
影响因子：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
通讯作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest