自律分散協調システム プロトコルと分散アルゴリズム 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007

自律分散協調システムとは？ 。。。ちょっと復習。。。

新しいパワフルなパラダイム 創発システムのパラダイム 自律分散協調システムとは？ 新しいパワフルなパラダイム 創発システムのパラダイム

自律分散協調システムとは？ システム内にシステム全体を制御／統治するスパーバイザは存在しない。 各サブシステムは、自律、分散した構成要素からなる。 全体のシステムの機能は、サブシステム間の協調作業によって遂行される。 © H.Tokuda 2007

自律性について 社会システム ネットワークロボットモデル 発展途上国における地方自治体モデル 日本における地方自治体モデル 自動整列問題 掃除ロボット問題 どのようなアルゴリズムが良いか？ スマート交差点問題 © H.Tokuda 2007

協調性について 協調のメカニズム 協調プロトコル 自然なプロトコル 人工的なプロトコル どのような協調パターンがあるのか？ どのように記述するのか？ なぜ協調するのか？ 自然なプロトコル 生物システム 人工的なプロトコル Client-Server Ethernet’s MAC Layer 競売プロトコル 回覧板プロトコル その他多種多様なプロトコル。。。 © H.Tokuda 2007

分散プログラムのモデル 並行プロセスモデル 並行オブジェクトモデル 対象としているシステムのモデル化に適している。 Program = a set of cooperating (sequential) processes 並行オブジェクトモデル Program = a set of cooperating objects 対象としているシステムのモデル化に適している。 いくつかの分散・並行プログラミング言語も開発されている。 © H.Tokuda 2007

並行プロセス: プロセス間通信(1) © H.Tokuda 2007

並行プロセス: プロセス間通信(2) © H.Tokuda 2007

並行プロセス: プロセス間通信(3) © H.Tokuda 2007

並行オブジェクト © H.Tokuda 2007

