A Robust Distributed Generalized Matching Protocol that Stabilizes in Linear Time

We present a self-stabilizing algorithm for finding a generalized maximal matching (􀀀-matching) in an arbitrary distributed network. We show that the algorithm converges in 􀀀 moves under an unfair central demon independent of the 􀀀-values at different nodes. The algorithm is capable of working with multiple types of demons (schedulers) as is the most recent algorithm in [1, 2].


Back