1. Qiita
  2. 投稿
  3. Consensus

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

  • 25
    いいね
  • 0
    コメント

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

  • 書き途中

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

  • 分散コンセンサス (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

実装の難易度が高い、と言われる

PBFT

DLS

POW: Proof of Work

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

POS: Proof of Stake

POSについては、以下にまとめています。
Proof of Stake とは何か? - Qiita

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

引用元: Blockchain Consensus Protocols

Stellar Consensus Protocol

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

引用: Software and Bounded Rationality - Ethereum Blog

日本語情報

スライド

関連用語