第 8 回 Angluin のアプローチ

本日の内容

• 8-1. 前回の復習
• 8-2. Angluin のアプローチ

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

8-1. 前回の復習

8-2. Angluin のアプローチ

D. Angluin "Local and Global Properties in Networks of Processors" 12th Symposium on Theory of Computer Science.(1980)

問題: ネットワーク(分散システム)が機能するためには、各プロセッサは自分 のID、他のID、ネットワークの構造などどのような情報をどれくらい知らなく てはならないのだろうか？ そのためのアプローチとして、まず、各プロセッサにほとんど何も情報のない 状態で仕事をさせます。 この何も情報の無い状態はどのようにして与えるかというと、同じ次数のプロ セッサは同じプログラムを与えることにします。 そして、どのようなグラフにおいて、目的の仕事(生成木を作る等)ができるか 考えます。

準備

計算ができる、できないを議論するため、計算を厳密に定義する必要がありま す。 そのため、ネットワークをグラフとチューリング機械のような物を使って表現 します。

正整数 d に対して Z_d={1,...,d} とします。 アルファベット A とは記号を表現するものの集合で、有限で少なくとも二つの要 素を持つものとします。

グラフ

• Gを有限無向連結で、さらに単純(多重辺、自己ループのない)なグ ラフのクラスとします。
• グラフ G に対して頂点の集合を V(G)、辺の集合を E(G)で表します。 また頂点 v に対して、 N_G(v)は v に接続してる頂点集合としま す。 頂点 v の次数を deg(v) で表します。
• G∈G に対してポートナンバリング {f_v} とは v∈G に対し、 f_v: N_G(v)→Z_deg(v) は全単射(bijection)であるものを言います。

プロセッサ

次数 d のプロセッサとは (Q,M) の二つ組で表されます。

• Q は状態の集合です。無限集合も許します。
• M は通信関数(Communication Function) で M: Q× Z_d→2^A×A×Q です。
• プロセッサ p_d に対して、 STATE(p_d)=Q、 M_d は p_d の communication funciton とする。

