论文标题
人口协议的建设性表达能力
Constructive expressive power of population protocols
论文作者
论文摘要
人口协议是用于研究具有动态通信结构的独立计算代理网络的分布式计算模型。每个代理商都有有限数量的州，并且沟通机会是无确定性的，允许参与的代理商根据彼此的州改变其州。通常，就输入配置满足某些谓词而达成共识，通常研究人口协议。 在本文中，我们提出了另一种观点。我们没有研究协议可以识别的投入的属性，而是研究协议最终确保的输出的性质。我们定义建设性的表现力。我们表明，对于一般人口方案和立即观察人口协议，建设性表达能力与正常表达能力一致。 即时观察方案还可以在建设性表达能力设置中保留其相对较低的验证复杂性。
Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication opportunities occur nondeterministically, allowing the agents involved to change their states based on each other's states. Population protocols are often studied in terms of reaching a consensus on whether the input configuration satisfied some predicate. In the present paper we propose an alternative point of view. Instead of studying the properties of inputs that a protocol can recognise, we study the properties of outputs that a protocol eventually ensures. We define constructive expressive power. We show that for general population protocols and immediate observation population protocols the constructive expressive power coincides with the normal expressive power. Immediate observation protocols also preserve their relatively low verification complexity in the constructive expressive power setting.
