分散アノレゴリズムについて
山下雅史
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111.

り，それらを自由に利用することもできないし，まはじめにt.::. ,計算機が互いに結合され，計算機システムが複雑化す

3. 問題を解決するのに必要なデータ(計算機が送信るにしたがって，さまざまな並列計算機システム向けのしたメッセージ履歴)は，それぞれの計算機に分散アルゴリズム論が展開されてきており，この並列アルゴしている.

リズム特集でも，共有メモリ結合型やハイパーキュープ

広域ネットワークのように，システム全体の状況をあ等のトポロジーを持つメッセージ突換型のマルチプロセ

る特別な計算機(プロセス)が把握し，制御できないよ

ツサシステムをはじめ，スーパーコンピュータやシストうなシステムを分散(裂)ジステムと言い，分散システリックアレ一等の並列計算機システム用のアルゴリズムム用のアルゴリズムを分散アルゴリズムと呼ぶ.

が紹介されている.ある特定の並列計算機システム用のアルゴリズムを論じるには，その並列計算機システムの特徴を反映した抽象的な並列計算機械を定義し，その上で問題解決を議論することになるが，このとき，

2.

問題

並列アルゴリズムと分散アルゴリズムの問題設定の相違を，基本的なグラフ問題である，最小生成木問題

1. この並列計算機械のことを十分に知っている，(minimumspanningtreeproblem) を例にとって説

2.

明しよう.

この並列計算機械を自由に使用できる，

3. 問題を解くために必要なデータはすで‘に揃っていコスト付き無向グラフ G=(V ， E ， c) が与えられたときに，コスト最小の生成木 T=(V ， E T ) を抽出する問題が最小生成木問題である.ここに ， c(e)(eEE)る，等は自明な仮定として採用される.これらは，集中型シは枝 e のコストを表わし，生成木 T のコスト c(T) はc(T)= 1: c(e)ステム上の計算の典型的な特徴である.

eeET

しかし実際には，これらの項目を仮定て‘きないような計算機システムも存在する.たとえば，

TCP/IP とで与えられる.

最小生成木問題の並列アルゴリズムを議論する場合に呼ばれるプロトコルで結合されている広域(計算機)ネ

は，入力 G を与えることは，それを解くための計算機械ットワークを考えよう.これには世界中の 15万台を超え

M と，その上で G がどのように保持されているか(あるるワークステーションが参加している.このように巨大いはどのように入力されるか)決めることである.計算なネットワークであるがつのシステムに組織し，利終了時に，結果である T は，ある特定のメモリ(群)に用することもしばしば行なわれる.たとえば，われわれ指定した要領で格納されている(あるいは，計算終了まは，この上に構築された電子メールシステムを利用するでにある順序で出力する).

ことで，世界中のどの地点、にもほとんど瞬時にメールを設計者は，送りつけることができる.このネットワーク上で，たと1. Mを熟知し，えば，一定時間内に流れたある話題に関するメッセージ

2. Mを自由に利用でき，数を計数したいとしよう.このとき，

1. このネットワークの現在の姿について正確に知ることはできないし，

3.

すなわち，アルゴリズムのG を完全に知っている，と仮定されている.
分散アルゴリズムにとっても，最小生成木問題は基本

2. 各計算機はそれぞれ異なる方針で運営されてお的な問題である.たとえば，ある計算機聞がネットワー

ク N に参加するすべての計算機にあるメッセージを伝え
やましたまさふみ広島大学工学部第 2 類る問題である，放送問題 (broadcast problem) を考え

干 724 東広島市鏡山町

る(問題を解決したいと思い，アルゴリズムを起動する

3
82 (28)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

計算機却を始動計算機 (initiator) と呼ぶ).

ネットワ

ーク N のトポロジーを G=(V ， E) で表現する.ここで，V は計算機の集合であり ，(u ， ψ) EE は，計算機 u とむが直接メッセージを交換できる，すなわちu と u の間には双方向の通信リンクが存在する，ことを示す.次のでに)分散されてある問題を解決するために開発されるのである.
本解説では，分散システム，分散問題や分散アルゴリ
ズムの定義には立ち入らないので，これらの定義はたとえば，文献[ 1]を参考にされるようお願いする.

