A self-stabilizing algorithm for b-matching

Abstract We present the first self-stabilizing algorithm for finding a maximal b -matching in arbitrary networks and under distributed unfair (adversarial) schedulers. The previous self-stabilizing b -matching algorithm presented by Goddard et al. in 2003 assumes central scheduler. We give proof for the correctness of our new algorithm for both unfair and fair schedulers, as well as the synchronous scheduler. Our algorithm stabilizes in O ( B m ) steps under unfair scheduler and in O ( n ) rounds under distributed fair and synchronous schedulers, where n , m and B are the number of processors, the number of edges and the maximum capacity in the graph, respectively. The time complexity of distributed fair version of our algorithm is better than that of the transformation of Goddard et al.'s sequential self-stabilizing algorithm to the distributed fair one with the conflict manager of Gradinariu and Tixeuil (2007).