A Self-stabilizing 1-maximal Independent Set Algorithm

• Item type: Journal(1)
• 公開日: 2021-03-15
• タイトル: A Self-stabilizing 1-maximal Independent Set Algorithm
• タイトル / 言語: en
• タイトル: A Self-stabilizing 1-maximal Independent Set Algorithm
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文（推薦論文）] distributed system, self-stabilizing algorithm, loop composition, 1-maximal independent set
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: Faculty of Advanced Science and Technology and Ryukoku Center for Mathematical Sciences and Networks, Ryukoku University
• 著者所属: Graduate School of Information Science and Technology, Osaka University
• 著者所属: University of Nevada, Las Vegas
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Advanced Science and Technology and Ryukoku Center for Mathematical Sciences and Networks, Ryukoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): University of Nevada, Las Vegas
• 著者名: Hideyuki, Tanaka; Yuichi, Sudo; Hirotsugu, Kakugawa; Toshimitsu, Masuzawa; Ajoy, K. Datta
• 著者名(英): Hideyuki, Tanaka; Yuichi, Sudo; Hirotsugu, Kakugawa; Toshimitsu, Masuzawa; Ajoy, K. Datta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We consider the 1-maximal independent set (1-MIS) problem: given a graph G=(V, E), our goal is to find a 1-maximal independent set (1-MIS) of a given network G, that is, a maximal independent set (MIS) S ⊂ V of G such that S ∪ {v, w} ∖ {u} is not an independent set for any nodes u ∈ S, and v, w ∉ S (v ≠ w). We give a silent, self-stabilizing, and asynchronous distributed algorithm to construct a 1-MIS on a network of any topology. We assume the processes have unique identifiers and the scheduler is weakly-fair and distributed. The time complexity, i.e., the number of rounds to reach a legitimate configuration in the worst case of the proposed algorithm is O(nD), where n is the number of processes in the network and D is the diameter of the network. We use a composition technique called loop composition [Datta et al., 2017] to iterate the same procedure consistently, which results in a small space complexity, O(log n) bits per process.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.29(2021) (online); DOI http://dx.doi.org/10.2197/ipsjjip.29.247; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the 1-maximal independent set (1-MIS) problem: given a graph G=(V, E), our goal is to find a 1-maximal independent set (1-MIS) of a given network G, that is, a maximal independent set (MIS) S ⊂ V of G such that S ∪ {v, w} ∖ {u} is not an independent set for any nodes u ∈ S, and v, w ∉ S (v ≠ w). We give a silent, self-stabilizing, and asynchronous distributed algorithm to construct a 1-MIS on a network of any topology. We assume the processes have unique identifiers and the scheduler is weakly-fair and distributed. The time complexity, i.e., the number of rounds to reach a legitimate configuration in the worst case of the proposed algorithm is O(nD), where n is the number of processes in the network and D is the diameter of the network. We use a composition technique called loop composition [Datta et al., 2017] to iterate the same procedure consistently, which results in a small space complexity, O(log n) bits per process.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.29(2021) (online); DOI http://dx.doi.org/10.2197/ipsjjip.29.247; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 62, 号 3, 発行日 2021-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764