DROPS

Volume

LIPIcs, Volume 157

10th International Conference on Fun with Algorithms (FUN 2021)

FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy

Editors: Martin Farach-Colton, Giuseppe Prencipe, and Ryuhei Uehara

Volume

LIPIcs, Volume 100

9th International Conference on Fun with Algorithms (FUN 2018)

FUN 2018, June 13-15, 2018, La Maddalena, Italy

Editors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe

Document

DOI: 10.4230/LIPIcs.FUN.2026.40

An ASP-Completeness Framework for Dynasty Puzzles

Authors: Kosuke Susukita

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

A certain class of pencil-and-paper puzzles shares common rules: given a grid, certain cells must be shaded such that i) no two shaded cells are orthogonally adjacent, and ii) all unshaded cells are orthogonally connected. Such puzzles are sometimes referred to as "dynasty puzzles" within parts of the online puzzle community. We introduce a framework for proving the ASP-completeness (i.e., NP-complete under parsimonious reductions) of various dynasty puzzles. We apply this framework to seven specific dynasty puzzles - Akichiwake, Aquapelago, Ayeheya, Guide Arrow, Heyawake, Hitori, and Kurodoko. As a consequence, for given k solutions of any of these puzzles, deciding whether a distinct solution exists is NP-complete, and counting the number of solutions is #P-complete. Our results strengthen the known result of ASP-completeness for Heyawake and establish the ASP-completeness of the other six puzzles. The main idea is to reconstruct the reduction from the Tree-Residue Vertex-Breaking Problem (TRVB) to the Hamiltonian Cycle Problem introduced by MIT Hardness Group (2024). In our framework, the connectivity of the unshaded cells ensures the connectivity of the shaded cells, allowing the shaded cells to simulate TRVB, which is also an alternative representation of the Hamiltonian cycles under certain conditions.

Cite as

Kosuke Susukita. An ASP-Completeness Framework for Dynasty Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{susukita:LIPIcs.FUN.2026.40,
  author =	{Susukita, Kosuke},
  title =	{{An ASP-Completeness Framework for Dynasty Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.40},
  URN =		{urn:nbn:de:0030-drops-257596},
  doi =		{10.4230/LIPIcs.FUN.2026.40},
  annote =	{Keywords: ASP-completeness, pencil-and-paper puzzles, dynasty puzzles, Hitori, Kurodoko, Hamiltonian cycle, Tree-Residue Vertex-Breaking}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.18

Optimal Deterministic Rendezvous in Labeled Lines

Authors: Yann Bourreau, Ananth Narayanan, and Alexandre Nolin

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

In a rendezvous task, a set of mobile agents initially dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with 2 initially asleep agents, without communication, and a synchronous notion of time. Each node on the line is labeled with a unique positive integer. The initial distance between the two agents is denoted by D. Time is divided into rounds and measured from the moment an agent first wakes up. We denote by τ the delay between the two agents' wake up times. If awake in a given round T, an agent at a node v has three options: stay at the node v, take port 0, or take port 1. If it decides to stay, the agent will still be at node v in round T+1. Otherwise, it will be at one of the two neighbors of v on the infinite line, depending on the port it chose. The agents achieve rendezvous in T rounds if they are at the same node in round T. We aim for a deterministic algorithm for this problem. The problem was recently considered by Miller and Pelc [Distributed Computing, 2025]. With 𝓁_{max} the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in o(D log^* 𝓁_{max}) rounds. The lower bound follows from a connection with the LOCAL model of distributed computing, and holds even if the agents are guaranteed simultaneous wake-up (τ = 0) and are told their initial distance D. Miller and Pelc also gave an algorithm of optimal matching complexity O(D log^* 𝓁_{max}) when the agents know D, but only obtained the higher bound of O(D² (log^* 𝓁_{max})³) when D is unknown to the agents. In this paper, we improve this second complexity to a tight O(D log^* 𝓁_{max}), closing the gap between the best known lower and upper bounds. In fact, our algorithm achieves rendezvous in O(D log^* 𝓁_{min}) rounds, where 𝓁_{min} is the smallest label within distance O(D) of the two starting positions. We obtain this result by having the agents compute sparse subsets of the nodes to gather at (formally, ruling sets over the line), as well as some general observations about the setting of rendezvous on labeled graphs.

Cite as

Yann Bourreau, Ananth Narayanan, and Alexandre Nolin. Optimal Deterministic Rendezvous in Labeled Lines. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bourreau_et_al:LIPIcs.STACS.2026.18,
  author =	{Bourreau, Yann and Narayanan, Ananth and Nolin, Alexandre},
  title =	{{Optimal Deterministic Rendezvous in Labeled Lines}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.18},
  URN =		{urn:nbn:de:0030-drops-255071},
  doi =		{10.4230/LIPIcs.STACS.2026.18},
  annote =	{Keywords: mobile agents, rendezvous, ruling set, deterministic algorithms, labeled line}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.32

Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Authors: Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo

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

Abstract

Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. They analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the φ-free graphs, a class that includes every graph with maximum degree at most three and every cactus.

Cite as

Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo. Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.OPODIS.2025.32,
  author =	{Takahashi, Shota and Kanaya, Haruki and Hiraoka, Shoma and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{32:1--32:15},
  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.32},
  URN =		{urn:nbn:de:0030-drops-252052},
  doi =		{10.4230/LIPIcs.OPODIS.2025.32},
  annote =	{Keywords: mobile agents, recolorable graphs, graph exploration}
}

Document

DOI: 10.4230/LITES.10.2.2

Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks

Authors: Marion Sudvarg, Christopher Gill, and Sanjoy Baruah

Published in: LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2

Abstract

Elastic scheduling provides a framework under which the utilizations of recurrent tasks are reduced by increasing their periods in response to system overload. The original elastic scheduling model was proposed by Buttazzo et al. in 1998 for implicit-deadline tasks on a uniprocessor and decreases task utilizations to satisfy a schedulable utilization bound. In 2019, Orr and Baruah extended the framework to multiprocessor scheduling of implicit-deadline tasks. In this paper, we propose, analyze, and evaluate new elastic scheduling algorithms for several of the scheduling policies considered in these prior works. In particular, (i) we evaluate an algorithm that we proposed as a short note in the Real-Time Systems journal and demonstrate that it allows for faster admission control than the algorithm of Buttazzo et al. when applied to uniprocessor and fluid scheduling. (ii) We also present faster elastic scheduling algorithms for partitioned EDF scheduling. Finally, (iii) we provide polynomial-time exact elastic scheduling algorithms for global EDF and global RM.

Cite as

Marion Sudvarg, Christopher Gill, and Sanjoy Baruah. Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks. In LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2, pp. 2:1-2:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sudvarg_et_al:LITES.10.2.2,
  author =	{Sudvarg, Marion and Gill, Christopher and Baruah, Sanjoy},
  title =	{{Improved Elastic Scheduling Algorithms for Implicit-Deadline Tasks}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{2:1--2:36},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.2.2},
  URN =		{urn:nbn:de:0030-drops-252346},
  doi =		{10.4230/LITES.10.2.2},
  annote =	{Keywords: real-time systems, elastic scheduling, scheduling algorithms}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2025.4

How Pinball Wizards Simulate a Turing Machine

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract

We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point. By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete - even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed - a so-called ray particle - can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete.

Cite as

Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer. How Pinball Wizards Simulate a Turing Machine. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adejoh_et_al:LIPIcs.FSTTCS.2025.4,
  author =	{Adejoh, Rosemary U. and Jakoby, Andreas and Mohanty, Sneha and Schindelhauer, Christian},
  title =	{{How Pinball Wizards Simulate a Turing Machine}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.4},
  URN =		{urn:nbn:de:0030-drops-250832},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.4},
  annote =	{Keywords: Pinball Wizard problem, Halting problem, Turing-complete}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.30

Team Formation and Applications

Authors: Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld

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

Abstract

A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size σ, where σ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.

Cite as

Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld. Team Formation and Applications. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2025.30,
  author =	{Emek, Yuval and Kutten, Shay and Rafael, Ido and Taubenfeld, Gadi},
  title =	{{Team Formation and Applications}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{30:1--30:25},
  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.30},
  URN =		{urn:nbn:de:0030-drops-248474},
  doi =		{10.4230/LIPIcs.DISC.2025.30},
  annote =	{Keywords: asynchronous message-passing, complete communication graph, initial failures, leader election, matching}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.33

Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

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

Abstract

Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.

Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2025.56

Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers

Authors: Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro

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

Abstract

The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, aka perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the LUMI model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities). However, we prove that, to be solvable under LUMI, the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots. We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