ようにして，放送問題を解くことができる.

3.

1. 始動計算機却は接続するすべてのリンクに，伝えたいメッセージ a を送信する.

以前に a を受信したことがないならばを除く接続しているすべてのリンクに a を送信する.

分散システムではメッセージ通信は高価であると考えられているので，~、くつかの自律的なプロセッサとプロセスをサポートするデータ蓄積装置，かつ/またはデータベースシステムから構成されるもので，全体として1 つの目標を達成するように協調動作するシステムであこのアルゴリズムでは最悪の場合 il(IEI) 回のメッセできれば O(IVI) 回のメッセージ送信でこの問題を解決したい.
このために ，間分散システムは，2. メッセージ a をリンク J から受信した計算機は，ージ送信が必要となる.

時

る，と定義される[ 5]. プロセス間の情報の交換は通信ネットワークを介するメッセージ通信によって行なわれる.メッセージ転送遅延は常に存在し，有限であるが変化する.分散システムには，通信遅延が局所的な計算

T=(V ， E r ) を G の生成木とし，各計算時間に比較して十分に長く，しかもそれを事前に見積も機 u は u に接続する T の技を認識していると仮定しようることが困難である，と L 、う特性がある(高速 LAN の(u は T 全体を知っている必要はな L 、).このとき，上の上に作られた分散システムではこの性質が近似的にしかアルゴリズムで，メッセージ a の送信を T の枝だけに限成立しないこともある).

定しでも，放送問題は解決でき，しかも，メッセージ数散システムに属するすべてのプロセスがある時点、におけは O(IVI) ですむ.なお，この{7JJ では，最小生成木がとる分散システム全体の状態を共通に知ることはできなりわけ必要ではなく，どの生成木でもかまわないのだ

い.この点が分散アルゴリズムの設計と，対象の全体像が，たとえば，枝のコストとして通信にかかる費用を考が常に把握できる集中型システムで実行される通常のア

えれば，最小生成木を用いる放送は，費用最小の放送とルゴリズムの設計との本質的な相違である.

通信遅延が存在するので，

分たとえば，あるプロセス i が，分散システムがデッドL 、う意味を持つ.

以上のような動機から最小生成木問題を考察しようとロックしているかどうか確認したいと考えたとしよう.

すると，問題例は次のように与えられるだろう.解くべ

このためには，分散システム全体の状態(大域状態)がき問題例であるコスト付きグラフ G=(V ， E ， c) は，わかれぽよい(大域状態を求める問題は大域的スナップ

その問題を解くアルゴリズムが実行される分散システムのショット問題 (globalトポロジーである.また，各計算機 u は，最初る).

u に局

並列アルゴリズムと分散アルゴリズムとは，ともに複数の計算機上のアルゴリズムという点で、類似のアルゴリ
ズム論のように錯覚しがちであるが，並列アルゴリズム

では，問題を(問題とは関係のない)並列計算機を利用して解決するのに対して，分散アルゴリズムでは(自分ネットワーク全体に関する問題を局所的な情報を交換して解決する，と L 、う意味で全く異“良い分散アルコリズムがないのなら，どうして分散して解く必要があるのか?"ある研究会で耳にした質問である.分散アルゴリズムは，並列アルゴリズムのよう分散(並列化)して問題を解くためではなくす
1992 年 8 月号

れは，不可能ではないとしても，全く現実的な解法ではない.分散システムを止めることなしに，プロセス i が他のプロセスの局所状態を回収し，それから大域状態を復元しようとすると，さまざまな時刻の局所状態を組み合わせることになり，保証はない口.

“正しい"大域状態が復元できる

これが，大域的スナップショット問題の困難な所である.このような問題は動的分散問題と呼ばれており，分散アルゴリズムの実行中に問題例が刻々変なるものである.に，snapshot problem) と呼ばれ分散システムを十分長い間止めることができるなら，この問題は簡単に解決できる.しかし，こ所的な情報しか持たない.

がその一員である)，

もしも，化する.

大域的スナップショット問題に戻って，各プロセス J1) “正し L 、"という用語の正確な定義は意外に難し
い.文献 [3 ]を参照せよ.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(29)383が，大域的スナップショットを取る時刻 T をすでに知らC( e ,) <C( e2)" を満たすならば論理時計である.論理時されていると仮定しよう.このとき，各プロセス j が時計によって，各プロセスは事象の前後関係について，矛刻 T の局所状態を i に伝えることで，問題が解決できる盾なく知ることができる.

