The Weakest Oracle for Symmetric Consensus in Population Protocols - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

The Weakest Oracle for Symmetric Consensus in Population Protocols

Résumé

We consider the symmetric consensus problem, a version of consensus adapted to population protocols, a model for large scale networks of resource-limited mobile sensors. After proving that consensus is impossible in the considered model, we look for oracles to circumvent this impossibility. An oracle is an external (to the system) module providing some information allowing to solve the problem. We define a class of oracles adapted to population protocols, and we prove that an oracle in this class, namely DejaVu, allows to obtain a solution. Finally, and this is the major contribution of the paper, we prove that DejaVu is the weakest oracle for solving the problem.
Fichier principal
Vignette du fichier
paper_8.pdf (495.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01247021 , version 1 (21-12-2015)

Identifiants

  • HAL Id : hal-01247021 , version 1

Citer

Joffroy Beauquier, Peva Blanchard, Janna Burman, Shay Kutten. The Weakest Oracle for Symmetric Consensus in Population Protocols. 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2015), Sep 2015, Patras, Greece. ⟨hal-01247021⟩
213 Consultations
78 Téléchargements

Partager

Gmail Facebook X LinkedIn More