A self-stabilizing algorithm for b-matching

Can Umut Ileri, Orhan Dagdeviren

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

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(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).

Original languageEnglish
Pages (from-to)64-75
Number of pages12
JournalTheoretical Computer Science
Volume753
DOIs
Publication statusPublished - 1 Jan 2019
Externally publishedYes

Keywords

  • b-matching
  • Distributed algorithm
  • Self-stabilization

Fingerprint Dive into the research topics of 'A self-stabilizing algorithm for b-matching'. Together they form a unique fingerprint.

Cite this