"Maximum Matching for Anonymous Trees with Constant Space Per Process" by Ajoy Datta, Lawrence Larmore et al.
 

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

UNLV article access

Share

COinS