Search Results

Documents authored by Flocchini, Paola

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.28
On Asynchrony, Memory, and Communication: Separations and Landscapes

Authors: Paola Flocchini, Nicola Santoro, Yuichi Sudo, and Koichi Wada

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

Abstract
Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in Look-Compute-Move (LCM) cycles, has recently focused on better understanding how the computational power of robots depends on the interplay between their internal capabilities (i.e., persistent memory, communication), captured by the four standard computational models (OBLOT, LUMI, FSTA, and FCOM) and the conditions imposed by the external environment, controlling the activation of the robots and their synchronization of their activities, perceived and modeled as an adversarial scheduler. We consider a set of adversarial asynchronous schedulers ranging from the classical semi-synchronous (Ssynch) and fully asynchronous (Asynch) settings, including schedulers (emerging when studying the atomicity of the combination of operations in the LCM cycles) whose adversarial power is in between those two. We ask the question: what is the computational relationship between a model M₁ under adversarial scheduler K₁ (M₁(K₁)) and a model M₂ under scheduler K₂ (M₂(K₂))? For example, are the robots in M₁(K₁) more powerful (i.e., they can solve more problems) than those in M₂(K₂)? We answer all these questions by providing, through cross-model analysis, a complete characterization of the computational relationship between the power of the four models of robots under the considered asynchronous schedulers. In this process, we also provide qualified answers to several open questions, including the outstanding one on the proper dominance of Ssynch over Asynch in the case of unrestricted visibility.
Cite as

Paola Flocchini, Nicola Santoro, Yuichi Sudo, and Koichi Wada. On Asynchrony, Memory, and Communication: Separations and Landscapes. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{flocchini_et_al:LIPIcs.OPODIS.2023.28,
  author =	{Flocchini, Paola and Santoro, Nicola and Sudo, Yuichi and Wada, Koichi},
  title =	{{On Asynchrony, Memory, and Communication: Separations and Landscapes}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{28:1--28:23},
  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.28},
  URN =		{urn:nbn:de:0030-drops-195188},
  doi =		{10.4230/LIPIcs.OPODIS.2023.28},
  annote =	{Keywords: Look-Compute-Move, Oblivious mobile robots, Robots with lights, Memory versus Communication, Moving and Computing, Asynchrony}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.33
Black Hole Search in Dynamic Rings: The Scattered Case

Authors: Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro

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

Abstract
In this paper we investigate the problem of searching for a black hole in a dynamic graph by a set of scattered agents (i.e., the agents start from arbitrary locations of the graph). The black hole is a node that silently destroys any agent visiting it. This kind of malicious node nicely models network failures such as a crashed host or a virus that erases the visiting agents. The black hole search problem is solved when at least one agent survives, and it has the entire map of the graph with the location of the black hole. We consider the case in which the underlining graph is a dynamic 1-interval connected ring: a ring graph in which at each round at most one edge can be missing. We first show that the problem cannot be solved if the agents can only communicate by using a face-to-face mechanism: this holds for any set of agents of constant size, with respect to the size n of the ring. To circumvent this impossibility we consider agents equipped with movable pebbles that can be left on nodes as a form of communication with other agents. When pebbles are available, three agents can localize the black hole in O(n²) moves. We show that such a number of agents is optimal. We also show that the complexity is tight, that is Ω(n²) moves are required for any algorithm solving the problem with three agents, even with stronger communication mechanisms (e.g., a whiteboard on each node on which agents can write messages of unlimited size). To the best of our knowledge this is the first paper examining the problem of searching a black hole in a dynamic environment with scattered agents.
Cite as

Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Black Hole Search in Dynamic Rings: The Scattered Case. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.OPODIS.2023.33,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Prencipe, Giuseppe and Santoro, Nicola},
  title =	{{Black Hole Search in Dynamic Rings: The Scattered Case}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{33:1--33:18},
  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.33},
  URN =		{urn:nbn:de:0030-drops-195233},
  doi =		{10.4230/LIPIcs.OPODIS.2023.33},
  annote =	{Keywords: Black hole search, mobile agents, dynamic graph}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.22
Tight Bounds on Distributed Exploration of Temporal Graphs

