解説分散アルゴリズム
──多数のコンピュータが自律的に協調するアルゴリズムの理論──角 川 裕 次
Hirotsugu KAKUGAWA

理工学部数理情報学科教授

Professor, Department of Applied Mathematics and Informatics

どは特に，日々の生活で欠かせない分散システム上1．はじめにのアプリケーションです．

2019 年 4 月に数理情報学科に着任いたしました．

今日では Raspberry Pi や Arduino など，高性能で計 算 機 科 学 の 1 分 野 で あ る，分 散 ア ル ゴ リ ズ ム

ソフトウエア開発が容易なワンボードマイコンや，（distributed algorithm）の基礎理論を専門としていまそれらに搭載可能な小型の無線通信ボードなどが低す．本稿ではその中でも特に，長年に渡って研究を価格で入手できるようになり，分散システムは自分進めてきている自己安定分散アルゴリズムを簡単にで構成できる身近なものになりつつあります．
（私紹介します．

がこの分野の研究を開始した 30 年前とは随分と状況は変化してきました．）

2．分散システムとは分散システムとは，複数の構成要素からなるシス

3．分散システムが持つ 3 つの性質テム（系）であり，システムを集中制御するものが大規模な分散システムには，以下に説明する非同

特になく，構成要素が互いに相互作用をしながら変期性，局所性，情報伝達遅延性の 3 つの性質のため化してゆく，あるいは変化しないような恒常性を実に，後述の分散アルゴリズムの設計が困難となって現するものです．そのようなものには様々なものがいます．

あり，多細胞の生物，蟻や鳥などの群れ，社会など

非同期性：動作の速度とタイミングがバラバラでも分散システムの例ですが，本稿では多数のコンピあることをいいます．全てのコンピュータは同じ処

ュータで構成されるネットワークを対象にして説明

理速度とは限りませんし，通信速度もまちまちなのを進めます．具体例として，インターネット，無が普通です．特にネットワークが混んでいるときと線 セ ン サ ネ ッ ト ワ ー ク（WSN），IoT（Internet of

そうでないときでは，通信速度が違うことが往々にThings），モバイルアドホックネットワークなどがして起きます．このようにネットワークの構成要素挙げられます．また，オンラインショッピング，電は，それぞれ随分と違った速度で動作するのが普通

子メイル，SNS，動画サイト，銀行のオンライントです．そして分散システムの規模が大きくなるほどランザクションシステム，オンラインストレージなこの傾向は顕著です．従って，大規模な分散システ―１―ムでは，全ての構成要素が足並み揃えて一定の処理かかるものだと，その後をどう頑張っても正確かつ速度で動作することは期待できません．

高速動作するソフトウエアは得られません．

局所性：得られる情報は，ネットワークの近接に分散アルゴリズムとは図 1 に示すように，それぞ限られること，すなわち局所的であることをいいまれのコンピュータで動作するアルゴリズムの集合体

す．どのコンピュータも，通信路で直接的に接続さであり，互いに通信をしながら処理を進めてゆく点れているコンピュータとは通信できます．しかしそに特徴があります．しかし分散システムには上述のれ以外のコンピュータとの通信は，いくつものコン非同期性，局所性，情報伝達遅延性があるために，ピュータを経由して通信する必要があります．

その設計は容易ではありません．さらに加えて，コ

情報伝達遅延性：情報の通信には時間がかかり，最新情報をすぐには得られないことをいいます．ネンピュータの故障や通信障害も発生するとなれば，その難しさは更に増します．

ットワークの高速化が進んでいるとはいえ，通信にこのような困難さのもとで，どのようにして分散はいくらかの時間がかかります．上述の局所性よ

アルゴリズムを設計すれば良いのでしょうか．これり，離れたコンピュータの情報を入手しようとすれが私の取り組んでいる研究テーマです．

ば情報はいくつものコンピュータを経由して伝達す

難しさを具体的にイメージできるよう，以下の問る必要があり，情報を得た瞬間でも，それはもう古題を考えてみて下さい．あるアイドルグループのフい情報になっています．例えば，夜に星空を見上げァンクラブの会員の総数を調べたいとします．問題て星を観察したとします．でもそれは，何光年もかの詳細な設定は以下の通りです．ファンクラブは各かって地球に届いた光をその瞬間に観察しているだ

地に地域事務局があり，それぞれの地域事務局はそけであり，その瞬間の宇宙全体の状態を観察してはの地域の会員のリストを持っていて，その地域でのいないのと似ています．

会員の数を知っています．地域事務局はボランティ
アで運営されているため，担当者がすぐに対応でき4．分散アルゴリズム

