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...
-
December 12, 2011 (v1)Conference paperUploaded on: December 3, 2022
-
September 22, 2011 (v1)Report
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...
Uploaded on: December 4, 2022 -
June 21, 2010 (v1)Conference paper
International audience
Uploaded on: December 3, 2022 -
2017 (v1)Journal article
This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. This problem has been mainly studied for its relationship with the pathwidth of graphs. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This...
Uploaded on: February 28, 2023 -
February 2012 (v1)Report
In graph searching, a team of mobile agents aims at clearing the edges of a contaminated graph. To clear an edge, an agent has to slide along it, however, an edge can be recontaminated if there is a path without agents from a contaminated edge to a clear edge. To goal of graph searching is to clear the graph, i.e., all edges are clear...
Uploaded on: December 3, 2022 -
October 2012 (v1)Conference paper
We tackle a practical version of the well known {\it graph searching} problem, where a team of robots aims at capturing an intruder in a graph. The robots and the intruder move along the edges of the graph. The intruder is invisible, arbitrary fast, and omniscient. It is caught whenever it stands on a node occupied by a robot, and cannot escape...
Uploaded on: December 4, 2022 -
2011 (v1)Conference paper
Nous étudions le protocole de collecte de données du projet ZebraNet, dans le modèle des protocoles de population. Dans ce projet des capteurs sont attachés à une population de zèbres, en Afrique Centrale, et fournissent des données aux biologistes qui étudient leurs structures migratoires et comportementales. Nous montrons qu'un protocole...
Uploaded on: December 3, 2022 -
September 2, 2013 (v1)Conference paper
This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This assumption may be unrealistic, e.g., in the case of searchers modeling physical...
Uploaded on: December 2, 2022 -
2012 (v1)Conference paper
Dans le cadre du nettoyage de graphes contaminés ( graph searching), des agents mobiles se déplacent successivement le long des arêtes du graphe afin de les nettoyer. Le but général est le nettoyage en utilisant le moins d'agents possible. Nous plaçons notre étude dans le modèle de calcul distribué CORDA minimaliste. Ce modèle est muni...
Uploaded on: December 3, 2022 -
July 25, 2010 (v1)Conference paper
Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only....
Uploaded on: December 4, 2022 -
February 2020 (v1)Journal article
Contrary to many previous studies on population protocols using the uniformly random scheduler, we consider a more general non-uniform case. Here, pair-wise interactions between agents (moving and communicating devices) are assumed to be drawn non-uniformly at random. While such a scheduler is known to be relevant for modeling many practical...
Uploaded on: February 25, 2024 -
July 26, 2021 (v1)Conference paper
We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time...
Uploaded on: February 25, 2024