DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2020.40

Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping

Authors: Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto

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

Abstract

We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds.

Cite as

Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 40:1-40:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.DISC.2020.40,
  author =	{Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara},
  title =	{{Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{40:1--40:3},
  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.40},
  URN =		{urn:nbn:de:0030-drops-131182},
  doi =		{10.4230/LIPIcs.DISC.2020.40},
  annote =	{Keywords: distributed algorithms, graph problems, semi-matching}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.9

Overcoming Obstacles with Ants

Authors: Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract

Consider a group of mobile finite automata, referred to as agents, located in the origin of an infinite grid. The grid is occupied by obstacles, i.e., sets of cells that can not be entered by the agents. In every step, an agent can sense the states of the co-located agents and is allowed to move to any neighboring cell of the grid not blocked by an obstacle. We assume that the circumference of each obstacle is finite but allow the number of obstacles to be unbounded. The task of the agents is to cooperatively find a treasure, hidden in the grid by an adversary. In this work, we show how the agents can utilize their simple means of communication and their constant memory to systematically explore the grid and to locate the treasure in finite time. As integral part of the agents' behavior, we present a method that allows a group of six agents to follow a straight line, even if the line is partially obstructed by obstacles, and to discover all free cells along this line. In total, our search protocol requires nine agents.

Cite as

Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{langner_et_al:LIPIcs.OPODIS.2015.9,
  author =	{Langner, Tobias and Keller, Barbara and Uitto, Jara and Wattenhofer, Roger},
  title =	{{Overcoming Obstacles with Ants}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.9},
  URN =		{urn:nbn:de:0030-drops-66005},
  doi =		{10.4230/LIPIcs.OPODIS.2015.9},
  annote =	{Keywords: Mobile agents, algorithms, treasure search}
}

Search Results

Documents authored by Keller, Barbara

Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping

Abstract

Cite as

Overcoming Obstacles with Ants

Abstract

Cite as

Thanks for your feedback!

Could not send message