WEKO3
アイテム
A self-stabilizing distributed algorithm for the 1-MIS problem under the distance-3 model
http://hdl.handle.net/10228/0002001646
http://hdl.handle.net/10228/00020016462fdfb9a7-160b-4e54-a670-c22bdd63a847
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10448660.pdf (182 KB)
|
|
| Item type | 共通アイテムタイプ(1) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-04-24 | |||||||||||||||
| タイトル | ||||||||||||||||
| タイトル | A self-stabilizing distributed algorithm for the 1-MIS problem under the distance-3 model | |||||||||||||||
| 言語 | en | |||||||||||||||
| 著者 |
Kakugawa, Hirotsugu
× Kakugawa, Hirotsugu
× Kamei, Sayaka
× 柴田, 将拡
WEKO
25091
× Ooshita, Fukuhito
|
|||||||||||||||
| 著作権関連情報 | ||||||||||||||||
| 言語 | en | |||||||||||||||
| 権利情報 | Copyright (c) 2024JohnWiley&SonsLtd. | |||||||||||||||
| 抄録 | ||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||
| 内容記述 | Fault-tolerance and self-organization are critical properties in modern distributed systems. Self-stabilization is a class of fault-tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self-stabilizing distributed algorithm for the 1-MIS problem under the unfair central daemon assuming the distance-3 model. Here, in the distance-3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1-MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is O(n) steps and the space complexity is O(logn) bits, where n is the number of processes. Finally, we extend the notion of 1-MIS to p-MIS for each nonnegative integer p, and compare the set sizes of p-MIS (p = 0, 1, 2...) and the maximum independent set. | |||||||||||||||
| 言語 | en | |||||||||||||||
| 書誌情報 |
en : Concurrency and Computation: Practice and Experience 巻 36, 号 26, p. e8281, 発行日 2024-09-09 |
|||||||||||||||
| 出版社 | ||||||||||||||||
| 出版者 | Wiley | |||||||||||||||
| キーワード | ||||||||||||||||
| 言語 | en | |||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | 1-MIS | |||||||||||||||
| キーワード | ||||||||||||||||
| 言語 | en | |||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | maximal independent set | |||||||||||||||
| キーワード | ||||||||||||||||
| 言語 | en | |||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | self-stabilization | |||||||||||||||
| キーワード | ||||||||||||||||
| 言語 | en | |||||||||||||||
| 主題Scheme | Other | |||||||||||||||
| 主題 | distributed algorithm | |||||||||||||||
| 言語 | ||||||||||||||||
| 言語 | eng | |||||||||||||||
| 資源タイプ | ||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||
| 資源タイプ | journal article | |||||||||||||||
| 出版タイプ | ||||||||||||||||
| 出版タイプ | AM | |||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||
| DOI | ||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||
| 関連識別子 | https://doi.org/10.1002/cpe.8281 | |||||||||||||||
| NCID | ||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||
| 収録物識別子 | AA11557540 | |||||||||||||||
| ISSN | ||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||
| 収録物識別子 | 1532-0626 | |||||||||||||||
| ISSN | ||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||
| 収録物識別子 | 1532-0634 | |||||||||||||||
| 査読の有無 | ||||||||||||||||
| 値 | yes | |||||||||||||||
| 研究者情報 | ||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/100001003_ja.html | |||||||||||||||
| 論文ID（連携） | ||||||||||||||||
| 値 | 10448660 | |||||||||||||||
| 連携ID | ||||||||||||||||
| 値 | 14427 | |||||||||||||||
