Search Results

Documents authored by Beauquier, Joffroy

Document
DOI: 10.4230/LIPIcs.DISC.2023.8
Treasure Hunt with Volatile Pheromones

Authors: Evangelos Bampas, Joffroy Beauquier, Janna Burman, and William Guy--Obé

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
In the treasure hunt problem, a team of mobile agents need to locate a single treasure that is hidden in their environment. We consider the problem in the discrete setting of an oriented infinite rectangular grid, where agents are modeled as synchronous identical deterministic time-limited finite-state automata, originating at a rate of one agent per round from the origin. Agents perish τ rounds after their creation, where τ ≥ 1 is a parameter of the model. An algorithm solves the treasure hunt problem if every grid position at distance τ or less from the origin is visited by at least one agent. Agents may communicate only by leaving indistinguishable traces (pheromone) on the nodes of the grid, which can be sensed by agents in adjacent nodes and thus modify their behavior. The novelty of our approach is that, in contrast to existing literature that uses permanent pheromone markers, we assume that pheromone traces evaporate over μ rounds from the moment they were placed on a node, where μ ≥ 1 is another parameter of the model. We look for uniform algorithms that solve the problem without knowledge of the parameter values, and we investigate the implications of this very weak communication mechanism to the treasure hunt problem. We show that, if pheromone persists for at least two rounds (μ ≥ 2), then there exists a treasure hunt algorithm for all values of agent lifetime. We also develop a more sophisticated algorithm that works for all values of μ, hence also for the fastest possible pheromone evaporation of μ = 1, but only if agent lifetime is at least 16.
Cite as

