The Weakest Oracle for Symmetric Consensus in Population Protocols

Abstract : 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.
Type de document :
Communication dans un congrès
11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2015), Sep 2015, Patras, Greece
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01247021
Contributeur : Janna Burman <>
Soumis le : lundi 21 décembre 2015 - 02:34:36
Dernière modification le : mardi 24 avril 2018 - 13:38:35
Document(s) archivé(s) le : samedi 29 avril 2017 - 22:56:11

Fichier

paper_8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01247021, version 1

Citation

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〉

Partager

Métriques

Consultations de la notice

362

Téléchargements de fichiers

27