ように思われる.

しかし，C j が正確でない限り，い.

そして，プロセス j が参照する時計問題が解決したことにはならな時計合わせは，多くの場非常に困難で，合，不可能な仕事なのである.たとえば，ある親時計 Cに各局所時計 C j を合わせるというような単純な方法はうまく L 、かない.通信遅延が無視できず，しかもその値を事前に見積もることができないのでC を管理するプ

Lamport[3]は，多くの目的の場合，分散システムの時計が果たす役割の本質的な部分が論理時間の提供であることを論じている.
論理時計は以下のようにして実現できる.各プロセス

Jは.，

1. 受信事象以外の事象が生起した直後に C j に 1 'を加える.

2.

・メッセージを送信するときには，タイムスタンロセスから C の現時刻 t を送信してもらい，通信遅延のプ ts=Cj をメッセージに付加して送信する.

見積を加えて Cj にセットするというような方法は取れ・タイムスタンプ ts を持つメッセージを受信しない 2>.

たときには ，時間の役割は，る.

1. 一連の事象が起きた順序を定める規準を提供し，したとする.

2.

2 つの事象の生起間隔を測る尺度を提供すること，

4.

Cj を max{C j ， ts}+lまで進め

この受信事象は更新された時刻 Cj に生起知識である.前段で述べたように，分散システムでは共通の分散アルゴリズムの対象となる問題は分散システムの時計を各プロセスが参照することが困難であり，したが大域的な知識にかかわる問題であり，ある問題を解くアって， (2) の目的で時聞を提供することは困難である. (1)

ルコリズムの実行過程は，その問題を解決するために必だけの目的で時聞を提供する時計を論理時計(l ogical

要な知識を効率よく収集する過程と考えられる.よいアclock)

ルゴリズムであればあるほど，少量の良質の知識を手際という.

もう少し，詳しく説明しよう.

プロセスの実行過程を(生起した)事象の列で表現する.事象の集合の聞に，次のようにして自然、な半順序関係→が定義でき，これを前後関係 (happened beforerelation)と呼ぶ.

e2 より先に生起したとき，かっそのときに限り ， e ,一→ e2.

2. 事象 e ， と事象 e2 がある同ーのメッセージの送信および受信事象であれば e ， →匂・かつら→ e8

ならば q→ e 3 •アルゴリズムは研究されているが，たまに故障する RA
M や PRAM上のアルゴリズムはあまり聞かない.一方，分散システムにはハードウェアやソフトウェアに起らの多くには再現性がないのでデバッグもままならないのが現実である.紙面の制約から解説する余裕がないがすなわち，考えられる限り最弱の前後関係から導かれプロセス J の時計 C j で計った j の事象 e が生起した時刻を Cj(e) で表現し，事象 eがプロセス j の事象ならば C( e)=Cj(e) と定義することで，大域時五十 C を定義する .C は条件“ e ，→のならば2) 以下の 2 条件は時計を“近似的"に合わせるための十分条件である.

1. 任意の 2 つのプロセスの局所時計の 1 秒 (tick­ing rate) の差異は定数で押さえられる.

2. 任意の 2 つのプロセスにおいて，それらの聞の通信遅延のゆらぎは定数で押さえられる.

384 (30)

常に作動すると仮定されている.丸め誤差等を考慮した悶する多くの故障の可能性が内在しており，しかもそれ

事象 e }， e2 および e 3 に関して e ，→e2 ，る半順序関係が→である.

2 つのプロセス i と j を結ぶ通信リンク t は，信頼性が低く，メッセージがその中で消えるかもしれないと仮定する.通常のアルゴリズム論では，抽象計算機械は正1. 事象 e ， とのが同じプロセスの事象ならば ， e ， が3.

よく交換することによって問題を解決する.

