Search Results

Documents authored by Viglietta, Giovanni

Document
DOI: 10.4230/LIPIcs.MFCS.2024.49
Efficient Computation in Congested Anonymous Dynamic Networks

Authors: Giuseppe A. Di Luna and Giovanni Viglietta

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
An anonymous dynamic network is a network of indistinguishable processes whose communication links may appear or disappear unpredictably over time. Previous research has shown that deterministically computing an arbitrary function of a multiset of input values given to these processes takes only a linear number of communication rounds (Di Luna-Viglietta, FOCS 2022). However, fast algorithms for anonymous dynamic networks rely on the construction and transmission of large data structures called history trees, whose size is polynomial in the number of processes. This approach is unfeasible if the network is congested, and only messages of logarithmic size can be sent through its links. Observe that sending a large message piece by piece over several rounds is not in itself a solution, due to the anonymity of the processes combined with the dynamic nature of the network. Moreover, it is known that certain basic tasks such as all-to-all token dissemination (by means of single-token forwarding) require Ω(n²/log n) rounds in congested networks (Dutta et al., SODA 2013). In this work, we develop a series of practical and efficient techniques that make it possible to use history trees in congested anonymous dynamic networks. Among other applications, we show how to compute arbitrary functions in such networks in O(n³) communication rounds, greatly improving upon previous state-of-the-art algorithms for congested networks.
Cite as

Giuseppe A. Di Luna and Giovanni Viglietta. Efficient Computation in Congested Anonymous Dynamic Networks. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.MFCS.2024.49,
  author =	{Di Luna, Giuseppe A. and Viglietta, Giovanni},
  title =	{{Efficient Computation in Congested Anonymous Dynamic Networks}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.49},
  URN =		{urn:nbn:de:0030-drops-206056},
  doi =		{10.4230/LIPIcs.MFCS.2024.49},
  annote =	{Keywords: anonymous dynamic network, congested network, history tree}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.18
Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks

Authors: Giuseppe A. Di Luna and Giovanni Viglietta

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

Abstract
We give a simple characterization of which functions can be computed deterministically by anonymous processes in dynamic networks, depending on the number of leaders in the network. In addition, we provide efficient distributed algorithms for computing all such functions assuming minimal or no knowledge about the network. Each of our algorithms comes in two versions: one that terminates with the correct output and a faster one that stabilizes on the correct output without explicit termination. Notably, these are the first deterministic algorithms whose running times scale linearly with both the number of processes and a parameter of the network which we call dynamic disconnectivity (meaning that our dynamic networks do not necessarily have to be connected at all times). We also provide matching lower bounds, showing that all our algorithms are asymptotically optimal for any fixed number of leaders. While most of the existing literature on anonymous dynamic networks relies on classical mass-distribution techniques, our work makes use of a recently introduced combinatorial structure called history tree, also developing its theory in new directions. Among other contributions, our results make definitive progress on two popular fundamental problems for anonymous dynamic networks: leaderless Average Consensus (i.e., computing the mean value of input numbers distributed among the processes) and multi-leader Counting (i.e., determining the exact number of processes in the network). In fact, our approach unifies and improves upon several independent lines of research on anonymous networks, including Nedić et al., IEEE Trans. Automat. Contr. 2009; Olshevsky, SIAM J. Control Optim. 2017; Kowalski-Mosteiro, ICALP 2019, SPAA 2021; Di Luna-Viglietta, FOCS 2022.
Cite as

