13 Search Results for "Daymude, Joshua J."

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.21
Solving Tasks with Fewer Registers Than Processes

Authors: Eli Gafni, Giuliano Losa, Michel Raynal, and Gadi Taubenfeld

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
This paper studies distributed-computing tasks through the lens of space complexity in the read/write wait-free model, defined as the number of multi-reader-multi-writer atomic read/write registers needed to solve a task using a wait-free algorithm. Surprisingly, even though the read/write wait-free model is at the foundation of distributed computing, previous work on space complexity has focused on synchronization primitives stronger than read/write registers or on weaker progress conditions. The paper reveals that the read/write wait-free model offers a rich space-complexity landscape: (1) assuming non-anonymous processes, it shows that there is an infinite hierarchy of tasks of increasing space complexity; (2) it shows that space complexity separates anonymous from non-anonymous memory; (3) regardless of process or register anonymity, it exhibits a task of space complexity two, which is the minimal non-trivial space complexity; (4) finally, it shows that subcases of the adopt-commit task have different space complexity in non-anonymous memory under bounded wait-freedom.
Cite as

Eli Gafni, Giuliano Losa, Michel Raynal, and Gadi Taubenfeld. Solving Tasks with Fewer Registers Than Processes. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gafni_et_al:LIPIcs.OPODIS.2025.21,
  author =	{Gafni, Eli and Losa, Giuliano and Raynal, Michel and Taubenfeld, Gadi},
  title =	{{Solving Tasks with Fewer Registers Than Processes}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.21},
  URN =		{urn:nbn:de:0030-drops-251947},
  doi =		{10.4230/LIPIcs.OPODIS.2025.21},
  annote =	{Keywords: Asynchrony, Read/write registers, Wait-freedom, Tasks, Covering argument, Lower bound, Space complexity, Anonymous Processes, Anonymous Memory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.7
On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits

Authors: Matthias Artmann, Andreas Padalkin, and Christian Scheideler

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the particle structure. Shape formation problems, where the particles have to reorganize themselves into a desired shape using basic movement abilities, are particularly interesting. In the related shape containment problem, the particles are given the description of a shape S and have to find maximally scaled representations of S within the initial configuration, without movements. For example, if S is a triangle, they have to identify the largest subsets of particles that already form a triangle. While the shape formation problem is being studied extensively, no attention has been given to the shape containment problem, which may have additional uses besides shape formation, such as detecting structural flaws. In this paper, we consider the shape containment problem within the geometric amoebot model for programmable matter, using its reconfigurable circuit extension to enable the instantaneous transmission of primitive signals on connected subsets of particles. We first prove a lower runtime bound of Ω (√n) synchronous rounds for the general problem, where n is the number of particles. Then, we present simple and efficient primitives for identifying subsets that form the desired shape. Using these primitives, we construct a large class of shapes which we call snowflakes. This class contains, among others, all shapes composed of parallelograms and hexagons, and the class of star convex shapes. Let k be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within 𝒪 (log² k) rounds. If it is a snowflake but not star convex, we solve it within 𝒪 (√n log n) rounds.
Cite as

Matthias Artmann, Andreas Padalkin, and Christian Scheideler. On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artmann_et_al:LIPIcs.DISC.2025.7,
  author =	{Artmann, Matthias and Padalkin, Andreas and Scheideler, Christian},
  title =	{{On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.7},
  URN =		{urn:nbn:de:0030-drops-248240},
  doi =		{10.4230/LIPIcs.DISC.2025.7},
  annote =	{Keywords: Programmable matter, amoebot model, reconfigurable circuits, shape containment}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.14
Energy-Efficient Maximal Independent Sets in Radio Networks

Authors: Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the radio network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model - with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1) CD model: We present a randomized distributed MIS algorithm with energy complexity O(log n), round complexity O(log² n), and failure probability 1 / poly(n), where n is the network size. We show that our energy complexity is optimal by showing a matching Ω(log n) lower bound. 2) no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity O(log²n log log n), round complexity O(log³ n log Δ), and failure probability 1 / poly(n). The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of O(log³ n) of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.
Cite as

Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-Efficient Maximal Independent Sets in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banasik_et_al:LIPIcs.DISC.2025.14,
  author =	{Banasik, Dominick and Dani, Varsha and Dufoulon, Fabien and Gupta, Aayush and Hayes, Thomas P. and Pandurangan, Gopal},
  title =	{{Energy-Efficient Maximal Independent Sets in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.14},
  URN =		{urn:nbn:de:0030-drops-248311},
  doi =		{10.4230/LIPIcs.DISC.2025.14},
  annote =	{Keywords: Distributed Computing, Energy Complexity, Sleeping Model, Radio Networks, Maximal Independent Set}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.10
Amnesiac Flooding: Easy to Break, Hard to Escape

Authors: Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/ STACS'20/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults? In this paper we make progress on both of these fronts. Under a reasonable restriction (obliviousness to message content) additional to the fault-free synchronous model, we prove that Amnesiac Flooding is the only strictly stateless deterministic protocol that can achieve terminating broadcast. We achieve this by identifying four natural properties of a terminating broadcast protocol that Amnesiac Flooding uniquely satisfies. In contrast, we prove that even minor relaxations of any of these four criteria allow the construction of other terminating broadcast protocols. On the other hand, we prove that Amnesiac Flooding can become non-terminating or non-broadcasting, even if we allow just one node to drop a single message on a single edge in a single round. As a tool for proving this, we focus on the set of all configurations of transmissions between nodes in the network, and obtain a dichotomy characterizing the configurations, starting from which, Amnesiac Flooding terminates. Additionally, we characterise the structure of sets of Byzantine agents capable of forcing non-termination or non-broadcast of the protocol on arbitrary networks.
Cite as

Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan. Amnesiac Flooding: Easy to Break, Hard to Escape. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austin_et_al:LIPIcs.DISC.2025.10,
  author =	{Austin, Henry and Gadouleau, Maximilien and Mertzios, George B. and Trehan, Amitabh},
  title =	{{Amnesiac Flooding: Easy to Break, Hard to Escape}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.10},
  URN =		{urn:nbn:de:0030-drops-248273},
  doi =		{10.4230/LIPIcs.DISC.2025.10},
  annote =	{Keywords: Amnesiac flooding, Terminating protocol, Algorithm state, Stateless protocol, Flooding algorithm, Network algorithms, Graph theory, Termination, Communication, Broadcast}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.75
Temporal Graph Realization with Bounded Stretch

Authors: George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time steps, where Δ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are "stretched", compared to their physical distances, i.e. their distances in the underlying static (non-temporal) graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be stretched once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple polynomial-time algorithm (the radius-algorithm) which always guarantees an approximation strictly smaller than Δ, and which also computes the optimum stretch in some cases. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most k edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to k.
Cite as

George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Temporal Graph Realization with Bounded Stretch. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2025.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Morawietz, Nils and Spirakis, Paul G.},
  title =	{{Temporal Graph Realization with Bounded Stretch}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{75:1--75:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.75},
  URN =		{urn:nbn:de:0030-drops-241829},
  doi =		{10.4230/LIPIcs.MFCS.2025.75},
  annote =	{Keywords: Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, stretch}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.81
AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition)

