分散アルゴリズムの初期条件の作る構造について
スポンサーリンク
概要
- 論文の詳細を見る
匿名ネットワーク上の分散アルゴリズムにおいて, 与える初期条件により解決でき得る問題は大きく異なる.従来の研究では全頂点数が与えられる場合の計算や, リーダを選出するアルゴリズムといった各個別の条件や, 問題に対するアプローチが行われてきた.本論文では分散アルゴリズムにより初期条件Bを満たすあらゆる初期値から初期条件Aを満たすような初期値を作ることができることをA≦Bという関係で表し, この関係が決定可能なあらゆる初期条件に対してどのような性質をもつかを調べた.この結果, この関係は同値類に対して半順序関係になり, 最大元, 最小元をもつ無限の要素をもつlatticeを作ることがわかった.また, 新たにk個だけあらかじめ特別な頂点を選ぶk-LEADERと, k種類のグループを与えるk-COLORという初期条件を与え, 相互の関係を調べた.
- 社団法人電子情報通信学会の論文
- 1998-11-25
著者
関連論文
- リーダ選出可能な確率的分散アルゴリズムの初期条件 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- プライベートネットワークアドレスを利用する際の経路制御について
- 分散アルゴリズムの初期条件の作る構造について
- 確率的分散アルゴリズムに対するネットワークのサイズに関する情報について (アルゴリズムと計算の理論)
- 分散アルゴリズムの初期条件の作る構造について
- 確率的分散アルゴリズムにおける初期条件の階層について(計算量理論とその応用)
- ネットワークの対称性と、$k$-LEADER(S)の計算能力(理論計算機科学とその周辺)