Authors: Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs. We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.
Cite as

Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Tight Bounds on Distributed Exploration of Temporal Graphs. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gotoh_et_al:LIPIcs.OPODIS.2019.22,
  author =	{Gotoh, Tsuyoshi and Flocchini, Paola and Masuzawa, Toshimitsu and Santoro, Nicola},
  title =	{{Tight Bounds on Distributed Exploration of Temporal Graphs}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.22},
  URN =		{urn:nbn:de:0030-drops-118082},
  doi =		{10.4230/LIPIcs.OPODIS.2019.22},
  annote =	{Keywords: Distributed algorithm, Mobile agents, Exploration of dynamic networks, Arbitrary footprint}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.24
Oblivious Permutations on the Plane

Authors: Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.
Cite as

Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Oblivious Permutations on the Plane. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.OPODIS.2019.24,
  author =	{Das, Shantanu and Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamashita, Masafumi},
  title =	{{Oblivious Permutations on the Plane}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.24},
  URN =		{urn:nbn:de:0030-drops-118103},
  doi =		{10.4230/LIPIcs.OPODIS.2019.24},
  annote =	{Keywords: Distributed Algorithms, Mobile Robots, Fully synchronous, Oblivious, Permutations, Chirality, Sequence of configurations}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.25
On Memory, Communication, and Synchronous Schedulers When Moving and Computing

Authors: Paola Flocchini, Nicola Santoro, and Koichi Wada

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship. In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ? In this paper we address these questions, focusing on two sub-models of LUMI: FSTA, where the robots have a constant-size persistent memory but are silent; and FCOM, where the robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler Fsynch, while they are incomparable under the semi-synchronous scheduler Ssynch.
Cite as