Authors: Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present AmoebotSim 2.0, a simulation environment for the geometric amoebot model of programmable matter that supports the reconfigurable circuit and joint movement extensions of the model. In the geometric amoebot model, we consider systems of simple computational entities called amoebots in a regular triangular grid environment. We are interested in distributed algorithms that solve coordination and shape formation problems. The reconfigurable circuit and joint movement extensions of the model allow the amoebots to communicate over greater distances and perform more complex movements, overcoming some limitations of the original model. AmoebotSim 2.0 is an open-source simulation environment that supports these extensions and provides a rich graphical interface, flexible simulation features, an extensive API, and comprehensive documentation.
Cite as

Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler. AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 81:1-81:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artmann_et_al:LIPIcs.SoCG.2025.81,
  author =	{Artmann, Matthias and Maurer, Tobias and Padalkin, Andreas and Warner, Daniel and Scheideler, Christian},
  title =	{{AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{81:1--81:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.81},
  URN =		{urn:nbn:de:0030-drops-232338},
  doi =		{10.4230/LIPIcs.SoCG.2025.81},
  annote =	{Keywords: Programmable matter, amoebot model, reconfigurable circuits, joint movements, simulator}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.15
On the Runtime of Local Mutual Exclusion for Anonymous Dynamic Networks

Authors: Anya Chaturvedi, Joshua J. Daymude, and Andréa W. Richa

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Algorithms for mutual exclusion aim to isolate potentially concurrent accesses to the same shared resources. Motivated by distributed computing research on programmable matter and population protocols where interactions among entities are often assumed to be isolated, Daymude, Richa, and Scheideler (SAND`22) introduced a variant of the local mutual exclusion problem that applies to arbitrary dynamic networks: each node, on issuing a lock request, must acquire exclusive locks on itself and all its persistent neighbors, i.e., the neighbors that remain connected to it over the duration of the lock request. Assuming adversarial edge dynamics, semi-synchronous or asynchronous concurrency, and anonymous nodes communicating via message passing, their randomized algorithm achieves mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1). However, they did not analyze their algorithm’s runtime. In this paper, we prove that any node will successfully lock itself and its persistent neighbors within 𝒪(nΔ³) open rounds of its lock request in expectation, where n is the number of nodes in the dynamic network, Δ is the maximum degree of the dynamic network, rounds are normalized to the execution time of the "slowest" node, and "closed" rounds when some persistent neighbors are already locked by another node are ignored (i.e., only "open" rounds are considered).
Cite as

Anya Chaturvedi, Joshua J. Daymude, and Andréa W. Richa. On the Runtime of Local Mutual Exclusion for Anonymous Dynamic Networks. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chaturvedi_et_al:LIPIcs.SAND.2025.15,
  author =	{Chaturvedi, Anya and Daymude, Joshua J. and Richa, Andr\'{e}a W.},
  title =	{{On the Runtime of Local Mutual Exclusion for Anonymous Dynamic Networks}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.15},
  URN =		{urn:nbn:de:0030-drops-230687},
  doi =		{10.4230/LIPIcs.SAND.2025.15},
  annote =	{Keywords: Mutual exclusion, dynamic networks, message passing, concurrency}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.45
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs

Authors: Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting.
Cite as

Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 45:1-45:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dou_et_al:LIPIcs.ITCS.2025.45,
  author =	{Dou, Jinfeng and G\"{o}tte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian},
  title =	{{Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{45:1--45:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.45},
  URN =		{urn:nbn:de:0030-drops-226734},
  doi =		{10.4230/LIPIcs.ITCS.2025.45},
  annote =	{Keywords: Distributed Graph Algorithms, Network Decomposition, Excluded Minor}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.35
Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast

Authors: Garrett Parzych and Joshua J. Daymude

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
Broadcast is a ubiquitous distributed computing problem that underpins many other system tasks. In static, connected networks, it was recently shown that broadcast is solvable without any node memory and only constant-size messages in worst-case asymptotically optimal time (Hussak and Trehan, PODC'19/STACS'20/DC'23). In the dynamic setting of adversarial topology changes, however, existing algorithms rely on identifiers, port labels, or polynomial memory to solve broadcast and compute functions over node inputs. We investigate space-efficient, terminating broadcast algorithms for anonymous, synchronous, 1-interval connected dynamic networks and introduce the first memory lower bounds in this setting. Specifically, we prove that broadcast with termination detection is impossible for idle-start algorithms (where only the broadcaster can initially send messages) and otherwise requires Ω(log n) memory per node, where n is the number of nodes in the network. Even if the termination condition is relaxed to stabilizing termination (eventually no additional messages are sent), we show that any idle-start algorithm must use ω(1) memory per node, separating the static and dynamic settings for anonymous broadcast. This lower bound is not far from optimal, as we present an algorithm that solves broadcast with stabilizing termination using 𝒪(log n) memory per node in worst-case asymptotically optimal time. In sum, these results reveal the necessity of non-constant memory for nontrivial terminating computation in anonymous dynamic networks.
Cite as

Garrett Parzych and Joshua J. Daymude. Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{parzych_et_al:LIPIcs.DISC.2024.35,
  author =	{Parzych, Garrett and Daymude, Joshua J.},
  title =	{{Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.35},
  URN =		{urn:nbn:de:0030-drops-212615},
  doi =		{10.4230/LIPIcs.DISC.2024.35},
  annote =	{Keywords: Dynamic networks, anonymity, broadcast, space complexity, lower bounds, termination detection, stabilizing termination}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.7
Energy-Constrained Programmable Matter Under Unfair Adversaries

Authors: Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Individual modules of programmable matter participate in their system’s collective behavior by expending energy to perform actions. However, not all modules may have access to the external energy source powering the system, necessitating a local and distributed strategy for supplying energy to modules. In this work, we present a general energy distribution framework for the canonical amoebot model of programmable matter that transforms energy-agnostic algorithms into energy-constrained ones with equivalent behavior and an 𝒪(n²)-round runtime overhead - even under an unfair adversary - provided the original algorithms satisfy certain conventions. We then prove that existing amoebot algorithms for leader election (ICDCN 2023) and shape formation (Distributed Computing, 2023) are compatible with this framework and show simulations of their energy-constrained counterparts, demonstrating how other unfair algorithms can be generalized to the energy-constrained setting with relatively little effort. Finally, we show that our energy distribution framework can be composed with the concurrency control framework for amoebot algorithms (Distributed Computing, 2023), allowing algorithm designers to focus on the simpler energy-agnostic, sequential setting but gain the general applicability of energy-constrained, asynchronous correctness.
Cite as

Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, and Joshua J. Daymude. Energy-Constrained Programmable Matter Under Unfair Adversaries. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{weber_et_al:LIPIcs.OPODIS.2023.7,
  author =	{Weber, Jamison W. and Chhabra, Tishya and Richa, Andr\'{e}a W. and Daymude, Joshua J.},
  title =	{{Energy-Constrained Programmable Matter Under Unfair Adversaries}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.7},
  URN =		{urn:nbn:de:0030-drops-194971},
  doi =		{10.4230/LIPIcs.OPODIS.2023.7},
  annote =	{Keywords: Programmable matter, amoebot model, energy distribution, concurrency}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.12
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Mutual exclusion is a classical problem in distributed computing that provides isolation among concurrent action executions that may require access to the same shared resources. Inspired by algorithmic research on distributed systems of weakly capable entities whose connections change over time, we address the local mutual exclusion problem that tasks each node with acquiring exclusive locks for itself and the maximal subset of its "persistent" neighbors that remain connected to it over the time interval of the lock request. Using the established time-varying graphs model to capture adversarial topological changes, we propose and rigorously analyze a local mutual exclusion algorithm for nodes that are anonymous and communicate via asynchronous message passing. The algorithm satisfies mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1) under both semi-synchronous and asynchronous concurrency. It requires 𝒪(Δ) memory per node and messages of size Θ(1), where Δ is the maximum number of connections per node. We conclude by describing how our algorithm can implement the pairwise interactions assumed by population protocols and the concurrency control operations assumed by the canonical amoebot model, demonstrating its utility in both passively and actively dynamic distributed systems.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.SAND.2022.12,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.12},
  URN =		{urn:nbn:de:0030-drops-159545},
  doi =		{10.4230/LIPIcs.SAND.2022.12},
  annote =	{Keywords: Mutual exclusion, dynamic networks, message passing, concurrency}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.20
The Canonical Amoebot Model: Algorithms and Concurrency Control

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The Canonical Amoebot Model: Algorithms and Concurrency Control. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.DISC.2021.20,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{The Canonical Amoebot Model: Algorithms and Concurrency Control}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.20},
  URN =		{urn:nbn:de:0030-drops-148227},
  doi =		{10.4230/LIPIcs.DISC.2021.20},
  annote =	{Keywords: Programmable matter, self-organization, distributed algorithms, concurrency}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.54
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems

Authors: Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.
Cite as

Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2019.54,
  author =	{Cannon, Sarah and Daymude, Joshua J. and G\"{o}kmen, Cem and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{54:1--54:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  URN =		{urn:nbn:de:0030-drops-112696},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  annote =	{Keywords: Markov chains, Programmable matter, Cluster expansion}
}
  • Refine by Type
  • 13 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 2 2024
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 6 Daymude, Joshua J.
  • 5 Richa, Andréa W.
  • 5 Scheideler, Christian
  • 2 Artmann, Matthias
  • 2 Mertzios, George B.
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs

  • Refine by Classification
  • 8 Theory of computation → Distributed algorithms
  • 5 Theory of computation → Self-organization
  • 3 Theory of computation → Concurrency
  • 3 Theory of computation → Distributed computing models
  • 2 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 5 Programmable matter
  • 4 concurrency
  • 3 amoebot model
  • 2 Mutual exclusion
  • 2 dynamic networks
  • 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