Maximum Matching for Anonymous Trees with Constant Space per Process

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