t3t5u

#{   1 => #{  11 => #{1112 => #{}},
              12 => #{1121 => #{},
                      1122 => #{},
                      1211 => #{},
                      1212 => #{ 122 => #{},
                                1111 => #{}}},
             111 => #{1221 => #{},
                      1222 => #{}},
             112 => #{ 121 => #{}}}}.

t3t5u

Root| Node|                           EagerPeers| LazyPeers
----+-----+-------------------------------------+-------------------------------------------
   1|    1|             [  11,   12,  111,  112]| [1111, 1122, 1211, 1222]
    |   11|                         [   1, 1112]| [ 111,  121,  122, 1111, 1122, 1211]
    |   12|       [   1, 1121, 1122, 1211, 1212]| [ 112,  122, 1111]
    |  111|                   [   1, 1221, 1222]| [  11,  112, 1112, 1121, 1211]
    |  112|                         [   1,  121]| [  12,  111, 1112, 1212, 1221]
    |  121|                               [ 112]| [  11,  122, 1111, 1112, 1121, 1122, 1212]
    |  122|                               [1212]| [  11,   12,  121, 1112, 1122, 1211, 1221]
    | 1111|                               [1212]| [   1,   11,   12,  121, 1121, 1222]

t3t5u

Root| Node|                           EagerPeers| LazyPeers
----+-----+-------------------------------------+-------------------------------------------
   1|    1|             [  11,   12,  111,  112]| [1122]
    |   11|             [ 121,  122, 1111, 1112]| [1122]
    |   12|             [1121, 1122, 1211, 1212]| [ 122]
    |  111|             [   1,   11, 1221, 1222]| [1121]
    |  112|                   [  12,  111,  121]| [1221]
    |  121|             [ 122, 1111, 1112, 1121]| [1122]
    |  122|             [1122, 1211, 1212, 1221]| [ 121]
    | 1111|             [   1,   11,   12, 1222]| [1121]

t3t5u

Epidemic Broadcast Trees: Plumtree

Push-Lazy-Push Multicast Tree.

高いスケーラビリティ、信頼性 (Reliability) 、回復力 (Resiliency) を達成するため、 流行性のブロードキャスト (Epidemic Broadcast) と、 決定論的なツリーに基づくブロードキャスト (Deterministic Tree-Based Broadcast) を統合する。

純粋な Gossip Protocol と異なり、ブロードキャスト用のツリーを構築するフェーズで、冗長な転送経路が取り除かれるので、重複するメッセージが大量に転送されることはない。

t3t5u

HyParView

Hybrid Partial View Membership Protocol.

信頼できる Gossip Protocol に基づき、メンバーシップを維持するプロトコル。

Partial Views

各ノードの内部で動的に変化する、すべてのノードの識別子のサブセット。

t3t5u

Gossip Protocol

流行性のブロードキャスト (Epidemic Broadcast) によるプロトコル。

決定論的なツリーに基づくブロードキャスト (Deterministic Tree-Based Broadcast) と比較して、 信頼性 (Reliability) と回復力 (Resiliency) が高く、メッセージのロスは少ないが、 重複するメッセージが大量に転送されるため、あまりスケーラビリティは高くない。

基本的な仕組み

t3t5u

pg2+globalとgproc+gen_leaderの比較。

• pg2+globalはErlang/OTP標準のモジュール。
• gproc+gen_leaderはオープンソースの拡張モジュール。
• どちらもプロセスのグループを管理するためのモジュール。

---

想定する利用状況。

t3t5u

名前でプロセスを管理するモジュール

代表的な実装

名前	スコープ
BIF	ローカル
global	グローバル
gproc	ローカル/グローバル

t3t5u

gen_leaderについて

http://github.com/garret-smith/gen_leader_revival

概要

• gprocの内部で使われている。
• 候補ノードのリストからリーダを選択する。
• リーダの選択には死んでいないすべてのフォロワの合意が必要。
• ノード間の情報伝達はリーダを介して行う。

t3t5u

6.4 物理学者の方法

銀行家の方法と同様に物理学者の方法でも、累積した貯蓄ではなく累積した負債を使うことができる。 伝統的な物理学者の方法では、ポテンシャル関数Φは累積した貯蓄の下限を表す。 貯蓄の代わりに負債を使うには、それぞれのオブジェクトを、累積した負債の上限(少なくとも、累積した負債のうちのオブジェクトの部分の上限)を表すポテンシャルにマップする関数Ψで、関数Φを置き換える。 大ざっぱに言えば、ある演算の償却されるコストとは、その演算の完全なコスト(つまり共有されるコストと共有されないコスト)からポテンシャルの変化を減算したものである。 ある演算の完全なコストを算出する簡単な方法は、全ての計算が正格であると見せ掛けることであった。

累積した負債の変化は、全てポテンシャルの変化に反映される。 ある演算が共有されるコストを全く支払わないなら、そのポテンシャルの変化は共有されるコストに等しくなるので、その演算の償却されるコストは共有されないコストに等しくなる。