Global Versus Local Computations: Fast Computing with Identifiers
Global Versus Local Computations: Fast Computing with Identifiers
复制标题
全局计算与局部计算：使用标识符进行快速计算
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Rabie
中科院分区：
文献类型：
--
作者：
M. Rabie
本文研究了什么可以计算通过使用概率本地交互与代理具有非常有限的权力在polylogarithmic并行时间。已知如果主体仅为有限状态（对应于Angluin等人的群体协议模型），则只能计算全局输入上的半线性谓词。事实上，如果种群以唯一的领导者开始，这些谓词甚至可以在多对数并行时间内计算。如果添加标识符（对应于Guerraoui和Ruppert的Community Protocol模型），则可以计算输入多集上的更多全局谓词。也可以计算根据标识符排序的输入上的局部谓词，只要标识符是有序的。其中一些谓词的时间可能需要指数并行时间。在本文中，我们考虑什么可以计算与社区协议在一个多对数的并行交互。我们引入类CPPL对应的协议，使用$O（nlog ^k n）$，对于一些k，预期的相互作用来计算其谓词，或等价的多对数并行预期的相互作用。我们提供了一些可计算的协议，类的一些边界，使用人口可以计算其大小的事实。我们还证明了两个不可能的结果，提供了一些参数，表明本地计算不再容易：人口没有时间比较一个线性数量的连续标识符。线性局部语言，例如有理语言$（ab）^*$，是不可计算的。
This paper studies what can be computed by using probabilistic local interactions with agents with a very restricted power in polylogarithmic parallel time. It is known that if agents are only finite state (corresponding to the Population Protocol model by Angluin et al.), then only semilinear predicates over the global input can be computed. In fact, if the population starts with a unique leader, these predicates can even be computed in a polylogarithmic parallel time. If identifiers are added (corresponding to the Community Protocol model by Guerraoui and Ruppert), then more global predicates over the input multiset can be computed. Local predicates over the input sorted according to the identifiers can also be computed, as long as the identifiers are ordered. The time of some of those predicates might require exponential parallel time. In this paper, we consider what can be computed with Community Protocol in a polylogarithmic number of parallel interactions. We introduce the class CPPL corresponding to protocols that use $O(nlog^k n)$, for some k, expected interactions to compute their predicates, or equivalently a polylogarithmic number of parallel expected interactions. We provide some computable protocols, some boundaries of the class, using the fact that the population can compute its size. We also prove two impossibility results providing some arguments showing that local computations are no longer easy: the population does not have the time to compare a linear number of consecutive identifiers. The Linearly Local languages, such that the rational language $(ab)^*$, are not computable.