プロセス間通信: Direct IPC Bsend(process_id, message, size) The communication is done between two processes without using any communication entity. Bsend(process_id, message, size) Nsend(process_id, message, size) Brec(process_id, buffer, size) Nrec(process_id, buffer, size) process_id = Brecany(buffer, size) process_id = Nrecany(buffer, size) Request(process_id, message, sizeof(message), buffer, sizeof(buf) Reply(process_id, message, size) © H.Tokuda 2007

分散システムの捕らえ方

システムの捕らえ方 構成論的手法 自己組織論的手法 Top-down, bottom-up手法 自律的にシステムを構成 群知能、集団行動 Client-server model 自己組織論的手法 自律的にシステムを構成 群知能、集団行動 アリの巣 都市のかたち 自律型ロボットシステム © H.Tokuda 2007

構成論的手法 協調方法を定義したアーキテクチャの構築 全体に対して個々のエージェントの役割が位置づけられる。 コミュニケーションプロトコルの設計 マスタースレーブ的な協調、機能分割的な協調 位置的、機能的分散処理の重視 工学的な効率、システム動作解析可能性の重視 © H.Tokuda 2007

自己組織論的手法 協調的行動を発現するアーキテクチャの構築 システムダイナミクスの研究 柔軟性、頑健性の重視 自律性に基づく協調 全体は、個々のエージェントのインタラクションの結果として創出される。 システムダイナミクスの研究 柔軟性、頑健性の重視 自律性に基づく協調 生物、社会現象の模倣 © H.Tokuda 2007

自律性とは？ 自律： 自立： 自律性をプログラムするとは？ 自分で自分の行為を規制すること 外部からの制御から脱して、自身の立てた規範に従って行動すること 自立： 他の援助や支配を受けず自分の力で身を立てること 自律性をプログラムするとは？ エージェントを作るとは？ © H.Tokuda 2007

ロボット整列問題 一群のロボットを自律的に円に整列される Alogrithm 1: Big brohter方式 各位置を明示 Algorithm 2:先生ロボット＋生徒ロボット 先生ロボットが計算し、支持 Algorithm 3:先生ロボットを選出 先生ロボットを動的に選出 Algorithm 4: 同一ロボット © H.Tokuda 2007

分散プログラム 並行プロセスと並行オブジェクト 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007

情報システムにおける自律分散協調モデル システムアーキテクチャ的な見方 分散プログラム的な見方 基本的な概念 構成要素は何か？ それらがどのように協調作業を進めるのか？ 制御の流れ データの流れ メッセージの流れ © H.Tokuda 2007

分散プログラムのモデル 並行プロセスモデル 並行オブジェクトモデル 対象としているシステムのモデル化に適している。 Program = a set of cooperating (sequential) processes 並行オブジェクトモデル Program = a set of cooperating objects 対象としているシステムのモデル化に適している。 いくつかの分散・並行プログラミング言語も開発されている。 © H.Tokuda 2007

並行プロセス: プロセス間通信(1) © H.Tokuda 2007

並行プロセス: プロセス間通信(2) © H.Tokuda 2007

並行プロセス: プロセス間通信(3) © H.Tokuda 2007

並行オブジェクト © H.Tokuda 2007

並行プロセスの挙動とその記述 慶應義塾大学環境情報学部 徳田英幸 © H.Tokuda 2007

プロセス間通信: Direct IPC Bsend(process_id, message, size) The communication is done between two processes without using any communication entity. Bsend(process_id, message, size) Nsend(process_id, message, size) Brec(process_id, buffer, size) Nrec(process_id, buffer, size) process_id = Brecany(buffer, size) process_id = Nrecany(buffer, size) Request(process_id, message, sizeof(message), buffer, sizeof(buf) Reply(process_id, message, size) © H.Tokuda 2007

Client/Server Model • Client/Server Model is a well-known model. • A client (i.e., a user process) sends the request message to a server process, which then does he work and sends back the results. Client 1. Request Server 2. Accept 3. do_service 4. Reply © H.Tokuda 2007

Web Server’s Architecture © H.Tokuda 2007

Client/Server in Web Web Server (httpd) Clients Get(/foo.html http/1.0) Response (header + contents(foo.html) foo.html © H.Tokuda 2007

Actions in Web Server Process web_server() { while(1) { Brecany() do_service() reply() } © H.Tokuda 2007

Process P1 { … brec(p2, …); } Process P2 { … brec(p1, …); } 並行プロセスの挙動 デッドロック(1) Process P1 { … brec(p2, …); } Process P2 { … brec(p1, …); } Brec(p2,...) Brec(p1,...) p2 p1 © H.Tokuda 2007

システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 並行プロセスの挙動 デッドロックとは？ システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 p1 Brec(p2,...) Brec(p3,...) Brec(p1,...) p2 p3 © H.Tokuda 2007

Process P1 { … request(printer,…) request(tape, …) } Process P2 { … 並行プロセスの挙動 デッドロック（２） Process P1 { … request(printer,…) request(tape, …) } Process P2 { … request(tape, …) request(printer,…) } p2 p1 © H.Tokuda 2007

Process P1 { … bsend(p2, …); } Process P2 { … brec(p2, …); 並行プロセスの挙動 パイプライン（１） Process P1 { … bsend(p2, …); } Process P2 { … brec(p2, …); do_my_part(); bsend(p3, …); } … p1 p2 P3 pk © H.Tokuda 2007

Process P1 { … nsend(p2, …); } Process P2 { … nsend(p3, …); } 並行プロセスの挙動 パイプライン（2） Process P1 { … nsend(p2, …); } Process P2 { … nsend(p3, …); } … p1 p2 P3 pk © H.Tokuda 2007

Server S1 { … Brecany(msg,…) do_service(...) reply(msg, …) } 並行プロセスの挙動 Workerモデル Server S1 { … Brecany(msg,…) do_service(...) reply(msg, …) } s1 c1 © H.Tokuda 2007

並行プロセスの挙動 動的Workerモデル Server S1 { … ci=Brecany(msg,…) create_worker(ci,...) } Process w1 { … do_service(msg,…) reply(ci,…) } w1 . s1 c1 wk © H.Tokuda 2007

並行プロセスの挙動 静的Workerモデル Server S1 { … ci=Brecany(msg,…) if(ci is worker) assign_task(ci, …) else enque(ci, task) } Process w1 { … 　request(s1, ...) do_service(msg,…) reply(ci,…) } w1 . s1 c1 wk © H.Tokuda 2007

課題１ Direct IPC モデル １）Direct IPCモデルのNsend, Nrecを使わずにパイプライン型の協調モデルを記述せよ。 ２）Direct IPCモデルを使って静的Workerモデルを完成せよ。 Ｈｉｎｔ：　余分なプロセスとＱｕｅｕｅを使う。 © H.Tokuda 2007

プロトコルとは？ ～協調動作の記述～

プロトコルとは？ 外交上の儀礼 通信の送信側と受信側で取り決めた約束事 通信手段 pro･to･col 1 Ｕ(外交上の)儀礼，典礼. 2 Ｃ 条約原案; 議定書，プロトコル. 3 Ｃ (国家間の)協定.→＃ 4 Ｃ 《米》 (実験･治療の)実施要綱[計画]. 5 Ｃ 【電算】 プロトコル 《データ通信の手順》. [株式会社研究社　新英和・和英中辞典] © H.Tokuda 2007

プロトコルの記述 プロトコルの記述は、通信上の約束事すべてを定義する。 通信メッセージのフォーマット（書式）の詳細 (format) -> (syntax) メッセージを交換する際の手順　(procedure) -> (grammer) 正しいメッセージが表わしている意味、語彙 (correctness) -> (semantics) Completeな記述　vs. Incompleteな記述 © H.Tokuda 2007

何のためにプロトコルが必要か？ データ転送に必要な初期化や終了 送信者と受信者との同期（条件） 転送エラーの検出や訂正 データの書式や符合化を行う © H.Tokuda 2007

状態遷移図 © H.Tokuda 2007

Time-Space Chart © H.Tokuda 2007

Concurrent Programming Language © H.Tokuda 2007 2

Stop-and-Wait Protocol © H.Tokuda 2007 3

課題-2 回覧板プロトコル 入札プロトコル 逆オークションプロトコル © H.Tokuda 2007

回覧板プロトコル（１） © H.Tokuda 2007

回覧板プロトコル(2) © H.Tokuda 2007

分散システムの捕らえ方

システムの捕らえ方 構成論的手法 自己組織論的手法 Top-down, bottom-up手法 自律的にシステムを構成 群知能、集団行動 Client-server model 自己組織論的手法 自律的にシステムを構成 群知能、集団行動 アリの巣 都市のかたち 自律型ロボットシステム © H.Tokuda 2007

構成論的手法 協調方法を定義したアーキテクチャの構築 全体に対して個々のエージェントの役割が位置づけられる。 コミュニケーションプロトコルの設計 マスタースレーブ的な協調、機能分割的な協調 位置的、機能的分散処理の重視 工学的な効率、システム動作解析可能性の重視 © H.Tokuda 2007

自己組織論的手法 協調的行動を発現するアーキテクチャの構築 システムダイナミクスの研究 柔軟性、頑健性の重視 自律性に基づく協調 全体は、個々のエージェントのインタラクションの結果として創出される。 システムダイナミクスの研究 柔軟性、頑健性の重視 自律性に基づく協調 生物、社会現象の模倣 © H.Tokuda 2007

自律性とは？ 自律： 自立： 自律性をプログラムするとは？ 自分で自分の行為を規制すること 外部からの制御から脱して、自身の立てた規範に従って行動すること 自立： 他の援助や支配を受けず自分の力で身を立てること 自律性をプログラムするとは？ エージェントを作るとは？ © H.Tokuda 2007

ロボット整列問題 一群のロボットを自律的に円に整列される Alogrithm 1: Big brohter方式 各位置を明示 Algorithm 2:先生ロボット＋生徒ロボット 先生ロボットが計算し、支持 Algorithm 3:先生ロボットを選出 先生ロボットを動的に選出 Algorithm 4: 同一ロボット © H.Tokuda 2007

© H.Tokuda 2007

分散アルゴリズム

分散アルゴリズム Distributed Mutual Exclusion Election Algorithm Distributed Deadlock Clock Synchronization Byzantine consensus problem 。。。 © H.Tokuda 2007

Logical Clock L. Lamport (1978) 分散システムでの事象(event)の順序関係 happens-before: a -> b If a and b are events in the same process and a occurs before b then a->b is true. If a is "send-event" of a message in Pi and b is "receive-event" of the message in Pj, then a->b is true. For any two events in different processes, x->y is not true and y->x is not true: x and y are concurrent events © H.Tokuda 2007

Lamport's Logical Clock Ci : Logical Clock （局所論理時計） 規則１：受信事象以外の事象eがPiで起こった場合、その直後にCiに１を加える．事象eは、更新された時刻Ciに生起したとする． 規則２： Piがメッセージを送信するときには、時刻印ts=Ciをメッセージに付加して送信する． Piが時刻印tsを持つメッセージを受信したときには、Ciをmax{Ci, ts}+1まで進める．この受信事象は更新された時刻Ciに生起したとする． © H.Tokuda 2007

Lamport's Algorithm 基本的なアイデア ? ? Pi Pj Pk req-i req-j reply reply © H.Tokuda 2007

Ricart-Agrawala's Algorithm 1)資源を使用したいプロセスPiはreq(TSi, Pi)を他のすべてのプロセスに送信する． 2)プロセスPiからreqメッセージを受信したプロセスはPjは以下のように行動する． Pjが今資源を要請していないならば、Pjの現時点での局所時刻印を持つreplyメッセージをPiに返す． もし要請中であれば、（TSi、Pi）をPjのreqの（TSj、Pj）と比較する． if (TSi, Pi) < (TSj, Pj)then replyメッセージをPiに返す． else req(TSi, Pi)へのreplyをPjが資源を使用し終わるまで保留する． © H.Tokuda 2007

Ricart-Agrawala's Algorithm (cont.) 3)他のすべてのプロセスから自分のreqメッセージに対するreplyメッセージを受信したときに限り、Piは、資源の使用を許可される． 4)Piが資源を解放したときは、replyを保留しているすべてのreqメッセージ（を送信したプロセス）に対して、replyメッセージを返す． © H.Tokuda 2007

直感的な例 Pi Pj Pk req reply reply reply reply © H.Tokuda 2007

分散アルゴリズム ～分散デッドロック問題～

分散デッドロック システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 p1 Brec(p2,...) © H.Tokuda 2007

WFG(Wait-for-Gragh) p1 Brec(p2,...) Brec(p3,...) Brec(p1,...) p2 p3 Host-B Host-A © H.Tokuda 2007

Dependability Dependability Dependability... © H.Tokuda 2007

ディペンダブルシステム 高信頼性（Dependability）とは、以下の要件を満たす 可用性（Availability） システムを利用したいときに高い確率で利用可能 信頼性（Reliability） システムは、ある一定期間、正常に稼動可能 安全性（Safety） 障害時でも、システムに重大な問題が生じない 保守性（Maintainability） 故障したシステムを容易に回復可能 © H.Tokuda 2007

Dependabilityとの出会い @cmu Prof. Dan Siewiorek C.mmp => Cm* => C.vmp Issues in Testing and Reliability in Computer Systems 新しい概念？ Fault Tolerant Computing Systems Mission Critical Systems Dependable Computing Systems © H.Tokuda 2007

耐障害性（フォールトトレラント性） フォールトトレラント性 障害(fault)の種類 システムの一部に障害が発生しても、システム全体のサービスを提供を続けられる性質 障害(fault)の種類 過渡障害（transient fault） 一度だけ発生し、消滅する障害 ノイズによるビット損失など 間欠障害（intermittent fault） 一時的な障害が繰り返される障害 コネクタの接続不良など 永久障害（permanent fault） 修復されるまで存在し続ける障害 ディスククラッシュなど © H.Tokuda 2007

Dependabilityの議論 Dependability と IT assurance 運用・管理・保守している人、組織、社会制度 情報システム系 Reliability, Availability, Safety Confidentiality, Integrity, Maintenability ガバナンス系 運用・管理・保守している人、組織、社会制度 何がディペンドしているのか？ 人(命)、モノ、金 National Security . . . IT system Gov. © H.Tokuda 2007

障害の遮蔽 システムに冗長性を持たせることで障害を隠蔽 情報的冗長性 時間的冗長性 物理的冗長性 CRCチェック、エラー訂正符号など 動作のやり直しによる冗長性 トランザクション処理など 物理的冗長性 余分なデバイスやプロセスを持たせる冗長性 RAIDなど © H.Tokuda 2007

耐故障アルゴリズム 停止故障 仮定 t-回復力 (t-resilient) ビザンティン故障 故障したプロセスは永遠に停止する． 通信は、可能であるが、プロセスの挙動が保証されない t-回復力　(t-resilient) あるアルゴリズムが高々t個のプロセスの故障にも耐えるアルゴリズム． ビザンティン故障 故障したプロセスの動作に一切の仮定をおかない． 故障プロセスは、任意の動作しうる！ © H.Tokuda 2007

ビザンティン合意問題 正常なプロセスが同じ初期値を持っている場合、それらのプロセスは、ある値で合意形成することができる。 e.g. 3 processes -- 可能かどうか？ P1 値={0, 1} 合意の値は？ 故障プロセス P2 P3 © H.Tokuda 2007

ビザンティン合意問題：３ Processes 1 1 1 1 P3 P2 P3 P2 P3 P2 値={0, 1} 合意の値は? © H.Tokuda 2007

ビザンティン合意問題 Lamportの解(1982) 障害プロセスがm個のとき、正常プロセスが2m+1個以上、全体で3m+1個以上のとき、正常プロセス同士で合意に至ることが可能 (例）m=1, n=4>=3m+1なのでＯＫ 将軍１：(1,2,*,4)、将軍２：(1,2,*,4)、将軍４：(1,2,*,4) P1 P2 P4 P3 1 © H.Tokuda 2007

分散アルゴリズムの実践 ～頭の体操から創発システムへ～

(I) 分散ソート問題 １からＮまでの整数の分散ソート 問題 初期値 N = 100 Processes: P1- P10 Ｐ１からＰ１０までの各プロセスにランダムに選ばれた１０個の数が初期の値として与えられた時、どのようにしてソートすることができるか？ 各プロセスは、どのような条件で、ソートが終了したことを判定できるか？ © H.Tokuda 2007

(II) ロボット整列問題 ある部屋内において、与えられた半径ｄの円周上にほぼ等間隔で整列するプログラムを作成せよ。 仮定 ロボットが共有座標系を持つ 同期的な動作をする (c.f. life game) © H.Tokuda 2007

ロボット整列問題 一群のロボットを自律的に円に整列される Algorithm 1: Big brother方式 各位置を明示 Algorithm 2:先生ロボット＋生徒ロボット 先生ロボットが計算し、指示する Algorithm 3:先生ロボットを選出 先生ロボットを動的に選出 Algorithm 4: 同一ロボット 自律的に整列 © H.Tokuda 2007

hxt-課題：Robotroom.java どのように協調するのか？ 実行例… © H.Tokuda 2007

世代の概念: Life game (1) Life game Life gameのルール J. H. ConwayのLife Game 盤面上にいくつかの石（生命体）を置く．（初期集団） 盤面のある場所が空いていて、しかもその場所と隣り合うちょうど３個の場所に生命体が存在するならば、次の世代にはその空いた場所に新しい生命体が誕生する． また、すでに存在する生命体については、隣り合う場所に住む生命体が１個以下、または４個以上になると、過疎または過密のため、次の世代には、死んでしまう． © H.Tokuda 2007

世代の概念: Life game (2) 世代の概念 * * * … © H.Tokuda 2007

(III) Wave programの課題 配布されたwave2.cプログラムを改良して、 　競技場で起こるwave 現象をsimulateできるようにする。 　　＜初期状態＞＜次世代生成部分＞ ＊ソースコード ＊出力結果 ＊考察 　　これをもとに、創発を起こす上でもっとも重要な要因について議論せよ。 © H.Tokuda 2007

hxt-課題：wave2.c どのように協調するのか？ 実行例… © H.Tokuda 2007

創発システムについて 複数の要素が有機的に関係し合って、相互作用を通して全体としてまとまった機能を発現している要素の集まり 弱い創発システム 相互作用が変わればシステムの機能も変わる！ 弱い創発システム ミクロな要素の動きが集まって全体にわたるマクロなパターンが創発するシステム 強い創発システム 環境変化に適応できる創発するシステム © H.Tokuda 2007

共通する性質は？ 自分と同じ能力の要素が沢山存在する 沢山の要素が広い空間に分散している すべての要素が共通の方法で（自分の近くの要素とだけ）情報の交換をする すべての要素が同時並列的にうごく すべての要素が同じ状況になるように動く(同じ評価関数をもっている） © H.Tokuda 2007

分散アルゴリズム ～分散デッドロック問題～

分散デッドロック システムを構成しているすべてのプロセスが起きるはずのない事象を待ち続ける状態 p1 Brec(p2,...) © H.Tokuda 2007

WFG(Wait-for-Gragh) p1 Brec(p2,...) Brec(p3,...) Brec(p1,...) p2 p3 Host-B Host-A © H.Tokuda 2007

創発システムに向けて 慶應義塾大学環境情報学部 徳田英幸

情報システムにおける自律分散協調論 自律分散協調システムのねらい 自律分散協調コンピューティング 自己組織性 創発のメカニズム アドホックネットワークプロトコル ソフトウェアエージェント 自律ロボット p2pアプリケーション © H.Tokuda 2007

自律性について 社会システム 自律分散協調モデル ガバナンスモデル 教育、交通、安全システム 創発とは？ ロボット自動整列問題 電子政府モデル 地方自治体モデル 教育、交通、安全システム スマート交差点問題 自律分散協調モデル 創発とは？ Waveは、どう起るか？ ロボット自動整列問題 ロボットよ、コンパスを持って協調せよ！ 掃除ロボット問題 どのようなアルゴリズムが良いか？ © H.Tokuda 2007

協調性について 協調メカニズム 協調プロトコル 自然なプロトコル 人工的なプロトコル どのような協調パターンがあるのか？ どのように記述するのか？ なぜ協調するのか？ 自然なプロトコル 生物システム 人工的なプロトコル Client-Server Ethernet’s MAC Layer 競売プロトコル 回覧板プロトコル その他多種多様なプロトコル。。。 © H.Tokuda 2007

ロボット整列問題 ある部屋内において、与えられた半径ｄの円周上にほぼ等間隔で整列するプログラムを作成せよ。 仮定 ロボットが共有座標系を持つ 同期的な動作をする (c.f. life game) © H.Tokuda 2007

ロボット整列問題 一群のロボットを自律的に円に整列される Algorithm 1: Big brother方式 各位置を明示 Algorithm 2:先生ロボット＋生徒ロボット 先生ロボットが計算し、支持 Algorithm 3:先生ロボットを選出 先生ロボットを動的に選出 Algorithm 4: 同一ロボット 自律的に整列 © H.Tokuda 2007

課題：Robotroom.java どのように協調するのか？ 実行例… © H.Tokuda 2007

Wave programの作成 配布されたwave2.cプログラムを改良して、 　競技場で起こるwave 現象をsimulateできるようにする。 　　＜初期状態＞＜次世代生成部分＞ ＊ソースコード ＊出力結果 ＊考察 　　これをもとに、創発を起こす上でもっとも重要な要因について議論せよ。 © H.Tokuda 2007

演習：wave2.c どのように協調するのか？ 実行例… © H.Tokuda 2007

創発システムについて 複数の要素が有機的に関係し合って、相互作用を通して全体としてまとまった機能を発現している要素の集まり 弱い創発システム 相互作用が変わればシステムの機能も変わる！ 弱い創発システム ミクロな要素の動きが集まって全体にわたるマクロなパターンが創発するシステム 強い創発システム 環境変化に適応できる創発するシステム © H.Tokuda 2007

共通する性質は？ 自分と同じ能力の要素が沢山存在する 沢山の要素が広い空間に分散している すべての要素が共通の方法で（自分の近くの要素とだけ）情報の交換をする すべての要素が同時並列的にうごく すべての要素が同じ状況になるように動く(同じ評価関数をもっている） © H.Tokuda 2007

自律分散協調コンピューティング 分散アルゴリズム 複雑な問題に対する新しいアプローチ 協調作業支援システム 相互排除問題、デッドロック問題、etc 複雑な問題に対する新しいアプローチ エージェントシステム 遺伝的アルゴリズム(GA) 協調作業支援システム CSCWシステム グループウェア コミュニティウェア © H.Tokuda 2007