Gossip Protocol

論文

• PODC’87: Epidemic algorithms for replicated database maintenance

概要

• データベースの一貫性維持を信頼性の低いネットワークで行うことは困難
• Randomized algorithmで解決していく
• 以下3つの手法を検討
  • Direct mail
    • 更新は、更新がおきたサイトから他のすべてのサイトへ直ちに送られる
    • 信頼性の低いネットワークでは難しい。(それに、すべてのサイトを知っているとも限らない←P2P的な仮定)
  • Anti-entropy
    • 全てのサイトは、ランダムに他のサイトを選択して、状態を共有し合って一貫性を維持する
    • Direct mailより更新の伝播が遅い
  • Rumor mongering ← これがGossip
    • 噂話モデル
    • 新しい更新を受け取ると、Hot rumorとして保持し、定期的に他のサイトをランダムに選び送りつける
      • 相手がすでに知っていたら、Hotではないとして伝播をやめていく

Notation

• $S$: サイトの集合。$|S|=n$。
• $s\in S$におけるDBのコピーは以下の関数を持つ
  • $s.valueOf:K\to (v:V\times t:T)$
  • $K$: キーの集合、$V$: 値の集合、$T$: タイムスタンプ
  • $s.valueOf[k]=(NIL,t)$は、$k$に対応する値は削除されたことを示す。
  • 単一キーに絞ると、$s.\text{ValueOf}\in (v:V\times t:T)$
• 全てのサイト間で一貫性がある状態: $\forall s,s^{\prime }:s.\text{ValueOf}=s^{\prime }.\text{valueOf}$
• 更新操作: $Update[v:V]\equiv s.ValueOf\leftarrow (v,Now)$

Direct Mail

• 自分のサイトで更新が起きたら、以下をやる

FOR EACH s' ∈ S DO
	PostMail[to: s', msg: ("Update", s.ValueOf)]
	ENDLOOP

• 更新メッセージ$(\text{"Update"},(v,t))$を受け取ったサイトは以下をやる

IF s.ValueOf.t < t THEN
	s.ValueOf ← (v, t)

Anti-entropy

• 各サイトが以下をやる
• Pull型、Push型、Push-Pull型がある

FOR SOME s' ∈ S DO
	ResolveDifference[s, s']
	ENDLOOP

ResolveDifference: PROC[s, s'] = {  // PUSH
	IF s.ValueOf.t > s'.ValueOf.t THEN
		s'.ValueOf ← s.ValueOf
}

ResolveDifference: PROC[s, s'] = {  // PULL
	IF s.ValueOf.t < s'.ValueOf.t THEN
		s.ValueOf ← s'.ValueOf
}

ResolveDifference: PROC[s, s'] = {  // PUSH-PULL
	SELECT TRUE FROM
		IF s.ValueOf.t > s'.ValueOf.t ⇛ s'.ValueOf ← s.ValueOf
		IF s.ValueOf.t < s'.ValueOf.t ⇛ s.ValueOf ← s'.ValueOf
		ENDCASE => NULL
}

• Push: $lo{g}_2(n)+\ln (n)+O(1)$ラウンドでいきわたる (証明: Boris Pittel: On Spreading a Rumor)
  • 序盤で速いが、Unreach問題がある
• Pull: 確率的に到達保証ができる。
• Push-Pull: 序盤で速いし、到達保証もできる