分散アルゴリズム
アルゴリズムや定理
分散システム
CAP 定理
CAP 定理は分散データベースシステムにおいて一貫性 (consistensy)、可用性 (availability)、分断耐性 (partition-tolerance) の 3 つの特性のうち 2 つまでしか満たすことができないという概念。…
ビザンチン合意問題
ビザンチン合意問題 (Byzantine agreement problem; ビザンチン将軍問題) は分散システムにおけるサブシステム間の合意の困難さを表す例として挙げられる想定問題である。…
Practical Byzantine Fault Tolerance
PBFT (practical Byzantine Fault Tolerance) はビザンチン障害耐性をもつ分散合意アルゴリズムの 1 つ。それ以前に提案されていた研究レベルのいくつかの BFT アルゴリズムを改良し、実用的に利用できる水準となった最初の BFT アルゴリズムである。…
ゴシッププロトコル
ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上での情報マルチキャストの方法。実社会でうわさ話や感染症が伝播する過程と似たモデルである。…
分散ハッシュテーブル
分散データベースにおいて目的とするオブジェクトを効率的に検索するために特定のスキームに基づいてネットワークに配置する方法を分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) と呼ぶ。…
Tapestry
Tapestry(2,3) は PRR の論文(1)に基づいた Prefix ルーティングを行う分散ハッシュテーブルルゴリズム。RPP にノードの参加と離脱のアルゴリズムが追加されている。各ノードは SHA-1 を使用した ID (アドレス) が割り当てられ、アプリケーションにもエンドポイント GUID が割り当てられる。…
Chord
Chord は Consistent Hashing に基づく分散ハッシュテーブル。対数メッシュのリンクを内包する論理リングで表される。
Kademlia
Kademlia は二分木構造に基づく実用的な分散ハッシュテーブルアルゴリズム。P2P ファイル共有では Gnutella, BitTorrent, IPFS で使用されており、ブロックチェーンではアイディアや PoC として Ethereum 1 や Storj, Dfinity などのノード検索で検討されている。…
論文翻訳: Kademlia: A Peer-to-peer Information System Based on the XOR Metric
二分探索木に基づき距離関数に XOR を使用する分散ハッシュテーブルアルゴリズム Kademlia に関する 2002 年の論文。ネットワーク全体では二分木の構造だが、個々のノードのルーティングテーブルはその部分木として見ることのできるリスト構造となる。…
Hadoop
Peer to Peer
Peer to Peer
P2P (peer to peer) は対等な動作をする (明確な主従関係を持たない) ノードによるネットワークまたはシステムのモデル。従来のクライアント/サーバシステム (C/S システム) におけるサーバがクライアントに対して一方的にサービスを提供する役割だったのに対して、P2P ではそれぞれのピアが状況に応じてサーバとクライアント両方の役割を持つ。…
P2P ファイル共有
P2P ファイル共有は P2P ネットワーク技術を使用したファイルの配布と共有を行うサービス、アプリケーションまたはネットワーク。ダウンロードのネットワーク負荷をユーザ側で分散することから低コストでサービスを運営することができるが、一方で、データのマネジメントを行うことができず著作権管理や情報漏えいと言った法的な問題に巻き込まれることも多い。…
InterPlanetary File System
IPFS (InterPlanetary File System) は Protocol Labs 社を中心に開発されている P2P 技術を使用したファイル配信のための分散ストレージおよびそのプロトコルの名称である。…
Blockchain
Blockchain
分散システムにおけるブロックチェーン (blockchain) は、ビザンチン耐性のある分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。…
ブロックチェーンコンセンサス概要
ブロックチェーンのコンテキストでコンセンサスと呼ばれているものは、分散システムで言うところのリーダー選出と合意のアルゴリズムまたはより抽象的なスキームを意味する。バズワード的に使用されており曖昧であるため文脈には注意する必要がある。…
Proof of Work
Proof of Work (PoW) はサービス要求者に何らかの作業を強制することによって DoS 攻撃やスパムメールの送信といった悪意のあるコンピューティング能力を使用を防止する実用上の対策である。…
Bitcoin
Note: ビットコインのブロックチェーン
BCCC 2017 で行った bitcon のブロックチェーン技術に関するノート。
Tendermint
Blockchain: 用語
論文翻訳
論文翻訳: Impossibility of Distributed Consensus with One Faulty Process
コンセンサスの問題にはプロセスの非同期システムが含まれており、そのいくつかは信頼性が欠落していることがある。課題は、信頼できるプロセスが 2 値の下で合意することである。本論文では、この課題に対するどのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。…
論文翻訳: In Search of an Understandable Consensus Algorithm (Extended Version)
Raft は複製されたログを管理するためのコンセンサスアルゴリズムである。これは (Multi-) Paxosと同等の結果を生み出し Paxos と同程度に効率的だが、その構造は Paxos とは異なる; Raft によって Paxos よりも理解しやすく実用的なシステムを構築するためのより良い基盤が提供される。…
論文翻訳: Practical Byzantine Fault Tolerance
Byzantine Fault Tolerance 合意アルゴリズムを実装面で補強した 1999 年の論文。
論文翻訳: HotStuff: BFT Consensus in the Lens of Blockchain
State Machine Replication を行うための BFT 合意アルゴリズム HotStuff に関する 2019 年の論文。ブロックチェーンのような頻繁なリーダー変更を行う環境向けに、通信コストが \(O(n^2)\) から \(O(n)\) となっている。…
論文翻訳: Skip Graphs
Skip Graph は、要素を格納する分散システムでバランスツリーの全機能を提供する、Skip List に基づく新しい分散データ構造である。要素はいつでも失敗する可能性のある別々のノードに格納される。…
論文翻訳: Reaching Agreement in the Presence of Faults
ビザンチン故障を含むネットワークでの分散合意が可能な条件についての 1979 年の論文。
論文翻訳: DFINITY Technology Overview Series Consensus System
Dfinity のテクニカルオーバービューを記述した 2018 年の論文。公証 (notalization) がブロックの承認を表している? 少し用語の言い替えがある。
翻訳: The ZILLIQA Technical Whitepaper
既存の暗号通貨及びスマートコントラクトプラットフォームはスケーラビリティの問題を抱えている。すなはち、1秒間に処理できるトランザクションの数が制限されており、通常 10 未満であることが知られている。…
論文翻訳: Byzantine Finality Gadgets
Polkadot で検討されている、重み付き PoW を使った分岐の発生するコンセンサスにファイナリティ特性を追加するための PoS に基づいたアルゴリズムに関する 2019 年の提示文書。…
論文翻訳: Algorand: Scaling Byzantine Agreements for Cryptocurrencies
PoS に VRF (Verifiable Random Function) を組み合わせた選出を行う BFT 合意アルゴリズム Algorand に関する 2017 年の論文。
翻訳: Introduction to Transaction Management
論文翻訳: The latest gossip on BFT consensus
Tendermint のコンセンサスに関する 2018 年の論文。
論文翻訳: Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin
優先度を重みづけされたプロセッサにラウンドロビンでジョブを割り当てるアルゴリズムに関する 2009 年の論文。
論文翻訳: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
Consistent Hashing を使用した分散ハッシュテーブルアルゴリズム Chord に関する 2001 年の論文。2003 年に似た内容で新しい論文 (2) が出ているのでそちらを参照したほうが良いかも知れない。…