Self-stabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering

Joffroy Beauquier 1, 2 Janna Burman 1, 2, 3
2 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : This paper presents and proves correct two self-stabilizing deterministic algorithms solving the mutual exclusion and the group mutual exclusion problems in the model of population protocols with covering. In this variant of the population protocol model, a local fairness is used and bounded state anonymous mobile agents interact in pairs according to constraints expressed in terms of their cover times. The cover time is an indicator of the "time" for an agent to communicate with all the other agents. This indicator is expressed in the number of the pairwise communications (events) and is unknown to agents. In the model, we also assume the existence of a particular agent, the base station. In contrast with the other agents, it has a memory size proportional to the number of the agents. We prove that without this kind of assumption, the mutual exclusion problem has no solution. The algorithms in the paper use a phase clock tool. This is a synchronization tool that was recently proposed in the model we use. For our needs, we extend the functionality of this tool to support also phases with unbounded (but finite) duration. This extension seems to be useful also in the future works.
Type de document :
Communication dans un congrès
15th International Conference On Principles Of Distributed Systems, OPODIS 2011, Dec 2011, Toulouse, France. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00639651
Contributeur : Janna Burman <>
Soumis le : mardi 22 novembre 2011 - 16:35:51
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : jeudi 23 février 2012 - 02:20:15

Fichier

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

Identifiants

  • HAL Id : hal-00639651, version 1

Citation

Joffroy Beauquier, Janna Burman. Self-stabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering. 15th International Conference On Principles Of Distributed Systems, OPODIS 2011, Dec 2011, Toulouse, France. 2011. 〈hal-00639651〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

116