| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 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 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | 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. |
|
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | self-stabilization / 1-maximal matching / distributed unfair daemon / arbitrary network / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 117, no. 249, DC2017-30, pp. 61-66, Oct. 2017. | |
| Paper # | DC2017-30 | |
| Date of Issue | 2017-10-12 (SS, DC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | SS2017-31 DC2017-30 |
|
| Conference Information | |
| Committee | SS DC |
| Conference Date | 2017-10-19 - 2017-10-20 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kochi City Culture-plaza CUL-PORT |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Software System and Dependability on Network, etc |
| Paper Information | |
| Registration To | DC |
| Conference Code | 2017-10-SS-DC |
| Language | English |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks |
| Sub Title (in English) | |
| Keyword(1) | self-stabilization |
| Keyword(2) | 1-maximal matching |
| Keyword(3) | distributed unfair daemon |
| Keyword(4) | arbitrary network |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Michiko Inoue |
| 1st Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 2nd Author's Name | Fukuhito Ooshita |
| 2nd Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 3rd Author's Name | Sebastien Tixeuil |
| 3rd Author's Affiliation | UPMC Sorbonne Universités (UPMC) |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2017-10-20 10:00:00 |
| Presentation Time | 30 minutes |
| Registration for | DC |
| Paper # | SS2017-31, DC2017-30 |
| Volume (vol) | vol.117 |
| Number (no) | no.248(SS), no.249(DC) |
| Page | pp.61-66 |
| #Pages | 6 |
| Date of Issue | 2017-10-12 (SS, DC) |
[Return to Top Page]