When Birds Die: Making Population Protocols Fault-tolerant

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.

Published in:
Proceedings of the 2006 International Conference on Distributed Computing in Sensor Systems (DCOSS '06)
Presented at:
2006 ACM/IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '06)
Other identifiers:

Note: The status of this file is: Anyone

 Record created 2006-02-27, last modified 2020-10-28

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)