Paper Info
Title
Self-stabilizing mutual exclusion and group mutual exclusion for population protocols with covering
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 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.
Year
DOI
Venue
2011
10.1007/978-3-642-25873-2_17
OPODIS
Keywords
Field
DocType
anonymous mobile agents interact,particular agent,phase clock tool,cover time,group mutual exclusion problem,paper present,mutual exclusion problem,population protocol model,synchronization tool,mutual exclusion,distributed algorithms,synchronization,self stabilization
Population,Pairwise comparison,Synchronization,Computer science,Population protocol,Self-stabilization,Distributed algorithm,Mutual exclusion,Distributed computing,Bounded function
Conference
Volume
ISSN
Citations 
7109
0302-9743
4
PageRank 
References 
Authors
0.47
21
2
Name
Order
Citations
PageRank
Joffroy Beauquier144853.52
Janna Burman212313.55