るとは限りません．さらに電話やインターネットは分散アルゴリズムとは，分散システムを動かすた一切使えず，情報のやり取りに使える方法は郵便葉めのアルゴリズムのことをいいます．アルゴリズム書に限定されています．配達が翌日の場合もあれ（algorithm）とは，ある決まった計算や制御を行う

ば，もっとかかる場合もあり，何日かかるか事前にための（抽象的な）処理手順のことをいいます．実

予想できません（非同期性）．地域事務局を統括す

際に動作するソフトウエアを作る際には，プログラる総事務局はなく，地域事務局の住所の一覧表すらムコードとして具体的に処理手順を詳細化します．

ありません．あなたが今知っているのは，居住してソフトウエアの基本設計書がアルゴリズムですかいる場所の地域事務局だけです．各地域事務局は隣ら，アルゴリズムに間違いがあったり処理に手間がの地域の地域事務局の住所しか知りません（局所図1

分散システムと分散アルゴリズム―２―性）．総会員数の調査にあたっては，他の地域事務5.1

定義局にお願いして，隣接する地域事務局に調査の葉書分散システム全体の状態を「状況」と呼ぶことにを出してもらわないといけないので結構面倒です．

します．状況には，各コンピュータの状態（変数値さらに，会員の総数を調べている最中にも入会や脱など）と各通信路の状態（伝送途中のメッセージな会があちこちの地域事務局で発生することに加えど）すべてがひとまとめに表現されています．変数て，会員が引越しをすると所属する地域事務所の変値が取りうる値は様々あり，またメッセージ内容も更が発生します（情報伝達遅延性）．一体どのよう様々ですから，取りうる状況の組み合わせの数は膨な方法で会員の総数を求めれば良いでしょうか．ま

大になります．分散システムが正しく動作している

た，得られた数値をどう解釈すれば良いのでしょう

望ましい状況のことを「正当な状況」と呼ぶことにか．（4 月 1 日午前零時の人数を全ての地域事務局します．状況が正当かどうかは，各コンピュータので一斉に記録して報告するよう，葉書で予め調査依状態がネットワーク全体で相互に整合が取れている頼を伝えておく方法ではうまくゆきません．3 月末

かどうかで決まります．1 台のコンピュータの状態までに葉書がすべての地域事務局に届くとは限らなだけで分散システムが正しく動作しているかは判断いからです．従って，地域事務局ごとにまちまちのできないからです．

日時に記録を取るしか方法がありません．また，例

自己安 定 性 を 持 つ 分 散 シ ス テ ム は，一 時 故 障

えば総会員数 4096 名という数値が得られたとして（transient fault）と呼ばれる障害への極めて強靭なも，それはいったいどの時点での数値と解釈すれば耐性を持ちます．一時故障には，例えば，伝送途中良いのでしょうか．）のメッセージの損失（通信障害），メッセージ内容

このような問題でも十分に難しそうなのに，さらの変化（ノイズ），コンピュータの再起動によるメにコンピュータの故障や通信障害などが起きても正モリ内容の消失（リブート），宇宙線の影響によるしく動作する仕組みを考えるのはとても大変そうでメモリ内容の変化（ソフトエラー）などが含まれます．

す．すなわち，ハードウエアやソフトウエアのプログラムコード自体は正常であっても，情報が意図し5．自己安定分散アルゴリズムない内容に変化してしまう類の障害のことを言いま

大規模 な 分 散 シ ステ ム で 重 要 なの は 故 障 耐 性

す．

（fault-tolerance）や 自 律 性（autonomy）で す．な ぜ

分散アルゴリズムが自己安定であるとは，以下になら，機器の数が膨大になるとそのうちの一部が故説明する閉包性と収束性のふたつの条件を満たすと障したり通信障害が発生するのは日常茶飯事であきをいいます．

り，ひとつひとつ人手で復旧作業することは事実上閉包性：ひとたび分散システムが正当な状況にな不可能だからです．例えばインターネットでは，通ると，その後の実行で現れる状況は正当である．

信機器の更新・障害・撤去などがいつも世界中のど（新たな一時故障が生じない限りは，システムは安こかで行われています．そのたびにインターネット定して正しく動作し続ける性質を表します．）

全体の機器，つまり世界中の機器を停止して再設定

収束性：必ずしも正当とは限らない状況から分散や再起動をするのは全く不可能であることは容易にシステムが動作を開始しても，その後のいかなる実想像できます．自己安定分散アルゴリズム（self-行に対しても，正当な状況に到達する．
（正当な状

stabilizing distributed algorithm）とは，分散システム況に到達しないまま無限に続く実行は一切存在しなに故障耐性や自律性に優れた性質を実現して，上記いということです．つまり一時故障が同時多発的にの問題の解決を目指した分散アルゴリズムです．

