自律分散協調システム論

Author

gentam

Status
archived
Date
2018-04-09
Category

lecturenote

Tag

distribution, decentralization, p2p, network, lecture

Updated

2018-07-16

自律分散協調システム論 / Autonomous Decentralized Cooperative Systems (徳田英幸) の授業ノート

Contents

シラバス

科目概要

社会、組織や情報環境において、分散された自律系を主体としたシステム構築が 進んで きている。本講義では、このような自律分散システムが、個々の構成要素 の自律性と、 それらの要素間での協調を基に全体として、機能、性能、信頼性を 向上していくシステ ムの概念、技術、方法、そして、その意味について学習する。

主題と目標/授業の手法など

社会、組織や情報環境において、分散された自律系を主体としたシステム構築が 進んで きている。本講義では、このような自律分散システムが、個々の構成要素の自律性と、そ れらの要素間での協調を基に全体として、機能、性能、信頼性を 向上していくシステム の概念、技術、方法、そして、その意味について学習する。

参考図書

  • Andrew S. Tanenbaum 分散システム - 原理とパラダイム

  • 亀田恒彦, 分散アルゴリズム (アルゴリズムシリーズ) 単行本 – 1994/7

第1回 自律分散協調システムとは?

  • 概説 - 事始め -

  • 自律分散協調システム

  • 概論(1) - 生物学的システム、工学的システム

  • 概論(2) - 社会学的モデル、社会システム

自律分散協調システム: Autonomous Distributed Cooperative (ADC)

システム内に全体を統括するスーパバイザが存在しない.そして各サブシステムは自律 ,分散した構成要素からなる.全体のシステムの昨日はサブシステム間の協調作業によ って遂行される.

集中型と分散型の比較

  • スケーラビリティ:
    集中型では負荷が一箇所にかかってボトルネックとなるが,分散型の方がスケーラビリ
    ティが高まる
  • 耐障害性:
    集中型では一箇所が故障すると全てが使えなくなるが,分散型の方が別の部分で補うこ
    とができ,耐障害性が高い
  • 管理・マネタイズ:
    集中型の方がシステムを管理したり,ビジネスとしてマネタイズしやすい傾向にある
  • セキュリティ:
    集中型の方がセキュリティ面での対策が行いやすい傾向にある

基本的な概念

  • 自律性:

    • 個の確立

    • 主体的行動

      西洋はなぜ日本より進んでいるのかということを考えた福沢諭吉:

      一身独立し一国独立す

  • 分散性

    • 多数の個

    • 空間的・ネット的に分散

  • 協調性

    • 個と個の協調プロトコル

    • 協調により全体の昨日を維持・形成する

    • 構成論的手法 vs. 自己組織論的手法

  • システムとしての評価

    • 評価の軸

    • 良いシステム vs. 悪いシステム

第2回 分散コンピューティングのパラダイム(1)

  • 分散コンピューティング

  • 並行プロセスモデル

  • 並行オブジェクトモデル

  • ネットワーク

  • プロトコルとは

  • 協調動作の記述

  • 自然言語

  • Time-space chart

  • 状態遷移図

  • 擬似並行プログラミング言語

自律分散協調システムの目的

  • 機能拡大

  • コスト性能の改善

  • 分散処理による効率・サービスの改善

  • オンラインリアルタイム処理の実現

  • 局所化による通信料の提言

  • 構成要素のモジュール化

  • 拡張性の保証

  • 集団組織の効率化

  • 信頼性•耐故障性の改善

  • 状況・環境変化への適応

  • 生存可能性の増大

演習: 集中的なシステムと分散的なシステムを3つ挙げる

Centralized:

  1. ブリタニカ百科事典

  2. 銀行システム

  3. Gmailサービス

Distributed:

  1. Wikipedia (の編集プロセス)

  2. Bitcoin / Blockchain

  3. 電子メールプロトコル / インターネット

Sensor Network Models

  • Sink-node Model

  • P2P Model

