Tetsuro Sano t3t5u

Epidemic Broadcast Trees: Plumtree

Push-Lazy-Push Multicast Tree.

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

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

HyParView

Hybrid Partial View Membership Protocol.

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

Partial Views

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

Gossip Protocol

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

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

基本的な仕組み

pg2+globalとgproc+gen_leaderの比較。

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

想定する利用状況。

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

代表的な実装

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

`gen_leader`について

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

概要

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

6.4 物理学者の方法

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

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

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

	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]

	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]