分散システムの各所で生じても，やがては正しい動―３―図2

自己安定分散システムの状況の遷移図作に復帰することを保証しています．）
図 2 に自己安定分散システムの状況の遷移図を示します．丸（●）はシステムの状況を，矢印（→）
はシステムの動作による状況間の遷移を，それぞれ表します．この図において，閉包性と収束性がともに成り立っていることを確認してみて下さい．正当ではない状況からどのような矢印のたどり方をして図3も，やがて必ず正当な状況へ到達します．
5.2

極小連結支配集合（黒丸のノード群）による無線ワイヤレスセンサネットワークにおける仮想バックボーンネットワーク

例：連結支配集合を求める問題

無線センサネットワークでのデータ収集に有用ないうことです．

ネットワーク構造のひとつとして，連結支配集合が連結性：MCDS に含まれているノードだけで構挙げられます．例えば図 3 に示すように，センシン成するネットワークは 1 つの連結成分だけである．

グだけを行うノードと，センシングに加えてデータすなわち，仮想バックボーンネットワークの数は 1送信のための仮想バックボーンネットワークを構成つだけであり，相互にマルチホップ通信が可能であするノードの 2 つに役割を分けて，データ収集を行る，ということです．

うのに有用です．仮想バックボーンネットワークと極小性：MCDS に含まれているノードをひとつは分散システムの背骨となる仮想的なネットワーク

でも減らすと，支配性あるいは連結性が成り立たなであり，分散システム全体での通信を可能にする役くなる．すなわち，仮想バックボーンネットワーク目を持ちます．従って仮想バックボーンネットワーを構成するために働くノードの数は極力少なくしてクは分散システム全体をカバーしていることが重要

資源の消費を少なくしたい，ということです．極端です．

な場合，全てのノードを選べば（極小ではない）連ネ ッ ト ワ ー ク（グ ラ フ）の 極 小 連 結 支 配 集 合

結支配集合になりますが，それでは全てのノードが（Minimal Connected Dominating Set；以 下 MCDS）

仮想バックボーンネットワークを構成するために働とは，以下の条件を満たすノード（頂点）の集合でくことになり，資源の浪費になるからです．
無線センサネットワークでは，バッテリー切れにす．
支配性：MCDS に含まれ な い ノ ー ド は，MCDSよるノードの停止，バッテリ充電によるノードの復に含まれるノードと直接通信できる．すなわちセン活，通信障害など，様々な事象が発生しますので，シングだけを行うノードは，仮想バックボーンネッ

自己安定性があればネットワークの管理・運営に極トワークを構成するノードに直接隣接している，とめて便利です．文献［7］では MCDS を求める自己―４―安定分散連結支配集合アルゴリズムが提案されてお図 4（a）：動作開始してすぐの状況です．11×11

り，その実行の経過の様子を図 4 に示します．これの計 121 のノードを格子状に配置しており，各ノーは 1 台のパーソナルコンピュータ上で実行する自己ドは無線により周囲のノードと通信をします．右下

安定分散アルゴリズムのビジュアルシミュレータのノードを中心とする大きな円は，無線通信可能な（著者作成）による表示のスクリーンショットで，範囲を表しています．他のノードも同じ通信半径を以下に実行の経過を説明します．

持ちますが，表示は一部のノードに対してのみ行っ（a）始動直後（b）動作中（c）動作中（d）MCDS で安定（e）矩形内のノードを選択（f）選択したノードを停止した直後（g）動作中（h）MCDS で安定
図4

自己安定分散連結支配集合アルゴリズムの実行例―５―

ています．全てのノードに対して描くと見にくくなノードと相互に通信をすることで不整合の解消を行ってしまうからです．右下のノードに各センサの測う形のアルゴリズムになっています．あるひとつの定データを収集するというシナリオを想定すると分特定のノードがネットワーク全体の状況を確認しかりやすいと思います．て，修復司令を一斉に出すのではありません．

図 4（b）：動作開始後，しばらく経過した状況で

図 4（g）：MCDS 自己安定分散アルゴリズムに従す．各ノードは MCDS 自己安定分散アルゴリズムって動作している途中の状況で，MCDS が再構成を実行しています．MDCS のノードとして選ばれされつつあります．
図 4（h）：現在動作しているノード群に対 す るているものは黒い丸で描かれています．まだ途中段MCDS が求まり，安定した状況です．分散システ階ですので，MDCS は完成していません．
図 4（c）：更に時間が経過した様子です．これもまだ途中段階で，MDCS は完成していません．ノ

ムに障害等が発生しない限りはこのまま変化は起きず，安定した状況が続きます．