第3回 分散コンピューティングのパラダイム(2)

  • 並行プロセスモデル

  • 並行オブジェクトモデル

  • 自律分散協調アルゴリズムとは?

  • 論理クロック

  • 相互排除問題

プロセス間通信: Direct IPC

B → Blocking, N → Non-blocking

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)

演習

  1. Direct IPCモデルのNsend, Nrecを使わずにパイプライン型の協調モデルを記述せよ。

Process P1
{
  msg = init();
  Bsend(P2, msg, sizeof(msg));
}

Process P2
{
  Brec(P1, buf, sizeof(buf));
  do_my_part(buf);
  Bsend(P3, buf, sizeof(buf));
}

Process P3 { ... }

2. Direct IPCモデルを使って静的Workerモデルを完成せよ。 Hint: 余分なプロセスとQueueを使う。

Server S1
{
    taskQ[MAX_TASK] = {};
    workQ[N] = {};

    loop N times { /* initialization */
        worker_pid = create_worker();
        enque(workQ, worker_pid);
    }
    loop {
        pid = NULL;
        pid = Nrecany(buf, ...); /* non-blocking recv to avoid deadlock */
        if (pid is NULL) { /* did not receive any message */
            if (not_empty(workQ) && not_empty(taskQ))
                Nsend(deque(workQ), deque(taskQ), ...); /* assign task */
        } else
        if (is_worker(pid)) { /* a worker finished a task */
            enque(workQ, pid); /* back to waiting state */
            {cid, result} = buf;
            Reply(cid, result, ...); /* send result back to client */
        }
        else { /* got a new request from a client */
          if (not_full(taskQ))
              enque(taskQ, {pid, msg});
          /* if taskQ is full, drop request */
        }
    }
}

Process W1
{
    loop {
        Brec(S1, {cid, buf}, ...);
        res = do_service(buf, ...);
        Bsend(pid_client, {cid, res}, ...);
    }
}
Process W2 { ... }

第4回 自律分散協調アルゴリズム(1)

  • 相互排除問題

  • 回覧板プロトコル

  • 分散ソート

  • アドホックネットワークの経路制御アルゴリズム

プロトコルの記述 N-way Protocols

プロトコル

外交上の儀礼.通信の送信側と受信側で取り決めた約束事.通信手段.

2-way vs N-way protocol

なんのためにプロトコルが必要か:

  • データ転送に必要な初期化や終了

  • 送信者と受信者と同期(条件)

  • 転送エラー検出や訂正

  • データ書式や符合化を行う

プロトコルの記述

  • プロトコルの記述は,通信状の約束事を全て定義する

  • 通信メッセージのフォーマットの詳細.(format) -> (syntax)

  • メッセージを交換する歳の手順: (procedure) -> (grammer)

  • 正しいメッセージが表している意味,語彙: (correctness) -> (semantics)

  • complete な記述 vs. incomplete な記述

記述方法:

  • 自然言語

  • Time-space chart

  • 状態遷移図

  • 擬似Prog. Languages

Sender -> Receiver: msg
Sender <- Receiver: ACK
  • 入札プロトコル

  • 回覧板プロトコル

  • 仮想リングプロトコル

  • 逆オークションプロトコル

State Transition Diagram

状態遷移図

演習: Distributed Partitioned Sort

  • 1からNまでの整数の分散分割ソート

問題

  • P1からP10までの各プロセスにランダムに与えられたときどのようにしてソートするこ とができるか?

Note

Leslie Lamport のロジカルクロック

第5回 自律分散協調アルゴリズム (2) と創発

  • ロジカルクロック

  • 分散相互排除問題

  • 分散デッドロック

  • p2pシステム

分散サーチ

  • Distributed search for the numbers between 1 and N

  • Processes: P1-P100

  • N = 1,000

  • Each process has 100 cards

  • Given integer k(1..1000), is it in 100 cards or not?