Giuseppe A. Di Luna and Giovanni Viglietta. Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2023.18,
  author =	{Di Luna, Giuseppe A. and Viglietta, Giovanni},
  title =	{{Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.18},
  URN =		{urn:nbn:de:0030-drops-191442},
  doi =		{10.4230/LIPIcs.DISC.2023.18},
  annote =	{Keywords: anonymous dynamic network, leaderless network, disconnected network, history tree}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.1
Pushing Blocks by Sweeping Lines

Authors: Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
We investigate the reconfiguration of n blocks, or "tokens", in the square grid using line pushes. A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite direction by one unit. Tokens that are in the way of other tokens are displaced in the same direction, as well. Similar models of manipulating objects using uniform external forces match the mechanics of existing games and puzzles, such as Mega Maze, 2048 and Labyrinth, and have also been investigated in the context of self-assembly, programmable matter and robotic motion planning. The problem of obtaining a given shape from a starting configuration is know to be NP-complete. We show that, for every n, there are sparse initial configurations of n tokens (i.e., where no two tokens are in the same row or column) that can be compacted into any a×b box such that ab = n. However, only 1×k, 2×k and 3×3 boxes are obtainable from any arbitrary sparse configuration with a matching number of tokens. We also study the problem of rearranging labeled tokens into a configuration of the same shape, but with permuted tokens. For every initial configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.
Cite as

Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta. Pushing Blocks by Sweeping Lines. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1,
  author =	{A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni},
  title =	{{Pushing Blocks by Sweeping Lines}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.1},
  URN =		{urn:nbn:de:0030-drops-159719},
  doi =		{10.4230/LIPIcs.FUN.2022.1},
  annote =	{Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.5
Chasing Puppies: Mobile Beacon Routing on Closed Curves

Authors: Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
Cite as

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5,
  author =	{Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
  title =	{{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.5},
  URN =		{urn:nbn:de:0030-drops-138046},
  doi =		{10.4230/LIPIcs.SoCG.2021.5},
  annote =	{Keywords: Beacon routing, navigation, generic smooth curves, puppies}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.12
Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots

Authors: Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
A swarm of anonymous oblivious mobile robots, operating in deterministic Look-Compute-Move cycles, is confined within a circular track. All robots agree on the clockwise direction (chirality), they are activated by an adversarial semi-synchronous scheduler (SSYNCH), and an active robot always reaches the destination point it computes (rigidity). Robots have limited visibility: each robot can see only the points on the circle that have an angular distance strictly smaller than a constant ϑ from the robot’s current location, where 0 < ϑ ≤ π (angles are expressed in radians). We study the Gathering problem for such a swarm of robots: that is, all robots are initially in distinct locations on the circle, and their task is to reach the same point on the circle in a finite number of turns, regardless of the way they are activated by the scheduler. Note that, due to the anonymity of the robots, this task is impossible if the initial configuration is rotationally symmetric; hence, we have to make the assumption that the initial configuration be rotationally asymmetric. We prove that, if ϑ = π (i.e., each robot can see the entire circle except its antipodal point), there is a distributed algorithm that solves the Gathering problem for swarms of any size. By contrast, we also prove that, if ϑ ≤ π/2, no distributed algorithm solves the Gathering problem, regardless of the size of the swarm, even under the assumption that the initial configuration is rotationally asymmetric and the visibility graph of the robots is connected. The latter impossibility result relies on a probabilistic technique based on random perturbations, which is novel in the context of anonymous mobile robots. Such a technique is of independent interest, and immediately applies to other Pattern-Formation problems.
Cite as

Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi. Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2020.12,
  author =	{Di Luna, Giuseppe A. and Uehara, Ryuhei and Viglietta, Giovanni and Yamauchi, Yukiko},
  title =	{{Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.12},
  URN =		{urn:nbn:de:0030-drops-130907},
  doi =		{10.4230/LIPIcs.DISC.2020.12},
  annote =	{Keywords: Mobile robots, Gathering, limited visibility, circle}
}
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.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.13
Super Mario Bros. is Harder/Easier Than We Thought

Authors: Erik D. Demaine, Giovanni Viglietta, and Aaron Williams

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

Abstract
Mario is back! In this sequel, we prove that solving a generalized level of Super Mario Bros. is PSPACE-complete, strengthening the previous NP-hardness result (FUN 2014). Both our PSPACE-hardness and the previous NP-hardness use levels of arbitrary dimensions and require either arbitrarily large screens or a game engine that remembers the state of off-screen sprites. We also analyze the complexity of the less general case where the screen size is constant, the number of on-screen sprites is constant, and the game engine forgets the state of everything substantially off-screen, as in most, if not all, Super Mario Bros. video games. In this case we prove that the game is solvable in polynomial time, assuming levels are explicitly encoded; on the other hand, if levels can be represented using run-length encoding, then the problem is weakly NP-hard (even if levels have only constant height, as in the video games). All of our hardness proofs are also resilient to known glitches in Super Mario Bros., unlike the previous NP-hardness proof.
Cite as

Erik D. Demaine, Giovanni Viglietta, and Aaron Williams. Super Mario Bros. is Harder/Easier Than We Thought. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.FUN.2016.13,
  author =	{Demaine, Erik D. and Viglietta, Giovanni and Williams, Aaron},
  title =	{{Super Mario Bros. is Harder/Easier Than We Thought}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{13:1--13:14},
  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.13},
  URN =		{urn:nbn:de:0030-drops-58802},
  doi =		{10.4230/LIPIcs.FUN.2016.13},
  annote =	{Keywords: video games, computational complexity, PSPACE}
}
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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.269
Algorithms for Designing Pop-Up Cards

Authors: Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°.
Cite as

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. Algorithms for Designing Pop-Up Cards. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.STACS.2013.269,
  author =	{Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lubiw, Anna and Schulz, Andr\'{e} and Souvaine, Diane L. and Viglietta, Giovanni and Winslow, Andrew},
  title =	{{Algorithms for Designing Pop-Up Cards}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{269--280},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269},
  URN =		{urn:nbn:de:0030-drops-39407},
  doi =		{10.4230/LIPIcs.STACS.2013.269},
  annote =	{Keywords: geometric folding, linkages, universality}
}
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