少々の故障に影響されることなく正しく問題を解決す
る耐故障アルゴリズム(fault tolerantalgorithm) の検討は，この分野の重要なテーマの l つとなっている[4].
簡単のために，リンク J の通信遅延が常に l 秒であると仮定し，プロセス i が j に事実。を確実に伝えようと考えたとする.このためのアルゴリズムは以下のようなものであろう.
1.は，j からメッセージ ack が到着するまで ，を運ぶメッセージを 2 秒間隔で繰り返し送信する.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

2.

j は i からのメッセージが到着するたびにackを返送する.

させることによって，アルゴリズムの構成を試みるのは，有力なアプローチの 1 つであり，このようにして作このアルゴリズム RELIABLE-SEND によって ，i\ttþ の送信を確実なものにできる.

られたアルゴリズムを知識ベースプロトコルと呼ぶ.知識ペースプロトコルが用いる ，もう少し複雑な問題を考えてみようが事実併を jに送信しは“ j がゆを知っていること"を，一方 jK h 1/f という形の式を扱う様相論理は知識論理 (knowledge logic)と呼ばれ，上に述べたアルゴリズムの構成の側面を含め，さまざまは“ i が“ j がゆを知っているということ"を知っていな側面からの研究が進められている.

ること"を，それぞれ確信したいと考えたとする.このK h 1/f=辛苦T，すなわち，成立しない事実を知っていること

ような状況はと J が同じデータを参照しているとはない，ことを自然な公理として採用しているが，これきがそのデータに変更を加えようとしてを公理として採用しない様相論理体系として(正しくなj に了解を求めるときなどに現われる.プロセス h がある事実事Tし、事実の)，を知っていることを K h 1]f で表現することにする.この論理 (beHef logic) がある [2 ].

知識論理では，思い込みも含めて扱う論理体系である信念

とき，参芳文献

1. Kjtþ を i の知識にし，[1] 荻原，増津:分散アルゴリズム，情報処理学会誌

2. KiKj併を j の知識とする，

31 , 9 (1990)1245‑
1256.

ことが目的となる.
故障が起こらな L 、というシナリオに沿って進んでみよ[2] Halpern , J.Y. , “ Reasoning about know.

j はがを受ledge:an overview" , Proc. of the 1986 Gon.

信し ， KjØ を返送するは K/fI を受信する.このとference on Theoretical Aspects of Reasoning

きは Kj併を確信できるが ， K/fI が i に到達したこ

ed.J.Halpern) Monterey ,About Knowledge(とを j は確信できな L 、から

Calfornia (March 19-22 , 1986) Morgan Kauf.

うはゆ(運ぶメッセージ)を送信する

j は，KiKjtþ を確信できない.そこでは K/fI を受信したことを伝えるために KiKJtþ を j に送信する

j は KiKjtþ を受信し，目mann , 1
986.
[3] Lamport , L. ,“ Time , clocksandorderingof

的を達成できる.ここで ， K h 1/f と V は異なる知識である

events i
nadistributed system ヘ

ことに注意してほしい.すなわち，たとえば KiKjKitþ21 , 7 (1978)558‑
564.と Kitþ は異なる知識であり，混同は許されない.
なお，メッセージが脱落することがあっても最終的にM. , “ The Byzantine generals problem ヘ ACM
on Programming Language andTransactiυ ns

メッセージ仇 Kjtþ， KiKjtþ の送信を確実にする必要が1982)382‑401.
Systems4, 3 (SEND を適用する.

したがってack どメッセージなを i と j の聞で交換する必要があるが，省略する.
このように，問題を解決するために必要不可欠な知識を理論式で具体的に表現し，それらをメッセージに対応

1992 年 8 月号

ACM

[4] Lamport , L., Shostak , R. E. , and Pease ,は J が KiKjtþ を知ることができるようにするためにはあり，このため，たとえば，アルゴリズム RELIABLE­Comm.

[5] Sloman , M. , and Kramer , J. “ Distributed
Systems and Computer Networks" , Prenticeｭ
Hall International , Hemel Hempstead , Hert.
fordshire , U.K.(
1987). (斉藤監訳:分散システムと計算機ネットワーク，丸善株式会社(1 988) ).

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

)385(31