並列処理の限界:

  • 総処理時間は最も遅いプロセスの時間 + 問題のコーディネーション時間

  • divide and conquer 型, Fork-join

Note

Amdahl's Law

演習2: 集中型から分散型へ

  • 待ち合わせ支援システム での例

  • Centralized type: クライアントがサーバに位置を通知

  • Decentralized type: クライアント間で直接メッセージを交換

  • 駅から15分の移動

    • サーバ経由: 1メッセージ/分 の場合,(15 + 1) * 2 回で会える

    • 分散型: 15 * 2 メッセージ

状態が変わらなければ,メッセージは送らない.

分散システムの評価基準は?

  • CPU時間,メモリ容量

  • 消費電力

  • 交換された総メッセージ数

  • リアルタイム vs ノンリアルタイム

結局,時間/空間の制約

分散相互排除問題

  • シリアルなリソースを利用する際には互いを妨げないように,排除しなければいけない

  • プリンタの例:

    • 集中型の場合は,ガードするプロセスがスケジューリングできるが, 分散環境ではお互いのルールを決めていかなければいけない

Logical Clock

    1. Lamport (1978)

  • 分散システムでの event ordering

  • 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 differenct processes, x->y is not true and y->x is not true: x and y are concurrent events

  • Ci: Logical Clock (局所論理時計)

  • 規則1: 受信事象以外の事象eがPiで起こった場合,,その直後にCiに1を加える.事象e は,更新された時刻Ciに生起したとする

  • 規則2:

    • Piがメッセージを送信するときには,時刻印ts=Ciをメッセージに付加して送信する

    • Piが時刻印tsを持つメッセージを受信した時には,Ciをmax{Ci, ts}+1まで進める. この受信事象は更新された時刻Ciに生起したとする

Ricart-Agrawala's Algorithms

  1. 資源を使用したいプロセスPiはreq(TSI, Pi)を他の全てのプロセスに送信する

  2. プロセスPiからreqメッセージを受信したプロセスPjは以下のように行動:

    • Pj が今資源を要請...

基本的なアイディア: 相手から全てreplyが帰ってきたら自分が使える

課題:

  • 仮想リングプロトコルをtime-space chart でデザインし,その挙動を記述せよ. (データフォーマットは図で示す)

  • <node id> <process id> <message body>

  • P1...P4 までの4つのプロセス間を記述

  • 終了条件などについても記述する

分散システムにおいては,到着順より出発順が重要

第6回 自律分散協調アルゴリズム (3) と Dependability

  • Distributed Algorithms(3)

  • 創発とは?

  • 創発システムの要件

  • Dependabilityとは?

事例:

高信頼性(Dependability)は以下の要件を満たす

第7回 創発と問題解決のパラダイム

  • 問題空間と解空間

  • 発見的手法

  • Robotroom.java

  • Wave2.c

  • Generate and Test

  • Genetic Algorithms

創発システムについて

  • 複数の要素が有機的に関係しあって,そうぞ作用を通じて全体としてまとまった昨日を 発現している要素の集まり: 相互作用が変われば,システムの機能も変わる

  • 弱い創発: ミクロな要素の動きが集まって全体に渡るマクロなパターン

  • 強い創発:

創発のかたち:

  • 上位層でのかたち: グループ,群,コミュニティ

  • 水の対流

  • サッカー場のウェーブ

  • 自律型ロボットの整列問題

ロボット整列問題

課題: 群のロボットを自律的に円に整列させる.

  1. Big brother: 完全なリーダー

  2. 先生ロボット + 生徒ロボット

  3. 先生ロボットを選出

  4. 同一ロボット: 自律的

Robotroom.java を完成させる. nextmove という次の位置決めロジック

書いたもの:

  • それぞれのロボットが,他の全てのロボットの位置を通信によって知っているという前提

  • 全てのロボットが同じロジックで動いているので,一応上の分類だと自律的といえそう

  • 具体的には以下の単純なベクトルの計算を行っている:

    • 中心へと引き寄せられるベクトル (中心からの距離に比例して増加)

    • 中心から離れようとするベクトル (中心からの距離に比例して減少)

    • 他のロボットから距離を置こうとする反発ベクトル

