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.OPODIS.2015.16
URN: urn:nbn:de:0030-drops-66074
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6607/
Go to the corresponding LIPIcs Volume Portal

Datta, Ajoy K. ; Larmore, Lawrence L. ; Masuzawa, Toshimitsu

Maximum Matching for Anonymous Trees with Constant Space per Process

pdf-format:
LIPIcs-OPODIS-2015-16.pdf (0.5 MB)

Abstract

We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.

BibTeX - Entry

@InProceedings{datta_et_al:LIPIcs:2016:6607,
  author =	{Ajoy K. Datta and Lawrence L. Larmore and Toshimitsu Masuzawa},
  title =	{{Maximum Matching for Anonymous Trees with Constant Space per Process}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6607},
  URN =		{urn:nbn:de:0030-drops-66074},
  doi =		{10.4230/LIPIcs.OPODIS.2015.16},
  annote =	{Keywords: anonymous tree, maximum matching, self-stabilization, unfair daemon}
}

Keywords: anonymous tree, maximum matching, self-stabilization, unfair daemon
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

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