A self-stabilizing algorithm for b-matching
Makaleler > Tam Makale · 2018
Yazarlar: CAN UMUT İLERİ, Orhan DAĞDEVİREN
Theoretical Computer Science, SCI Expanded İndekslerine Giren Dergi, Uluslararası, Wos, 2018, cilt 753, ss 64-75
DOI: 10.1016/j.tcs.2018.06.042
Özet
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 (Bm) 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). (C) 2018 Elsevier B.V. All rights reserved.