We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is @math moves with high probability, under the adversarial distributed daemon. In this algorithm, each node can determine whether one of its neighbors points to it or to another node, leading to a contradiction with the anonymous assumption. To solve this problem, we provide under the classical link-register model, a self-stabilizing algorithm that gives a unique name to a link such that this name is shared by both extremities of the link.
@cite_18: 
@cite_20: Abstract We present a self-stabilizing algorithm for finding a maximal matching in distributed networks. Due to its self-stabilizing property, the algorithm can automatically detect and recover from the faults caused by unexpected perturbations on local variables maintained on each node of the system. A variant function is provided to prove the correctness of the algorithm and to analyze its time complexity.
@cite_11: We propose a generalized scheme that can convert any algorithm that self-stabilizes under an unfair central daemon into a randomized one that self-stabilizes under a distributed daemon, using only constant extra space and without IDs. If the original algorithm is anonymous the resulting self-stabilizing algorithm is also anonymous. We provide a detailed complexity analysis that show that the expected slowdown is upper bounded by O(n3).
All algorithms presented above, but the Hsu and Huang @cite_20 , assume nodes have unique identity. The Hsu and Huang's algorithm is the first one working in an anonymous network. This algorithm operates under any sequential daemon (fair or adversarial) in order to achieve symmetry breaking. Indeed, @cite_18 proved that in some anonymous networks there exists no deterministic self-stabilizing solution to the maximal matching problem under a synchronous daemon. This is a general result that holds under either the fair or the adversarial distributed daemon. This also holds whatever the communication and atomicity model (the state model with guarded rule atomicity or the link-register model with read write atomicity). @cite_11 proposed a generalized scheme that can convert any anonymous and deterministic algorithm that stabilizes under an adversarial sequential daemon into a randomized one that stabilizes under a distributed daemon, using only constant extra space and without identity. The expected slowdown is bounded by @math moves. The composition of these two algorithms can compute a maximal matching in @math moves in an anonymous network under a distributed daemon.