When Birds Die: Making Population Protocols Fault-Tolerant
When Birds Die: Making Population Protocols Fault-Tolerant
复制标题
当鸟类死亡时：使种群协议具有容错能力
DOI：
10.1007/11776178_4
复制
发表时间：
2006
影响因子：
1.3
通讯作者：
E. Ruppert
中科院分区：
文献类型：
--
作者：
C. Delporte;H. Fauconnier;R. Guerraoui;E. Ruppert
在Anluin等人介绍的种群协议模型中。[2]，由有限状态机建模的代理的集合，不可预测地移动，并具有成对交互。在没有故障的情况下，研究了这种系统在最初分布在所有代理上的多组输入上计算函数的能力。在这里，我们证明了在存在停顿和瞬时故障的情况下，基本上可以计算出相同的函数集，只要在输入上添加了前提条件，使得故障不会立即掩盖足够多的输入来改变结果。为此，我们给出了一种通用变换，使无故障设置的任何算法都能容忍故障。
In the population protocol model introduced by Angluin et al. [2], a collection of agents, which are modelled by finite state machines, move around unpredictably and have pairwise interactions. The ability of such systems to compute functions on a multiset of inputs that are initially distributed across all of the agents has been studied in the absence of failures. Here, we show that essentially the same set of functions can be computed in the presence of halting and transient failures, provided preconditions on the inputs are added so that the failures cannot immediately obscure enough of the inputs to change the outcome. We do this by giving a general-purpose transformation that makes any algorithm for the fault-free setting tolerant to failures.