ードは MDCS のノードとして選ばれれるか否かを以上では簡単な動作シナリオを見てみましたが，互いに調整しながら動作しますので，いったん選ば分散システムのあちこちで同時多発的に障害やノーれたノードもその後には選ばれなくなることはしばドの停止などが起きたとしても，それらが収まればしば起きます．

自動的に安定します．

図 4（d）：MCDS が求まった状況であり，分散システムに障害等が発生しない限りはこのまま変化は5.3

前方復旧起きず，安定した状況が続きます．MCDS のノー分散システムの変化が起きても，上述のようにやドとして選ばれたものの中で，互いに直接通信が可がては安定するほか，ノードのメモリをデタラメに能な，つまり電波が到達する 2 ノード間に直線を描書き換えてもやがては安定します．ここで注意していてあります．この状況を見ると，以下の 2 点が成いただいたいのは，システムのバックアップをとっり立っていることが分かります．ておき，それに基づいた復旧（レストア）を行うの・MCDS のノードとして選ばれているものだけでではないという点です．バックアップをとっておい構成した部分ネットワークは，ひとつの連結した成ても，上記のようにノードの電源がオフになった分となっている．
（バックボーンネットワークを通り，新たなノードが追加されたりすると，分散シスじて，データは右下のノードに必ず到達できる．）

テムの構成が変化しているために，バックアップの・MCDS のノードとして選ばれていないも の は，データそのものが役に立ちません．

選ばれているノードの通信半径内に入っている．

自己安定の概念は，過去の正しい状況に戻すとい（バックボーンネットワークを構成するノードと直う後方復旧（backward recovery）とは異なり，今の接的に通信ができる．）

諸条件に合う正しい状況にシステムを持ってゆくと

図 4（e）：ここで意図的に分散システムに障害をいう前方復旧（forward recovery）という考え方で発生させてみます．矩形で囲まれたノードを選択す．参加するノードや利用可能なネットワークがしし，これらの電源の停止を行います．

ばしば変わる分散システムでは，自己安定の概念は

図 4（f）：選択されたノードの電源を停止した直後の状況です．残ったノードだけでは MCDS が構成できていません．各ノードは不整合が起きているとても有用な設計技法といえます．

6．おわりにことを検知して，MCDS 自己安定分散アルゴリズ

本稿では多数のコンピュータで構成される分散シムに従って動作します．このとき各ノードは周囲のステムを動作させるための分散アルゴリズム，特に―６―

故障耐性や自律性を実現する自己安定分散アルゴリずと言っていいくらい取り上げられてる基本的な問ズムを紹介しました．コンピュータの数が多数にな題のひとつですので，興味ある方は調べてみて下さるほど，故障耐性や自律性をアルゴリズムそのものい．に持たせることが重要になります．自己安定分散システムは，この課題の解決を目指した分散システム

参考文献の設計手法です．なお本稿で紹介した自己安定アル［ 1 ］ E. W. Dijkstra,

ゴリズムの定義では，自己安定分散アルゴリズムが完全に収束し安定するまで時間がかかることがあり

Self-Stabilizing Systems in Spite ofDistributed Control , Communications of the ACM,
Vol.17, No.11, pp.643-644, 1974.
［ 2 ］ K. Altisen, S. Devismes, S. Dubois, F. Petit, Introduc-ます．この問題点を解決する研究も行っていますがtion to Distributed Self-stabilizing Algorithms , Morgan& Claypool, 2019.

本稿では省略します．
なお本文中で紹介したアイドルグループのファンクラブの会員の総数を求める問題は，分散アルゴリ
ズムの分野ではグローバルスナップショット［ 3 ］ S. Dolev, Self-Stabilization , MIT Press, 2000.
［ 4 ］ 増澤，山下， 適応的分散アルゴリズム ，共立出
版，2010 年．
［ 5 ］ M. Schneider,（global snapshot）問題として知られており，分散システム全体のスナップショット（分散システムの状［ 6 ］ F. C. Gärtner, Fundamentals of Fault-Tolerant Distributed Computing in Asynchronous Environments , ACM態）を適切に記録する問題です．重要なデータのバックアップをグルーバルスナップショットアルゴリ

Self-stabilization , ACM ComputingServeys, Vol.25, No.1, pp.45-67, 1993.

Computing Serveys, Vol.31, No.1, pp.1-26, 1999.
［ 7 ］ S. Kamei, and H. Kakugawa,A Self-stabilizing Dis-ズムにより取得しておき，システム障害の際にはバtributed Approximation Algorithm for the Minimum

ックアップのデータをリストアすることで障害からConnected Dominating Set,の復旧が行えます（後方復旧）．グローバルスナッ

Foundation of Computer Science, Vol.21, No.3, pp.459-

プショット問題は分散アルゴリズムの教科書では必―７―476, 2010.

International Journal of