ここで M(q,i) は (a,b,q') という組の集合に対応づけられます。 これが意味するのは、状態 q のプロセッサがポート i のプロセッ サとメッセージ a と b を交換して、新たな状態 q' に遷移することです。

プロセッサが有限状態とは Q が有限集合であることです。

p_d を次数 d のプロセッサとするとき、プロセッサの列とは (p₁, p₂, ... ) という無限列を示す。

ネットワーク

ネットワークをグラフ、ポートナンバリング、プロセッサの列の三つ組み (G∈G, {f_v}, (p₁, p₂, ...)) で定義する。

ネットワークの configuration c(v) とは G の頂点 v から p_deg(v) の状態を対応づける関数とする。

c₁, c₂ が configuration の時、 c₁ が 1 step で c₂ に遷移する ( $c_1⊢c_2$ ) とは次の二つの条件を満たすことを言う。

1. ある辺 e=(u,v)∈E(G) とメッセージ a,b∈ A が存在し、 (a,b,c₂(u))∈ M_deg(u)(c₁(u),f_u(e)) と (b,a,c₂(v))∈ M_deg(v)(c₁(v),f_u(e)) が成り立つ。
2. ほかの w ∈ V(G)-{u,v} に対しては c₁(w)=c₂(w)

つまり、 configuration が 1 step 推移するとは、頂点 u, v がメッセージ a, b を交換して状態を遷移する一方、他のプロセッサはそのままであること を言います。 なお、この定義では遷移の過程で必ず一つだけのメッセージが送られているこ とを保証することになります。 これを利用すると他の分散システムの定義に比べ特殊なことができます(後述)。

計算の定義

c₀から遷移可能な configuration は複数あり、また遷移した configuration からもまた複数の configuration に遷移が可能である。 繰り返し遷移可能な configuration を並べると、c₀ を根とした 有向木になる(但し、木の頂点のラベルを configuration とした時、同一のラ ベルの存在を許す)。 また、 $⊢$ の反射推移閉包を ${⊢}^{*}$ で表します。 $c_0{⊢}^{*}c$ は c₀ の木の中に c が存在すること、つまり、 $\left.(∃c_1,c_2,...,c_k\right)\left[c_0⊢c_1⊢c_2⊢...⊢c_k⊢c\right]$ という関係を意味します。

c₀ からの計算とは c₀ から到達可能な c₀ の木の極大の path を示します。 これは根から始まり、最後の configuration からの遷移が無い場合だけ有限 になります。

Covering

グラフ H,G ∈ G と p:V(H)→V(G) に対して、 H が p による G の covering であるとは、 H に含まれる各頂点 v に対し て、p の定義域を N_H(v) に限定すると N_G(p(v)) に 対して一対一対応になることを意味します。

例えば H として頂点 6 のリング状グラフ、 G として頂点 3 のリング状グラ フとします。 それぞれ、頂点のラベルが {1,2,3,4,5,6} と {a,b,c} とし、p は p(1)=a, p(2)=b, p(3)=c, p(4)=a, p(5)=b, p(6)=c とします。 すると、頂点 1 に対しては　N_H(1)={2,6}, N_G(p(1))={b,c} で、 p(2)=b, p(6)=c は一対一になります。

また、単に H が G の covering であるとは、このような条件を満たす p が 存在することを意味します。 H と G が有限の共通 covering を持つとは、 H と G の covering となる K∈G が存在することを言います。 H が G の covering で、 H と G が同型でない時、 H は G の proper covering と言います。

例えば 4 頂点のリング状グラフと 6 頂点のリング状グラフに対して、 12 頂 点のリング状グラフは有限の共通 covering となります。

center の構成に関する結果

定義

プロセッサの列 (p₁, p₂, ...) の各プロセッサが z_d, c_d という異なる状態を持っている時、 c₀ が uniform initial configuration であるとは、 c₀(v)=z_deg(v) であること、 c₀ が centered configuration であるとは、 ただ一つの頂点 v にとって、c₀(v)=c_deg(v) であること、 c₀ が forbidden configuration であるとは、 二つの異なる頂点 v,w に対して、c₀(v)=c_deg(v), c₀(w)=c_deg(w) であることです。

(p₁, p₂, ...) が G で deterministically establishes a center とは c₀ からの全ての計算にお いて centered configuration を含み、また forbidden configuration を含まないこと。 また、(p₁, p₂, ...) が G で nondeterministically establishes a center とは c₀ からの ある計算が centered configuration を含み、 また全ての計算において forbidden configuration を含まないこと。

定理 4.1

全ての完全グラフに対して deterministically establishes a center となる プロセッサの列が存在する

証明のアイディア

計算モデルにおいて、メッセージが常に一つだけしか流れないことが保証され ているため、対向の頂点同士において同時にメッセージを出すことは無く、必 ずどちらか一方がメッセージを出すことが保証される。 これを利用して後にメッセージを出す方は center の状態に入らないようにす れば、最終的に一つの頂点だけが center の状態に入ることができる。

なお、現実的な分散システムにおいて、常に一つだけメッセージが流れること は保証されない。 従って、この定理は計算モデルに依存した結果であると言える。

定理 4.2

4 頂点のリング状ネットワークを S₄ で表す。 この時、 S₄ で determinstically established a center ができ るプロセッサは存在しない。

証明のアイディア

頂点の configuration が偶数時間に A,B,A,B と交互に同じ状態になっている と仮定します。これは一番最初は A=B ですが条件を満たします。 このような前提に対して、次の偶数時間に同じ条件が成り立つような遷移があ ることを示す。

これは A と B の組を頂点と考えると、同じ状態なら同じ通信を行う configuration が存在するという論法。 一方の A が B にメッセージを送ると、次の step で 一度に一つのメッセージしか存在しないことを利用して単独のプロセッサだと 相互に異なる状態に入れるが、二つ以上のプロセッサの組だと組の数分のステッ プで通常の同期モデルにおける同時送信と同じ現象が生じる。

非決定性(nondeterministic)は実用上あまり意味が無いので、定理 4.3, 4.5, 4.6 は省略。

定理 4.4

G に含まれる任意の木に対して deterministically establishes a center できるプロセッサの列が存在する。