第 7 回分散アルゴリズム

本日の内容

7-1. 前回の復習
7-2. 分散アルゴリズム

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

並列計算も分散アルゴリズムも、複数のプロセッサが協調して動作することは同じです。並列計算とは、問題に対してプロセッサ群によるネットワークを構築し、問題を解決するための行う計算を指します。一方、分散アルゴリズムは既に存在するネットワーク上のプロセッサが協調して行う計算で、計算の目標はそのネットワーク自体に存在する問題の解決です。分散アルゴリズムの例として、複数のプロセスによるデータベースアクセスのデッドロックの解消や、ダイクストラのダイニングフィロソファー問題などが知られています。さらに、これだけではなく、インターネットの管理などには分散アルゴリズムが積極的に使用されています。

データベースのデッドロック問題

WWW などでは多くのアクセスに対して並列的に処理が行なわれます。また、 WWW での処理においてしばしばデータベースが使用されています。例えば、ショッピングモールサイトなどで、あるユーザ X が A の条件を基に B を書き換える操作を要求するとします。一方、別のユーザが B の条件を基に A を書き換えるとします。この時、この X と Y が同時に発生するとデッドロックが発生します。つまり X が A を確保した後、 B を書き換える前に、 Y が B を確保し、 A を書き換えようとしている状況が発生します。

デッドロックを実際にどう解決するかはデータベースの問題ですが、各 X や Y がデッドロック状態に気づくためには、それぞれの操作を行なうプログラム内で処理する必要があります。つまり同一の Web アプリケーションプログラムを動かす複数のプロセスが互いにデッドロックを検知する必要があります。これは相互に要求している資源の関係をプロセス同士が通信を行ないながら取得し、要求の関係からデッドロックを検知します。

ダイニングフィロソファー問題

ダイニングフィロソファー(哲学者の食卓)問題とは丸テーブルに哲学者が座って食事をする際に生じる抽象的な問題です。食卓には皿、フォーク、皿、フォークと順に丸く配置されているとします。その際、哲学者は右または左のフォークを取って食事を始めるとします。各哲学者はどのようにして右または左を決定するのでしょうか？誰か一人がどちらかのフォークを取れば隣の哲学者はそれと同じ側のフォークを取ることで全員がフォークを手にすることができます。しかし、その一人をどのようにして決めるのでしょうか？このようにダイニングフィロソファー問題は相互にどのようにしてフォークを取るかを哲学者が思考し、いつまでも食事を始められない状況をどのように打開するかと言う問題です。

RIP(Routing Information Protocol)

インターネットの経路制御には経路表が使われます。経路表にはネットワークアドレス、転送先アドレス、メトリック（距離）が記述されています。この経路表をネットワーク上で相互に通信し合いながら計算するプログラムをルーティングプロトコルと呼びます。

RIP というルーティングプロトコルは距離ベクトル型のプロトコルです。これは各RIPの動いているルータは以下のようなプロトコルを実行します。

自分の経路表を定期的にネットワークに流す
ネットワークを流れている経路表を受信し、各ネットワークアドレスのエントリ毎に流れていた経路表と自分の経路表を比較する。流れている経路表のメトリック+1 と今の自分の経路表のメトリックを比較する。流れている経路表のメトリックが小さい時は自分の経路表の情報を上書きします。

このようにインターネットではルータが相互に同一のプログラムを実行してネットワークの制御を行なっています。

番号を振る分散アルゴリズム

分散アルゴリズムはネットワークを固定しません。そのため、条件を満たす任意のネットワーク上で動作できるよう、各プロセッサでは同一のプログラムを動かします。但し、多くの分散アルゴリズムでは各プロセッサにはユニークに番号が振られていることが仮定されています。一方、この番号を振ること自体も分散アルゴリズムの問題になり得ります。

前提条件

この節では分散アルゴリズムの例を考えるため、番号を振る分散アルゴリズムについて考えます。問題の前提条件として各プロセッサには番号が振られていないとします。また、全頂点は相互に一対一に接続され、互いに通信ができます(完全グラフ)。ここで全プロセッサ数を N とすると、各頂点の持つ通信線は(N-1)本あるため、各プロセッサは全プロセッサ数 N を知っており、また通信線には 1 から N-1 まで番号が振られていて通信相手を全て区別することが可能です。

この状態で全頂点に同じプログラムを与えプログラムが終了したときに各プロセッサはそれぞれ異なる番号を所持しているようにできるかがこの問題です。

じゃんけん

始めに隣接している二つのプロセッサに同じプログラムを走らせて、どちらかが 0, どちらかが 1 を出力するプログラムを考えます。これを行なうのにじゃんけんを考えます。じゃんけんではプロセッサは 0,1,2 のどれかをランダムに選びます。そして、二つのプロセッサ同士で選んだ値を比較します。比較は 0<1<2<0 の順番とし、小さい方が 0, 大きい方が 1 を出力します。

