Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks - Sorbonne Université Access content directly
Conference Papers Year : 2017

Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks

Abstract

We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. The 1-maximal matching is a 2/3-approximation of a maximum matching, a significant improvement over the 1/2-approximation that is guaranteed by a maximal matching. Our algorithm is efficient (its stabilization time is $O(e)$ moves, where $e$ denotes the number of edges in the network). Besides, our algorithm is optimal with respect to identifiers locality (we assume node identifiers are distinct up to distance three, a necessary condition to withstand arbitrary networks). The proposed algorithm closes the complexity gap between two recent works: Inoue et al. presented a 1-maximal matching algorithm that is $O(e)$ moves but requires the network topology not to contain a cycle of size of multiple of three ; Cohen et al. consider arbitrary topology networks but requires $O(n^3)$ moves to stabilize (where $n$ denotes the number of nodes in the network). Our solution preserves the better complexity of $O(e)$ moves, yet considers arbitrary networks, demonstrating that previous restrictions were unnecessary to preserve complexity results.
No file

Dates and versions

hal-01520336 , version 1 (10-05-2017)

Identifiers

  • HAL Id : hal-01520336 , version 1

Cite

Michiko Inoue, Fukuhito Ooshita, Sébastien Tixeuil. Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks. ACM Conference on Principles of Distributed Computing (PODC 2017) , Jul 2017, Washington, United States. ⟨hal-01520336⟩
256 View
0 Download

Share

Gmail Facebook X LinkedIn More