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.

Publié dans:
Proceedings of the 2006 International Conference on Distributed Computing in Sensor Systems (DCOSS '06)
Présenté à:
2006 ACM/IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '06)
Autres identifiants:

 Notice créée le 2006-02-27, modifiée le 2019-04-16

Télécharger le document

Évaluer ce document:

Rate this document:
(Pas encore évalué)