Even Small Birds are Unique: Population Protocols with Identifiers
Even Small Birds are Unique: Population Protocols with Identifiers
复制标题
即使是小鸟也是独一无二的：带有标识符的种群协议
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
E. Ruppert
中科院分区：
文献类型：
--
作者：
R. Guerraoui;E. Ruppert
虽然很多研究都致力于设计和实验的ad hoc网络的微小设备，很少有专注于设计理论模型，以捕捉这种网络的固有的权力和局限性。一个值得注意的例外是Angluin等人的群体方案模型[2]。这种模型简单而优雅，但有时被认为过于限制，因为它的匿名性：移动的代理没有身份，而且看起来都一样。在本文中，我们调查的人口协议模型的固有权力，增强了每个代理的能力，以唯一地确定以及存储恒定数量的其他代理的标识符。我们提供了一个精确的表征什么可以计算在这个新的社区协议模型：一个函数可以计算，当且仅当它是对称的，在NSPACE（n log n）。这是使用指针机器的模拟示出的。我们还考虑了我们的社区协议模型处理故障的能力。我们描述了什么可以计算时，有一个常数的良性故障，并表明，非平凡的计算可以实现，即使代理可以拜占庭。
Although much research has been devoted to designing and experimenting on ad hoc networks of tiny devices, very little has focussed on devising theoretical models to capture the inherent power and limitations of such networks. A notable exception is the population protocol model of Angluin et al. [2]. This model is simple and elegant but is sometimes considered too restrictive because of its anonymity: mobile agents have no identities and all look the same. We investigate in this paper the inherent power of the population protocol model augmented with the ability of each agent to be uniquely identified as well as store a constant number of other agents’ identifiers. We provide an exact characterization of what can be computed in this new community protocol model: a function can be computed if and only if it is symmetric and in NSPACE(n log n). This is shown using a simulation of pointer machines. We also consider the ability of our community protocol model to handle failures. We describe what can be computed when there are a constant number of benign failures and show that nontrivial computations can be achieved even if agents can be Byzantine.