HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Contributor : Sébastien Tixeuil Connect in order to contact the contributor
Submitted on : Wednesday, May 10, 2017 - 1:15:43 PM
Last modification on : Friday, January 8, 2021 - 5:38:04 PM


  • HAL Id : hal-01520336, version 1


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