最初2つの釣り合いによって,各ロボットは中心まで等距離の円周上に並ぶことになり, 最後の互いの反発によって均等に並ぶことになる.

対故障アルゴリズム

t-resilient: t個のプロセスの故障に耐えられる

二人の将軍問題

通信経路が信頼できないとき,2者間で安全に合意できるアルゴリズムを設計することは 不可能である

ビザンチン将軍問題

Lamportの解: 障害プロセスがm個のとき,正常プロセスが2m+1個以上,全体で3m+1個以上 のときに,正常プロセス同士で合意に至ることが可能

ビザンチン将軍問題も含めた古典的な合意問題の多くは、システムのプロセス数を n と したとき、n > 3t を満たさない場合の解が存在しない。言い換えれば、全プロセスの3 分の1未満が障害という状況でないと、正しい動作を保証できない。

ブロックチェーンでの活用

事例

  • 無線アドホックネットワーク

    • ネットワーク・インフラが存在しない

    • トポロジが人や物の動きと共に動的に変化

    • Weak Connectivity

  • Mebius Ring の実験: Asynmetric-link (Ackが返ってこないなど)

ルーティングの方式:

  1. Flooding: 全ての隣接ノードにブロードキャスト.最もシンプルなかたち

    目標のノードに到達しても,関係ない部分ではひたすら伝播されてしまう.基本的 に生成 waveよりも,終了waveが到達するのは遅くなるため終端できない.

    → 一定以上の規模のネットワークでは非現実的

  2. DSR: Dynamic Source Routing

    • まずRoute Discovery フェーズでは,ノードは自分のノードアドレスをを探索パケ ットのヘッダにappendしてから転送する

    • 最終的に受け取ったノードはソースまでの経路情報が分かるため,そこへリプライ する

    • 送信元はリプライを受けたら,実際にデータを送る

    • ノードの移動によって経路が壊れた場合は,全てのノードに Route Error (RERR) を伝えなければいけない.→ Flooding

  3. AODV: Ad-hoc On-Demand Distance Vector Roiuting

    DSRは宛先のルートを全てのパケットヘッダに含んでいるためやや効率が悪い. 一方,AODVは各ノードがルーティングテーブルを持っておく.

    • 各ノードは宛先に届けるために次にどのノードに投げれば良いのか知っている

    • 頻繁にルーティング情報が変わる場合は XXX 可能性がある

第8回 分散サーチと創発

  • サーチ

  • Hash Table

  • 分散サーチ

  • DHT

  • 創発とは?

DHT: Distributed Hash Table

名前空間の種類:

  • 階層的な構造 (e.g. ファイルシステム /usr/hxt/)

  • フラットな構造 (e.g. 0x7a9dc9...)

授業ではではChordを紹介. Chordはフラットな名前空間.

  • 分散マシン上のデータ格納と検索を実現したい

    • データは <key, value> ペア

  • Hash関数を活用して,どのマシンがそのデータを担当して保存するかを決める:

    • まず各ノードは自分のIPアドレスのハッシュ値 machineID := hash(IP_addr) を IDとして持っている

    • 保存したい/検索したいデータは dataID := hash(key) がmachineIDと最も近い かつ dataID < machineID なマシン{に保存 | から取得}できる

  • どうやって他のノードと通信するか:

    • 各ノードは自分の後続(successor)を持っていてリング状のネットワークを形成して いる

    • 後続ノードだけを持っていたら検索が非常に遅くなってしまうが,全ノードの情報を 持とうとするのはルーティングテーブルの更新だけでものすごい数のメッセージが必 要になって非現実的

      • そこで,各ノードは finger table と呼ばれるルーティングテーブルを持つ.これ は,スキップ自分の近傍は高い密度で情報を持っていて,遠くはまばらにしかもっ ていないという,リング状のスキップリスト的なもの.

