License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.12
URN: urn:nbn:de:0030-drops-98012
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9801/
Go to the corresponding LIPIcs Volume Portal

Bonamy, Marthe ; Ouvrard, Paul ; Rabie, Mikaël ; Suomela, Jukka ; Uitto, Jara

Distributed Recoloring

pdf-format:
LIPIcs-DISC-2018-12.pdf (0.4 MB)

Abstract

Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step?
We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously.
We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier?
The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.

BibTeX - Entry

@InProceedings{bonamy_et_al:LIPIcs:2018:9801,
  author =	{Marthe Bonamy and Paul Ouvrard and Mika{\"e}l Rabie and Jukka Suomela and Jara Uitto},
  title =	{{Distributed Recoloring}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9801},
  URN =		{urn:nbn:de:0030-drops-98012},
  doi =		{10.4230/LIPIcs.DISC.2018.12},
  annote =	{Keywords: Distributed Systems, Graph Algorithms, Local Computations}
}

Keywords: Distributed Systems, Graph Algorithms, Local Computations
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI