3 Search Results for "Sohier, Devan"

Document
DOI: 10.4230/LIPIcs.OPODIS.2024.33
Self-Stabilizing Fully Adaptive Maximal Matching

Authors: Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
A self-stabilizing randomized algorithm for mending maximal matching (MM) in synchronous networks is presented. Starting from a legal MM configuration and assuming that the network undergoes k faults or topology changes (that may occur in multiple batches), the algorithm is guaranteed to stabilize back to a legal MM configuration in time O(log k) in expectation and with high probability (in k), using constant size messages. The algorithm is simple to implement and is uniform in the sense that it does not assume unique identifiers, nor does it assume any global knowledge of the communication graph including its size. It relies on a generic probabilistic phase synchronization technique that may be useful for other self-stabilizing problems. The algorithm compares favorably with the existing self-stabilizing MM algorithms in terms of the dependence of its run-time on k, a.k.a. fully adaptive run-time. In fact, this dependence is asymptotically optimal for uniform algorithms that use constant size messages.
Cite as

Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten. Self-Stabilizing Fully Adaptive Maximal Matching. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bitton_et_al:LIPIcs.OPODIS.2024.33,
  author =	{Bitton, Shimon and Emek, Yuval and Izumi, Taisuke and Kutten, Shay},
  title =	{{Self-Stabilizing Fully Adaptive Maximal Matching}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.33},
  URN =		{urn:nbn:de:0030-drops-225698},
  doi =		{10.4230/LIPIcs.OPODIS.2024.33},
  annote =	{Keywords: self-stabilization, maximal matching, fully adaptive run-time, dynamic graphs}
}
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.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}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2019
  • 1 2017

  • Refine by Author
  • 2 Beauquier, Joffroy
  • 2 Burman, Janna
  • 2 Sohier, Devan
  • 1 Aspnes, James
  • 1 Bitton, Shimon
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Computer systems organization → Fault-tolerant network topologies
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 2 population protocols
  • 2 self-stabilization
  • 1 anonymous non-initialized agents
  • 1 counting
  • 1 deterministic naming
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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