Maximum Matching for Anonymous Trees with Constant Space Per Process
Leibniz International Proceedings in Informatics, LIPIcs
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
First page number:
Last page number:
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.
Anonymous tree; Maximum matching; Self-stabilization; Unfair daemon
Maximum Matching for Anonymous Trees with Constant Space Per Process.
Leibniz International Proceedings in Informatics, LIPIcs, 46
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.