Self-stabilizing 2-minimal dominating set algorithms based on loop composition

Maruyama Syohei

Sudo Yuichi

Kamei Sayaka

Kakugawa Hirotsugu

Theoretical Computer Science

Given a graph G = (V,E), a 2-minimal dominating set (2-MDS) of G is a minimal dominating set D ⊆ V such that D \ {pi, pj} ∪ {pz} is not a dominating set for any nodes pi, pj ∈ D (pi ̸= pj ) and pz ̸∈ D. We propose two silent self-stabilizing asynchronous distributed algorithms to find a 2-MDS. In both algorithms, we assume the weakly fair distributed daemon and that the processes have unique identifiers. The first one is for the general networks. The time complexity is O(nH) rounds, and the space complexity is O(Δ log n) bits per process, where n is the number of processes, H is the diameter of the network, and Δ is the maximum degree. The second one is for the networks of girth at least 7. The girth is the length of the shortest cycles in the network. The time complexity is O(nH) rounds, and the space complexity is O(log n) bits per process.

Dominating set

Self-stabilization

Loop composition

2-minimality

Girth

eng

Elsevier

© 2023. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/

This is not the published version. Please cite only the published version.

この論文は出版社版ではありません。引用の際には出版社版をご確認、ご利用ください。

[DOI] https://doi.org/10.1016/j.tcs.2023.114314 isVersionOf

日本学術振興会

Japan Society for the Promotion of Science

[Crossref Funder] https://doi.org/10.13039/501100001691

外乱に対して安定な分散アルゴリズムの相互作用パターン

外乱に対して安定な分散アルゴリズムの相互作用パターン

19K11826

日本学術振興会

Japan Society for the Promotion of Science

[Crossref Funder] https://doi.org/10.13039/501100001691

動的ネットワークにおける動的タスクのための適応的な耐故障性を持つ分散アルゴリズム

動的ネットワークにおける動的タスクのための適応的な耐故障性を持つ分散アルゴリズム

19K11828

日本学術振興会

Japan Society for the Promotion of Science

[Crossref Funder] https://doi.org/10.13039/501100001691

情報の不確かさに着目した大規模動的分散システムの新たな理論的基盤とその応用

New theoretical basis of large scale dynamic distributed systems based on uncertain information and its applications

19H04085

日本学術振興会

Japan Society for the Promotion of Science

[Crossref Funder] https://doi.org/10.13039/501100001691

障害から超高速に自律復旧するナノスケールネットワークの設計

障害から超高速に自律復旧するナノスケールネットワークの設計

20H04140

日本学術振興会

Japan Society for the Promotion of Science

[Crossref Funder] https://doi.org/10.13039/501100001691

動的ネットワークにおける多様な故障に対する耐性を持つ分散アルゴリズム

動的ネットワークにおける多様な故障に対する耐性を持つ分散アルゴリズム

23H03347

日本学術振興会

Japan Society for the Promotion of Science

[Crossref Funder] https://doi.org/10.13039/501100001691

動的自律分散システムにおけるプロセス選出のための相互作用パターンの解明

動的自律分散システムにおけるプロセス選出のための相互作用パターンの解明

23K11059

科学技術振興機構

Japan Science and Technology Agency

自己安定アルゴリズムの飛躍的発展に向けた研究

自己安定アルゴリズムの飛躍的発展に向けた研究

JPMJFR226U