Paola Flocchini, Nicola Santoro, and Koichi Wada. On Memory, Communication, and Synchronous Schedulers When Moving and Computing. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{flocchini_et_al:LIPIcs.OPODIS.2019.25,
  author =	{Flocchini, Paola and Santoro, Nicola and Wada, Koichi},
  title =	{{On Memory, Communication, and Synchronous Schedulers When Moving and Computing}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.25},
  URN =		{urn:nbn:de:0030-drops-118114},
  doi =		{10.4230/LIPIcs.OPODIS.2019.25},
  annote =	{Keywords: Look-Compute-Move, Oblivious mobile robots, Robots with lights, Memory versus Communication, Moving and Computing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.8
Gathering and Election by Mobile Robots in a Continuous Cycle

Authors: Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds.
Cite as

Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita. Gathering and Election by Mobile Robots in a Continuous Cycle. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{flocchini_et_al:LIPIcs.ISAAC.2019.8,
  author =	{Flocchini, Paola and Killick, Ryan and Kranakis, Evangelos and Santoro, Nicola and Yamashita, Masafumi},
  title =	{{Gathering and Election by Mobile Robots in a Continuous Cycle}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.8},
  URN =		{urn:nbn:de:0030-drops-115044},
  doi =		{10.4230/LIPIcs.ISAAC.2019.8},
  annote =	{Keywords: Cycle, Election, Gathering, Las Vegas, Monte Carlo, Randomized Algorithm}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2019
LIPIcs, Volume 132, ICALP'19, Complete Volume

Authors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
LIPIcs, Volume 132, ICALP'19, Complete Volume
Cite as

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{baier_et_al:LIPIcs.ICALP.2019,
  title =	{{LIPIcs, Volume 132, ICALP'19, Complete Volume}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019},
  URN =		{urn:nbn:de:0030-drops-108644},
  doi =		{10.4230/LIPIcs.ICALP.2019},
  annote =	{Keywords: Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 0:i-0:xxxviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baier_et_al:LIPIcs.ICALP.2019.0,
  author =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{0:i--0:xxxviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.0},
  URN =		{urn:nbn:de:0030-drops-105765},
  doi =		{10.4230/LIPIcs.ICALP.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.19
TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and Its Applications

Authors: Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, and Giovanni Viglietta

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

Abstract
In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Each robot is punctiform and memoryless, it operates in R^m, it has a local reference system independent of the other robots' ones, and is activated asynchronously by an adversarial scheduler. Moreover, the robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3m+3k of these weak entities in R^m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.
Cite as

Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, and Giovanni Viglietta. TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and Its Applications. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2018.19,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni},
  title =	{{TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and Its Applications}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.19},
  URN =		{urn:nbn:de:0030-drops-98086},
  doi =		{10.4230/LIPIcs.DISC.2018.19},
  annote =	{Keywords: Mobile Robots, Turing Machine, Real RAM}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.31
Shape Formation by Programmable Particles

Authors: Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Shape formation (or pattern formation) is a basic distributed problem for systems of compu- tational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter, where entities are assumed to be small and with severely limited capabilities. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessella- tion of the plane and have limited computational power (they have constant memory), strictly local interaction and communication capabilities (only with particles in neighboring nodes of the grid), and limited motorial capabilities (from a grid node to an empty neighboring node); their activation is controlled by an adversarial scheduler. Recent investigations have shown how, start- ing from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization (i.e., particles can flip coins to elect a leader). In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. The characterization is constructive: we provide a universal shape formation algorithm that, for each feasible pair of shapes (S_0,S_F), allows the particles to form the final shape SF (given in input) starting from the initial shape S_0, unknown to the particles. The final configuration will be an appropriate scaled-up copy of S_F depending on n. If randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that there are enough particles. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n^2) rounds and moves: this number of moves is also asymptotically worst-case optimal.
Cite as

Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Shape Formation by Programmable Particles. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.OPODIS.2017.31,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamauchi, Yukiko},
  title =	{{Shape Formation by Programmable Particles}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.31},
  URN =		{urn:nbn:de:0030-drops-86370},
  doi =		{10.4230/LIPIcs.OPODIS.2017.31},
  annote =	{Keywords: Shape formation, pattern formation, programmable matter, Amoebots, leader election, distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.14
Meeting in a Polygon by Anonymous Oblivious Robots

Authors: Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.
Cite as

Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Meeting in a Polygon by Anonymous Oblivious Robots. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2017.14,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamashita, Masafumi},
  title =	{{Meeting in a Polygon by Anonymous Oblivious Robots}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.14},
  URN =		{urn:nbn:de:0030-drops-79833},
  doi =		{10.4230/LIPIcs.DISC.2017.14},
  annote =	{Keywords: Meeting problem, Oblivious robots, Polygon, Self-stabilization}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.48
Brief Announcement: Shape Formation by Programmable Particles

Authors: Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane, have constant memory, can only communicate with neighboring particles, and can only move from a grid node to an empty neighboring node; their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization. In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. As a byproduct, if randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that n is large enough. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n^2) rounds and moves: this number of moves is also asymptotically optimal.
Cite as

Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Brief Announcement: Shape Formation by Programmable Particles. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2017.48,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamauchi, Yukiko},
  title =	{{Brief Announcement: Shape Formation by Programmable Particles}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{48:1--48:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.48},
  URN =		{urn:nbn:de:0030-drops-80019},
  doi =		{10.4230/LIPIcs.DISC.2017.48},
  annote =	{Keywords: Shape formation, pattern formation, programmable matter, Amoebots, leader election, distributed algorithms, self-assembly}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.14
A Rupestrian Algorithm

Authors: Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
Deciphering recently discovered cave paintings by the Astracinca, an egalitarian leaderless society flourishing in the 3rd millennium BCE, we present and analyze their shamanic ritual for forming new colonies. This ritual can actually be used by systems of anonymous mobile finite-state computational entities located and operating in a grid to solve the line recovery problem, a task that has both self-assembly and flocking requirements. The protocol is totally decentralized, fully concurrent, provably correct, and time optimal.
Cite as

Giuseppe A. Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. A Rupestrian Algorithm. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.FUN.2016.14,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Prencipe, Giuseppe and Santoro, Nicola and Viglietta, Giovanni},
  title =	{{A Rupestrian Algorithm}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.14},
  URN =		{urn:nbn:de:0030-drops-58751},
  doi =		{10.4230/LIPIcs.FUN.2016.14},
  annote =	{Keywords: mobile finite-state machines, self-healing distributed algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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