Time-Space Trade-offs in Population Protocols
Time-Space Trade-offs in Population Protocols
复制标题
DOI：
10.1137/1.9781611974782.169
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
中科院分区：
文献类型：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
群体协议是一种流行的分布式计算模型，其中具有很少计算能力的随机交互代理合作共同执行计算任务。受分子计算（特别是 DNA 计算）发展的启发，最近的算法工作重点关注解决群体模型中简单但基本任务的复杂性，例如领导者选举（这需要收敛到处于特殊“领导”状态的单个智能体）和多数（智能体必须收敛到决定两个可能的初始状态中哪一个具有更高的初始计数）。已知的结果表明此类算法的时间复杂度和空间复杂度（即每个代理可用的内存大小）之间存在固有的权衡。在本文中，我们探讨了这种权衡，并为多数选举和领导者选举提供了新的上限和下限。首先，我们证明了一个统一的下界，它将每个节点的可用空间与协议可实现的时间复杂度联系起来：例如，我们的结果意味着使用 O(log log n) 状态为 n 个代理解决这些任务中的任何一个的协议都必须花费 Ω(n/polylogn) 预期时间。这是第一个表征每个节点采用超恒定状态数的协议的时间复杂度的结果，并证明快速的多对数运行时间要求协议具有相对较大的空间成本。从积极的方面来看，我们给出的算法表明，在这两个任务的情况下，使用每个节点的 O(log2 n) 空间可以实现快速、多对数收敛时间。总体而言，我们的结果强调了群体协议中多数选举和领导者选举的 O (log log n) 和 θ(log2 n) 状态空间大小之间的时间复杂度分离，并引入了应该更广泛适用的新技术。
Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special "leader" state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O(log log n) states must take Ω(n/polylogn) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O(log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O (log log n) and Θ(log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.