| 概要： |
膨大な数の計算機から構成される大規模なネットワークでは，
個々の計算機に発生する故障を回避することができない．
そのため，大規模なネットワークを対象としたシステムでは，
高度な故障耐性と自立適応性が必要とされる．
本講演では，高度な自律適応能力をそなえた分散アルゴリズムである
自己安定アルゴリズムに着目し，自己安定極大マッチング問題に関する
最新の研究動向について紹介する．
極大マッチング問題はグラフ理論においてよく研究されている問題であり，
最大マッチングに対するよい近似アルゴリズムが必要とされている．
自己安定マッチングアルゴリズムにおいては，現在まで，
任意のネットワークに対する1/2-近似アルゴリズム，特定のネットワークに
対する2/3-近似アルゴリズムしか提案されていない．
本講演では，任意のネットワークに対する2/3-近似アルゴリズムを紹介するとともに，
既存の自己安定マッチングアルゴリズムを高速化する手法についても説明する．
The matching problem asks for a large set of disjoint edges in a graph.
It is a problem that has received considerable attention both from the
sequential and the self-stabilizing communities. Previous work has
resulted in self-stabilization algorithms for computing a maximal (1/2
-approximation) matching in a general graph, as well as computing a 2/3
-approximation on more specific graph types.
In this lecture we present a single self-stabilizing algorithm for the
maximal matching problem that unites all of the previous algorithms in
that it has the same time complexity as the previous best algorithms for
the sequential adversarial, the distributed fair, and the synchronous
daemon. In addition, the algorithm improves the previous best time
complexities for the distributed adversarial daemon from O(n2) and
O(d.m) to O(m) where n is the number of processes, m is the number of
edges, and d is the maximum degree in the graph.
Moreover, we present the first self-stabilizing algorithm for finding a
2/3-approximation to the maximum matching problem in a general graph.
We show that our new algorithm converges in time O(2^(n+2).d.n) moves
and O(n2) rounds under a distributed adversarial and distributed fair
daemon, respectively, where n is the number of nodes in the graph.
|