遺伝アルゴリズム

生物の自然淘汰と進化の仕組みを問題解決に応用する:

  • 交差 (配合)

  • 選択 (淘汰)

  • 突然変異

ポイント

  • 遺伝子情報を何にするか

    • e.g. Traveling Salesman Problem だと,都市の名前を巡回する順番に持った配列.

  • 適応度 (fitness) 評価関数を何にするか

    • e.g. TSP だと全ての都市を回りきるまでの時間(コスト)になる

第9回 エージェントとマルチエージェント(1)

  • 知的エージェントとは?

  • Vacuum World

  • Taxi Driver Agent

  • 単純反射エージェント

  • 記憶をもつ反射エージェント

  • ゴール主導エージェント

  • 効用主導エージェント

問題解決手法のパラダイム:

マルチエージェントシステム

AI Agent アプローチ

by Russel & Norvig 1995

AIの定義を4つに分類した:

  1. 人間のように行動するシステム: チューリングテストアプローチ

  2. 人間のように考える: 認知モデルアプローチ

  3. 合理的に考える: 思考の法則に夜アプローチ

  4. 合理的に行動する: 合理エージェントアプローチ

第10回 エージェントとマルチエージェント(2)

  • 知的エージェントとは?

  • Vacuum World

  • Taxi Driver Agent

  • エージェントアーキテクチャ

第11回 ゲストレクチャー: IoT-based Solutions

ゲストレクチャー(大越先生)へ変更

Key Concepts When You Think About IoT-based Solutions

  • 100年前の新聞の全面広告には"モーター"が載っていた

    • 今は,"モーター"は普遍的な存在で,別に意識したり宣伝するものではない.

  • 今から100年後のコンピュータは同じように,普遍的で意識から消えるようになるので はないか → それが ユビキタス という概念

  • IoTも中心となる概念は同じ

"SPA" Model

  • Sensing → Processing → Actuation

    • 情報の"ドミノ倒し"

  • "HoT-SPA": Here or There SPA

    • Here: on the client, edge

    • There: in the cloud

    • S,P,A をエッジとクラウドにどうやって配置するかには様々な組み合わせがある

  • Cyber Physical System for Smart Cities

どうやって,実世界の情報をセンシングしてくるか?

  • デバイスセンサーを使う

  • Social media as a sensor: e.g. Twitter

  • Participatory sensing: 実際にユーザに質問する.e.g. Weather News ゲリラ豪雨

  • Mobile sensing: スマホのセンサーをimplicitに利用

    • センサーデータの直接的利用と

    • 様々なセンサーデータを総合して,行動や状況を推論することができる

      • 機械学習の活用

  • データの量は膨大だが,人間のアテンションは有限.e.g. 膨大な量の通知

  • いくら情報を送っても読まれなければ意味がない

第12回 ゲストレクチャー: ブロックチェーン技術

ゲストレクチャー(鈴木茂哉先生)に変更


Term Project

集中型で実装されているサービスを見つけ,それを自律分散強調型のシステムに変更する ための詳細でデザインをせよ. また,そのシステムの評価指標及び,利点,欠点について議論せよ.

第13回 応用システム

分散ファイルシステム

第14回 自律分散協調型システムの設計とまとめ

  • 未来について.

進化の予測は難しいが,速度進化が物理亭な限界に近づいているのも事実

社会イノベーションのスピード

  • 文化 < 価値観 < 生活スタイル < 技術

"Political Animal -> Economic Animal -> Socializing Animal"

  • インターネットの進化

  • ARPANET につながっている大学とつながっていない大学の間に,最初の digital devide が生まれた

Note

ARPANETは主に学術系で使われ,軍事用はMILNETというネットワークがあった

  • 今,またデータを持つシリコンバレーの大企業とその他の間に,digital devideが再来

  • IoTとセキュリティ