さて、この場合、勝負が着くまで繰り返すとして、繰り返し回数の平均値を求めましょう。

一回の勝負で決着が着く確率は $\frac{2}{3}$ です。
二回の勝負で決着が着く確率は $(1 - \frac{2}{3}) \frac{2}{3}$ です。
三回の勝負で決着が着く確率は ${(1 - \frac{2}{3})}^{2} \frac{2}{3}$ です。
n 回の勝負で決着が着く確率は ${(1 - \frac{2}{3})}^{n - 1} \frac{2}{3}$ です。

この時、決着が着く平均繰り返し回数 E は次で得られます。

E = 1 \frac{2}{3} + 2 \frac{1}{3} \frac{2}{3} + 3 {(\frac{1}{3})}^{2} \frac{2}{3} ...

この無限和に対して、 n 項目までの和 E_nを考えます。

E_{n} = 1 \frac{2}{3} + 2 \frac{1}{3} \frac{2}{3} + 3 {(\frac{1}{3})}^{2} \frac{2}{3} ... + n {(\frac{1}{3})}^{n - 1} \frac{2}{3}

これに 1/3 を掛けると次のようになります。

\frac{1}{3} E_{n} = 1 \frac{1}{3} \frac{2}{3} + 2 {(\frac{1}{3})}^{2} \frac{2}{3} + 3 {(\frac{1}{3})}^{3} \frac{2}{3} ... + n {(\frac{1}{3})}^{n} \frac{2}{3}

これを辺々で引き算すると次が得られます。

E_{n} - \frac{1}{3} E_{n} = \frac{2}{3} + \frac{1}{3} \frac{2}{3} + {(\frac{1}{3})}^{2} \frac{2}{3} ... + {(\frac{1}{3})}^{n - 1} \frac{2}{3} - n {(\frac{1}{3})}^{n} \frac{2}{3}

\frac{2}{3} E_{n} = \frac{2}{3} \frac{1 - {(\frac{1}{3})}^{n}}{1 - \frac{1}{3}} - n {(\frac{1}{3})}^{n} \frac{2}{3}

このn の極限をとると E が次のように求まります。

\frac{2}{3} E = \frac{2}{3} \frac{1}{1 - \frac{1}{3}}

E = \frac{3}{2}

つまり、平均 3 回の繰り返しで決着が着くことがわかります。

次に二人ではなく、 n 人でジャンケンで順番を決めることを考えます。全員でジャンケンをする時、あいこになる確率は次で求められます。

Pr [あいこ] = Pr [全員が同じ手] + Pr [3種類の手が出る]

= Pr [全員が同じ手] + (1 - Pr [全員が同じ手] - Pr [全員が二種類])

= 1 - Pr [全員が二種類]

= 1 - {(\frac{1}{3})}^{n} (\begin{matrix} 3 \\ 2 \end{matrix}) \sum_{i = 1}^{n - 1} (\begin{matrix} n \\ i \end{matrix})

= 1 - {(\frac{1}{3})}^{n} 3 (2^{n} - 2)

= 1 - 3 ({(\frac{2}{3})}^{n} - 2 {(\frac{1}{3})}^{n})

よりあいこの確率は n が大きくなると 1 に近付いていきます。すると決着の着く回数も n が大きくなるにつれ大きくなっていきます。これはあまり効率のよい方法ではありません。

ダメな例

次に全員と一回ずつ二人だけのジャンケンの総当たり戦をし、集計することを考えます。二人だけのジャンケンだと勝負が着くまで平均 3/2 回、 n 人だと 3n/2 回で収束します。但し、A,B,C の三人で行う場合を考えると、 A は B に勝ち、 B は C に勝ち、 C は A に勝ちとサイクルができてしまうことが考えられます。この場合、全体で勝負が着きません。勝敗の着き方は 2³ で 8 通りありますが、この中でサイクルは右まわりと左まわりの 2 通りありますので、 1/4 の確率で勝負が着きません。 n 人でサイクルが発生する確率は以下のようになります。

1 - Pr [あらゆる組み合わせでサイクルが発生しない] > 1 - Pr [どの 3 人でもサイクルが発生しない] > 1 - {1 - \frac{1}{4}}^{n}

これでは n が大きくなると勝負がつく可能性が 0 に収束してしまいます。

リーダ選出

ここまで分散的に番号を振ることを考えてました。しかし、このような問題の場合、逆にサーバ／クライアントモデルを考えると容易に番号を振ることができます。つまりあるプロセッサだけがサーバとして機能していれば、このサーバが接続先に(通信線に付けられた)番号を送ることで全プロセッサに番号を振ることができます。そこで、分散アルゴリズムとしてサーバを一台決定することを考えましょう。二つのプロセッサ毎にジャンケンで勝敗を決めていき、一回でも負けたプロセッサはクライアントになることにします。これはトーナメント戦になるので、全体で n-1 戦のジャンケンをするとサーバのプロセッサが一つ決まります。

