期刊
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 140, 期 -, 页码 -出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2023.103481
关键词
Population protocols; Fast; Succinct; Population computers
This paper presents a construction method that produces population protocols with a small number of states, while achieving near-optimal expected number of interactions, for deciding Presburger predicates.
In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O(m center dot n2log n) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at 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 O(m) states that run in expected O(m7 center dot n2) interactions, optimal in n, for all inputs of size S2(m). For this, we introduce population computers, a generalization of population protocols, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.(c) 2023 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据