講演抄録/キーワード |
講演名 |
2017-10-20 10:00
Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks ○Michiko Inoue・Fukuhito Ooshita(NAIST)・Sebastien Tixeuil(UPMC) SS2017-31 DC2017-30 |
抄録 |
(和) |
We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. The textit{1-maximal} matching is a $frac{2}{3}$-approximation of a maximum matching, a significant improvement over the $frac{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 emph{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 emph{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. |
(英) |
We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. The textit{1-maximal} matching is a $frac{2}{3}$-approximation of a maximum matching, a significant improvement over the $frac{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 emph{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 emph{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. |
キーワード |
(和) |
/ / / / / / / |
(英) |
self-stabilization / 1-maximal matching / distributed unfair daemon / arbitrary network / / / / |
文献情報 |
信学技報, vol. 117, no. 249, DC2017-30, pp. 61-66, 2017年10月. |
資料番号 |
DC2017-30 |
発行日 |
2017-10-12 (SS, DC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
SS2017-31 DC2017-30 |
|