Apple Talk

Apple社の Macintosh はネットワークに接続すると特にアドレスの設定をしなくても相互に通信が可能です。これは以下のような手順(プロトコル)によりアドレスを自動的に付けているからです。

1 から 126 の数をランダムにえらぶ
アドレス 255(全員が傍受するブロードキャストアドレス)に選んだ番号を使用すると広告する
一定時間傍受し、番号が重複している報告があるかどうかを待つ。
重複しているとの報告があったら step 1 に戻る
一定時間、重複の報告が無かったら選んだ数をアドレスに選ぶ

Apple Talk というプロトコルはシリアル、あるいは Ethernet 上で使用されますが、どちらも何十台も同一セグメントに Macintosh を配置しませんので、これは十分機能します。但し、このプロトコルからわかるように 126 台以上 Macintosh が存在することはできません。

Bar-Iran & Zernik のアルゴリズム

J. Bar-Ilan and D. Zernik "Random Leaders and Random Spanning Trees", "Distributed Algorithms", Lecture Note in Computer Science. Vol. 392.(1989) pp. 1-12

この論文に載っているアルゴリズムは順に番号を振るものではなく、バラバラの数を振るものです。これは Apple Talk と同様、乱数を単に選ぶだけです。但し、全頂点数 n に対して、乱数を選ぶ範囲を 1 から n³ までとします。この時、うまくいく確率を次のように見積もります。

2 つの頂点が互いに異なる確率: $1 - \frac{1}{n^{3}}$
他の n-1 個と互いに異なる確率: ${(1 - \frac{1}{n^{3}})}^{n - 1}$
これが全ての n 頂点で成り立つ: ${({(1 - \frac{1}{n^{3}})}^{n - 1})}^{n}$

これに対して以下の公式を適用します。

{(1 + \frac{x}{n})}^{n - 1} \leq e^{x} \leq {(1 + \frac{x}{n})}^{n}

以下のように変形することで成功確率を見積もります。

{(1 - \frac{1}{n^{3}})}^{n^{2} - n} = {(1 - \frac{1}{n^{3}})}^{(n^{3} - 1) \frac{n^{2} - n}{n^{3} - 1}}

\geq e^{- \frac{n^{2} - n}{n^{3} - 1}} = e^{- \frac{n}{n^{2} + n + 1}} \geq e^{- \frac{1}{n}}

これは n が大きくなると 1 に近づきます。

分散アルゴリズムを動かすには

以上、いろいろな番号を振る方法を考えてきましたが、全て何らかの前提条件を必要としていました。これに関してまとめます。

前提条件は必要か: 乱数を使用しない 2 プロセッサのネットワークを考えます。両者のプロセッサに全く違いが無い状態で、二つのプロセッサに同じプログラムを与えると、二つのプロセッサは全く同じ動作をします。すると、出力も同じになるため、両者が自律的に異なる番号を得ることはできません。つまり、乱数を使わず、他の前提条件もないネットワークでは異なる番号を振ることはできません。
ネットワークトポロジ: 前提として完全グラフを想定していました。複数の通信線はそれぞれ識別するための符号が振られてますので、通信線の本数を数えることができます。完全グラフでは他のすべての頂点への辺がありますから、完全グラフであると言う情報により全頂点数がわかることになります。それ以上に一般的なネットワークにおいてすべての頂点間で直接通信が可能であることを仮定するのは無理があります。そのため、分散アルゴリズムとしてはネットワークトポロジを固定しないことが望ましいです。
問題設定: ここでは「1 から順に番号を振る」他に、「個別に異なる番号を振る」や「一つだけサーバを決める」なども議論しました。これらの等価性は厳密にわかってませんので、これらは別々の問題として取り扱うべきです。
前提条件: 前提条件として、異なる通信線は異なる符号により区別できるということを挙げましたが、全頂点数や乱数などを使用したアルゴリズムも紹介しました。これらの条件が必須なのかなくても可能かは議論が必要です。

通常の分散アルゴリズムでは個別の識別子や頂点数などを前提とするのが普通です。今回のように個別の識別子を求めるには、それらを前提にできません。各プロセッサが識別子を持たないネットワークを匿名ネットワーク (Anonymous Network)と言います。なお、ここでの議論により全くの匿名ネットワークでは番号を振ることができないことがわかっています。そこで、何らかの入力を与えて番号を得ることを考えます。

ネットワークに対する入力の与え方により研究の切口が変わってきます。次回はこの研究の先がけとなった Angluin の研究を紹介します。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 7 回 分散アルゴリズム