Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial global configuration satisfies a given property, specified as a predicate on the set of configurations. The state complexity of a predicate is the number of states of a smallest protocol that computes it. Previous work by Blondin \textit{et al.} has shown that the counting predicates $x \geq \eta$ have state complexity $\mathcal{O}(\log \eta)$ for leaderless protocols and $\mathcal{O}(\log \log \eta)$ for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of $x \geq \eta$ is $\Omega(\log\log \eta)$ for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.
翻译：人口协议是一种计算模型, 任意数量无法区分的有限国家代理商在其中进行对对方互动。 代理商的目标是以稳定的共识决定其初始全球配置是否满足一个特定属性, 指定该属性为一组配置的前提。 上游的复杂性是计算该属性的最小协议的状态。 Brondin\ textit{et al.} 先前的工作表明, 无领导协议的计算前端值为$x\geq\eta$( log\ eta), 无领导协议的计算为$\ mathcal{ O} (\log\ eta)$, 与领导者的协议为$\ mathcal{ O} (log\log\log\ log\ deta) $。 我们获得第一个非三边下框值的状态复杂性: $x\geq\ eta$ 的状态复杂性是 $\\ omega (log\ \ \ eta) $, 而与领导者之间的协议则反非元素功能 。
相关内容
微信扫码咨询专知VIP会员