A Self-stabilizing 1-maximal Independent Set Algorithm

• Hideyuki, Tanaka

• Yuichi, Sudo

• Hirotsugu, Kakugawa

• Toshimitsu, Masuzawa

• Ajoy, K. Datta

抄録

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 ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.29(2021) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.29.247------------------------------

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 ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.29(2021) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.29.247------------------------------

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 62 (3), 2021-03-15

キーワード

• [一般論文（推薦論文）] distributed system, self-stabilizing algorithm, loop composition, 1-maximal independent set

詳細情報

• CRID: 1050850412738215808
• NII論文ID: 170000184443
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00210262/
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles