Tech

分散型コンセンサス・アルゴリズム プロトコル まとめ

  • このエントリーをはてなブックマークに追加

暗号通貨、ブロックチェーン技術の方向からの分散型合意形成(コンセンサス)アルゴリズム、メカニズムの説明になります。

  • 書き途中

コンセンサス・アルゴリズムとは何か?

  • 合意アルゴリズムと言われることも

以下のとの違いは不明瞭?

  • 分散コンセンサス (distributed consensus)
  • 分散型合意システム
  • 合意プロトコル

なぜ必要か?

Byzantine Agreement Protocol (synchronous)

  • 2PC (Two-phase Commit):
  • 3PC (Three-phase Commit):
  • Paxos: Microsoft/Lamport: (State machine replication)
  • Paxos
  • 実装例?: Aerospike, Zookeeper/Chubby, Megastore
  • Chubby: Google (serve strongly consistent files), Paxos実装?
  • Zab:

Raft

  • 本家: Raft Consensus Algorithm
  • 参考 日本語スライド: Raft
  • Raftの解説がある CoreOS入門
  • ZooKeeper: Chubbyクローン, ZAB(ZooKeeper Atomic Broadcast)
  • etcdが利用している
  • Leader, Follower, Candidateから構成。
  • 大きなクラスタを組むのに適してない。適切なノードの数は、5から9?
  • P2P(全員同じ役割)なコンセンサス・アルゴリズムと違い、リーダーがいるモデル
  • はじめはフォロワー。キャンディデート(候補者)からリーダを選び、リーダーを中心にデータを送信、コミットしてから、合意に達するモデル
  • Raftを動的に理解できるスライド Raft

  • Raftを紹介する – obfuscatism

Paxos

  • 1990年に登場、命名。論文が出たのは1998年。
  • 実装の難易度が高い、と言われる
  • 故障に耐える合意プロトコルとしてきっちり証明されたのは、paxosが初?
  • p21: https://www.slideshare.net/kumagi/db-75506786

  • Paxosアルゴリズム – Wikipedia

PBFT

  • http://www.pmg.lcs.mit.edu/papers/osdi99.pdf

DLS

  • http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

POW: Proof of Work

  • Nakamoto Consensus: ビットコインのProof of Work
  • Dagger + Hashimoto (Ethereum)
  • Ethash (Ethereum)

POS: Proof of Stake

POSについては、以下にまとめています。
Proof of Stake とは何か? | block-chain.jp

POSのコンセンサス・アルゴリズム一覧

引用元: Blockchain Consensus Protocols

Stellar Consensus Protocol

  • SCP (Stellar Consensus Protocol) まとめ | block-chain.jp
  • ビザンチン (Byzantine): みんな共謀しようとする
  • 利他主義 (Altruistic): プロトコルにいつも従う
  • 合理的 (Rational): 合っていれば、プロトコルに従い、合わなければプロトコルに従わない

引用: Software and Bounded Rationality – Ethereum Blog

その他

地理分散データベース

  • 地理分散DBについて
  • Paxos, 2PC, 3PC, 2 Phase Lock, viewstamped replication, stake replication, MV2PL, Spanner, Replicated Commit, Calvin, FaunaDB,

日本語情報

スライド

関連用語

  • このエントリーをはてなブックマークに追加