Cite as

Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro. Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 56:1-56:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.DISC.2025.56,
  author =	{Feletti, Caterina and Flocchini, Paola and Pattanayak, Debasish and Prencipe, Giuseppe and Santoro, Nicola},
  title =	{{Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{56:1--56:7},
  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.56},
  URN =		{urn:nbn:de:0030-drops-248724},
  doi =		{10.4230/LIPIcs.DISC.2025.56},
  annote =	{Keywords: Luminous Robots, Sequence of Patterns, Pattern Formation, Sequential Scheduler}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2025.57

Brief Announcement: The Virtue of Self-Consistency

Authors: Fabian Frei and Koichi Wada

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

Abstract

We show that self-consistency can be a crucial property for autonomous mobile robots. Specifically, we consider the task of gathering three robots, placed adversarially in distinct locations in the Euclidean plane, in a single point. We assume the natural scheduler RoundRobin, which activates the robots in turns. An activated robot perceives all robot locations in an adversarially scaled, rotated, and mirrored Cartesian coordinate system with itself at the origin and then moves wherever it wants. We show that this task cannot be solved in the default robot model (without any consistency guarantees and no multiplicity detection) but becomes feasible if we assume self-consistency (i.e., no changes between the different activations of the same robot) of either the unit length (i.e., no scaling) or the compass (i.e., no rotating) by providing explicit algorithms.

Cite as

Fabian Frei and Koichi Wada. Brief Announcement: The Virtue of Self-Consistency. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 57:1-57:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.DISC.2025.57,
  author =	{Frei, Fabian and Wada, Koichi},
  title =	{{Brief Announcement: The Virtue of Self-Consistency}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{57:1--57:7},
  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.57},
  URN =		{urn:nbn:de:0030-drops-248737},
  doi =		{10.4230/LIPIcs.DISC.2025.57},
  annote =	{Keywords: Autonomous Mobile Robots, Distinct Gathering, Round Robin, Disorientation, Self-Consistency}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.16

Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

Authors: Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal

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

Abstract

In this paper, we investigate the following question: "How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves maliciously, under the control of an adversary?" This malicious node is termed as "Byzantine black hole (BBH)" and at any given round it may choose to destroy all visiting agents, or none of them. While investigating this question, we found out that this subtle power turns out to drastically undermine even basic exploration strategies which have been proposed in the context of a classical, always active, black hole. We study this perpetual exploration problem in the presence of at most one BBH, without initial knowledge of the network size. Since the underlying graph may be 1-connected, perpetual exploration of the entire graph may be infeasible. Accordingly, we define two variants of the problem, termed as PerpExploration-BBH and PerpExploration-BBH-Home. In the former, the agents are tasked to perform perpetual exploration of at least one component, obtained after the exclusion of the BBH. In the latter, the agents are tasked to perform perpetual exploration of the component which contains the home node, where agents are initially co-located. Naturally, PerpExploration-BBH-Home is a special case of PerpExploration-BBH. The mobile agents are controlled by a synchronous scheduler, and they communicate via face-to-face model of communication. The main objective in this paper is to determine the minimum number of agents necessary and sufficient to solve these problems. We first consider the problems in acyclic networks, and we obtain optimal algorithms that solve PerpExploration-BBH with 4 agents, and PerpExploration-BBH-Home with 6 agents in trees. The lower bounds hold even in path graphs. In general graphs, we give a non-trivial lower bound of 2Δ-1 agents for PerpExploration-BBH, and an upper bound of 3Δ+3 agents for PerpExploration-BBH-Home. To the best of our knowledge, this is the first paper that studies a variant of a black hole in arbitrary networks, without initial topological knowledge about the network.

Cite as

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal. Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.DISC.2025.16,
  author =	{Bhattacharya, Adri and Goswami, Pritam and Bampas, Evangelos and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{16:1--16:17},
  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.16},
  URN =		{urn:nbn:de:0030-drops-248333},
  doi =		{10.4230/LIPIcs.DISC.2025.16},
  annote =	{Keywords: mobile agents, perpetual exploration, malicious host, Byzantine black hole}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.68

Graph Exploration: The Impact of a Distance Constraint

Authors: Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

A mobile agent, starting from a node s of a simple undirected connected graph G = (V,E), has to explore all nodes and edges of G using the minimum number of edge traversals. To do so, the agent uses a deterministic algorithm that allows it to gain information on G as it traverses its edges. During its exploration, the agent must always respect the constraint of knowing a path of length at most D to go back to node s. The upper bound D is fixed as being equal to (1+α)r, where r is the eccentricity of node s (i.e., the maximum distance from s to any other node) and α is any positive real constant. This task has been introduced by Duncan et al. [Christian A. Duncan et al., 2006] and is known as distance-constrained exploration. The penalty of an exploration algorithm running in G is the number of edge traversals made by the agent in excess of |E|. In [Petrisor Panaite and Andrzej Pelc, 1999], Panaite and Pelc gave an algorithm for solving exploration without any constraint on the moves that is guaranteed to work in every graph G with a (small) penalty in 𝒪(|V|). Hence, a natural question is whether we can obtain a distance-constrained exploration algorithm with the same guarantee as well. In this paper, we provide a negative answer to this question. We also observe that an algorithm working in every graph G with a linear penalty in |V| cannot be obtained for the task of fuel-constrained exploration, another variant studied in the literature. This solves an open problem posed by Duncan et al. in [Christian A. Duncan et al., 2006] and shows a fundamental separation with the task of exploration without constraint on the moves.

Cite as

Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel. Graph Exploration: The Impact of a Distance Constraint. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{devismes_et_al:LIPIcs.ICALP.2025.68,
  author =	{Devismes, St\'{e}phane and Dieudonn\'{e}, Yoann and Labourel, Arnaud},
  title =	{{Graph Exploration: The Impact of a Distance Constraint}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{68:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.68},
  URN =		{urn:nbn:de:0030-drops-234452},
  doi =		{10.4230/LIPIcs.ICALP.2025.68},
  annote =	{Keywords: exploration, graph, mobile agent}
}

Document

DOI: 10.4230/LIPIcs.SAND.2025.10

Fault Detection and Identification by Autonomous Mobile Robots

Authors: Stefano Clemente and Caterina Feletti

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

Abstract

The Look-Compute-Move model (LCM) is adopted to study swarms of mobile robots that have to solve a given problem. Robots are generally assumed to be autonomous, indistinguishable, anonymous, homogeneous and to move on the Euclidean plane. Different LCM sub-models have been theorized to study different settings and their computational power. Notably, the literature has focused on four base models (i.e., OBLOT, FSTA, FCOM, LUMI) that differ in memory and communication capabilities, and in different synchronization modes (e.g., fully synchronous FSYNCH, semi-synchronous SSYNCH). In this paper, we consider fault-prone models where robots can suffer from crash faults: each robot may irremediably stop working after an unpredictable time. We study the general Fault Detection (FD) problem which is solved by a swarm if it correctly detects whether a faulty robot exists in the swarm. The Fault Identification (FI) problem additionally requires identifying which robots are faulty. We consider 12 LCM sub-models (OBLOT, FSTA, FCOM, LUMI, combined with FSYNCH, SSYNCH, and the round-robin RROBIN) and we study the (im)possibility of designing reliable procedures to solve FD or FI. In particular, we propose three distributed algorithms so that a swarm can collectively solve FD under the models LUMI^FSYNCH, FCOM^FSYNCH, and LUMI^RROBIN.

Cite as

Stefano Clemente and Caterina Feletti. Fault Detection and Identification by Autonomous Mobile Robots. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.SAND.2025.10,
  author =	{Clemente, Stefano and Feletti, Caterina},
  title =	{{Fault Detection and Identification by Autonomous Mobile Robots}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{10:1--10:20},
  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.10},
  URN =		{urn:nbn:de:0030-drops-230639},
  doi =		{10.4230/LIPIcs.SAND.2025.10},
  annote =	{Keywords: Autonomous mobile robots, Faulty robots, Look-Compute-Move, Fault detection, Fault identification, Round-robin}
}

Document

DOI: 10.4230/LIPIcs.SAND.2025.13

Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents

Authors: Jion Hirose, Ryota Eguchi, and Yuichi Sudo

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

Abstract

We study the Byzantine gathering problem involving k mobile agents with unique identifiers (IDs), f of which are Byzantine. These agents start the execution of a common algorithm from (possibly different) nodes in an n-node network, potentially starting at different times. Once started, the agents operate in synchronous rounds. We focus on weakly Byzantine environments, where Byzantine agents can behave arbitrarily but cannot falsify their IDs. The goal is for all non-Byzantine agents to eventually terminate at a single node simultaneously. In this paper, we first prove two impossibility results: (1) for any number of non-Byzantine agents, no algorithm can solve this problem without global knowledge of the network size or the number of agents, and (2) no self-stabilizing algorithm exists if k ≤ 2f even with n, k, f, and the length Λ_g of the largest ID among IDs of non-Byzantine agents, where the self-stabilizing algorithm enables agents to gather starting from arbitrary (inconsistent) initial states. Next, based on these results, we introduce a perpetual gathering problem and propose a self-stabilizing algorithm for this problem. This problem requires that all non-Byzantine agents always be co-located from a certain time onwards. If the agents know Λ_g and upper bounds N, K, F on n, k, f, the proposed algorithm works in O(K⋅ F⋅ Λ_g⋅ X(N)) rounds, where X(n) is the time required to visit all nodes in a n-nodes network. Our results indicate that while no algorithm can solve the original self-stabilizing gathering problem for any k and f even with exact global knowledge of the network size and the number of agents, the self-stabilizing perpetual gathering problem can always be solved with just upper bounds on this knowledge.

Cite as

Jion Hirose, Ryota Eguchi, and Yuichi Sudo. Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirose_et_al:LIPIcs.SAND.2025.13,
  author =	{Hirose, Jion and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{13:1--13:18},
  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.13},
  URN =		{urn:nbn:de:0030-drops-230662},
  doi =		{10.4230/LIPIcs.SAND.2025.13},
  annote =	{Keywords: Distributed algorithms, Byzantine environments, Gathering}
}

86 Search Results for "Prencipe, Giuseppe"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message