Evangelos Bampas, Joffroy Beauquier, Janna Burman, and William Guy--Obé. Treasure Hunt with Volatile Pheromones. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bampas_et_al:LIPIcs.DISC.2023.8,
  author =	{Bampas, Evangelos and Beauquier, Joffroy and Burman, Janna and Guy--Ob\'{e}, William},
  title =	{{Treasure Hunt with Volatile Pheromones}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.8},
  URN =		{urn:nbn:de:0030-drops-191343},
  doi =		{10.4230/LIPIcs.DISC.2023.8},
  annote =	{Keywords: Mobile Agents, Exploration, Search, Treasure Hunt, Pheromone, Evaporation}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.9
Space-Optimal Naming in Population Protocols

Authors: Janna Burman, Joffroy Beauquier, and Devan Sohier

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
The distributed naming problem, assigning unique names to the nodes in a distributed system, is a fundamental task. This problem is nontrivial, especially when the amount of memory available for the task is low, and when requirements for fault-tolerance are added. The considered distributed communication model is population protocols. In this model, a priori anonymous and indistinguishable mobile nodes (called agents), communicate in pairs and in an asynchronous manner (according to a fairness condition). Fault-tolerance is addressed through self-stabilization, in terms of arbitrary initialization of agents. This work comprises a comprehensive study of the necessary and sufficient state space conditions for naming. The problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is presented.
Cite as

Janna Burman, Joffroy Beauquier, and Devan Sohier. Space-Optimal Naming in Population Protocols. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{burman_et_al:LIPIcs.DISC.2019.9,
  author =	{Burman, Janna and Beauquier, Joffroy and Sohier, Devan},
  title =	{{Space-Optimal Naming in Population Protocols}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.9},
  URN =		{urn:nbn:de:0030-drops-113161},
  doi =		{10.4230/LIPIcs.DISC.2019.9},
  annote =	{Keywords: networks of passively mobile agents, population protocols, deterministic naming, self-stabilization, exact space complexity, tight lower bounds, global and weak fairness}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.20
Beeping a Deterministic Time-Optimal Leader Election

Authors: Fabien Dufoulon, Janna Burman, and Joffroy Beauquier

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the leader election problem with an asymptotically optimal round complexity of O(D + log n), for a network of unknown size n and unknown diameter D (but with unique identifiers). Contrary to the best previously known algorithms in the same setting, the proposed one is deterministic. The techniques we introduce give a new insight as to how local constraints on the exchangeable messages can result in efficient algorithms, when dealing with the beeping model. Using this deterministic leader election algorithm, we obtain a randomized leader election algorithm for anonymous networks with an asymptotically optimal round complexity of O(D + log n) w.h.p. In previous works this complexity was obtained in expectation only. Moreover, using deterministic leader election, we obtain efficient algorithms for symmetry-breaking and communication procedures: O(log n) time MIS and 5-coloring for tree networks (which is time-optimal), as well as k-source multi-broadcast for general graphs in O(min(k,log n) * D + k log{(n M)/k}) rounds (for messages in {1,..., M}). This latter result improves on previous solutions when the number of sources k is sublogarithmic (k = o(log n)).
Cite as

Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. Beeping a Deterministic Time-Optimal Leader Election. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.DISC.2018.20,
  author =	{Dufoulon, Fabien and Burman, Janna and Beauquier, Joffroy},
  title =	{{Beeping a Deterministic Time-Optimal Leader Election}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.20},
  URN =		{urn:nbn:de:0030-drops-98090},
  doi =		{10.4230/LIPIcs.DISC.2018.20},
  annote =	{Keywords: distributed algorithms, leader election, beeping model, time complexity, deterministic algorithms, wireless networks}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.13
Time and Space Optimal Counting in Population Protocols

Authors: James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized. This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents. First, assuming probabilistic fairness, we present a "non-guessing" time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in big-omega (2^n) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains).
Cite as

James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and Space Optimal Counting in Population Protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.OPODIS.2016.13,
  author =	{Aspnes, James and Beauquier, Joffroy and Burman, Janna and Sohier, Devan},
  title =	{{Time and Space Optimal Counting in Population Protocols}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.13},
  URN =		{urn:nbn:de:0030-drops-70828},
  doi =		{10.4230/LIPIcs.OPODIS.2016.13},
  annote =	{Keywords: networks of passively mobile agents/sensors, population protocols, counting, anonymous non-initialized agents, time and space complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.21
The Benefits of Entropy in Population Protocols

Authors: Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
A distributed computing system can be viewed as the result of the interplay between a distributed algorithm specifying the effects of a local event (e.g. reception of a message), and an adversary choosing the interleaving (schedule) of these events in the execution. In the context of large networks of mobile pairwise interacting agents (population protocols), the adversary models the mobility of the agents by choosing the successive pairs of interacting agents. For some problems, assuming that the adversary selects the schedule according to some probability distribution greatly helps to devise (almost) correct solutions. But how much randomness is really necessary? To what extent does a problem admit implementations that are robust against a "not so random" schedule? This paper takes a first step in addressing this question by borrowing the concept of T-randomness, 0 <= T <= 1, from algorithmic information theory. Roughly speaking, the value T fixes the entropy rate of the considered schedules. For instance, the case T = 1 corresponds, in a specific sense, to schedules in which the pairs of interacting agents are chosen independently and uniformly (perfect randomness). The holy grail question can then be precisely stated as determining the optimal entropy rate to solve a given problem. We first show that perfect randomness is never required. Precisely, if a finite-state algorithm solves a problem with 1-randomness, then this algorithm still solves the same problem with T-randomness for some T < 1. Second, we illustrate how to compute bounds on the optimal entropy rate of a specific problem, namely the leader election problem.
Cite as

Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui. The Benefits of Entropy in Population Protocols. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{beauquier_et_al:LIPIcs.OPODIS.2015.21,
  author =	{Beauquier, Joffroy and Blanchard, Peva and Burman, Janna and Guerraoui, Rachid},
  title =	{{The Benefits of Entropy in Population Protocols}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.21},
  URN =		{urn:nbn:de:0030-drops-66128},
  doi =		{10.4230/LIPIcs.OPODIS.2015.21},
  annote =	{Keywords: algorithmic randomness, entropy, leader election, distributed computing, scheduler, population protocols}
}
Document
DOI: 10.4230/DagSemRep.290
Self-Stabilization (Dagstuhl Seminar 00431)

Authors: Anish Arora, Joffroy Beauquier, Shlomi Dolev, Ted Herman, and Willem-Paul de Roever

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Anish Arora, Joffroy Beauquier, Shlomi Dolev, Ted Herman, and Willem-Paul de Roever. Self-Stabilization (Dagstuhl Seminar 00431). Dagstuhl Seminar Report 290, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{arora_et_al:DagSemRep.290,
  author =	{Arora, Anish and Beauquier, Joffroy and Dolev, Shlomi and Herman, Ted and de Roever, Willem-Paul},
  title =	{{Self-Stabilization (Dagstuhl Seminar 00431)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{290},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.290},
  URN =		{urn:nbn:de:0030-drops-151744},
  doi =		{10.4230/DagSemRep.290},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact