Maximum matching for anonymous trees with constant space per process

Document Type

Conference Proceeding


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

UNLV article access