(2,2)-弱極大DAG構成自己安定アルゴリズムの研究

摘要

本研究では，任意の無向グラフ上に(2,2)-弱極大DAG を構成する自己安定アルゴリズムを提案する．自己安定 アルゴリズムとは，任意の初期ネットワーク状況から実 行を開始しても，目的のシステム状況に到達できる分 散アルゴリズムであり，一時故障に対する耐故障性を持 ち，トポロジの変化にも対応できるという特徴がある． DAG とは，閉路の無い有向グラフのことで，内向辺を 持たないノードをソース，外向辺を持たないノードをシ ンクという．(S; T )-極大DAG とは，与えられた任意の 連結無向グラフにおいて，あらかじめ決められたS 個 のノードとT 個のノードをそれぞれソースとシンクに なるように構成された有向辺と無向辺が混在するグラフ で，無向辺を一つでも方向付けると，指定されていない ノードがソースやシンクとなるか，有向閉路が生じる． (S, T )-弱極大DAG とは，各ソースが少なくとも一つの シンクに有向経路を持ち，かつ各シンクが少なくとも一 つのソースからの有向経路を持つものである．本研究で は，(2,2)-弱極大DAG を構成する自己安定アルゴリズ ムを提案する．