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

2 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
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.
Keywords :
Document type :
Conference papers

https://hal.sorbonne-universite.fr/hal-01520336
Contributor : Sébastien Tixeuil <>
Submitted on : Wednesday, May 10, 2017 - 1:15:43 PM
Last modification on : Tuesday, May 14, 2019 - 10:14:25 AM

Identifiers

• HAL Id : hal-01520336, version 1

Citation

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⟩

Record views