Maximum Matching for Anonymous Trees with Constant Space Per Process
Document Type
Conference Proceeding
Publication Date
1-1-2016
Publication Title
Leibniz International Proceedings in Informatics, LIPIcs
Publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume
46
First page number:
16.1
Last page number:
16.16
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 δ) space per process, where δ is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group ℤ7. © Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa.
Keywords
Anonymous tree; Maximum matching; Self-stabilization; Unfair daemon
Language
English
Repository Citation
Datta, A.,
Larmore, L.,
Masuzawa, T.
(2016).
Maximum Matching for Anonymous Trees with Constant Space Per Process.
Leibniz International Proceedings in Informatics, LIPIcs, 46
16.1-16.16.
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
http://dx.doi.org/10.4230/LIPIcs.OPODIS.2015.16