分散アルゴリズム
アルゴリズムや定理
分散システム
分散システム (distributed system) は、クライアント (エンドユーザ) から単一のシステムとして見えるように動作する、協調して動作する複数のコンピュータで構成されるシステム。…
CAP 定理
CAP 定理は分散データベースシステムにおいてネットワーク分断 (partitioning) が発生したときに一貫性 (consistensy) か可用性 (availability) のどちらかしか取ることができないという原則。…
ビザンチン障害耐性
BFT (Byzantine fault-tolerance) またはビザンチン障害耐性はビザンチン障害プロセスが含まれていても安全な合意を達成することのできる性質である (あるいはその性質を持つ合意アルゴリズムを BFT とも呼ぶ)。…
Practical Byzantine Fault Tolerance
PBFT (practical Byzantine Fault Tolerance) はビザンチン障害耐性をもつ分散合意アルゴリズムの 1 つ。それ以前に提案されていた研究レベルのいくつかの BFT アルゴリズムを改良し、実用的に利用できる水準となった最初の BFT アルゴリズムである。…
Federated Byzantine Agreement
Federated Byzantine Agreement (FBA; 連合ビザンチン合意) は合意に参加する参加者それぞれの信頼に基づくクォーラム (quorum) と呼ばれる部分ネットワークを形成する P2P 向けのコンセンサス機構である。…
ゴシッププロトコル
ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上で情報をマルチキャストする方法の一つ。…
クロック同期
コンピュータにおけるクロック同期 (clock synchronization) とは、複数のコンピュータやデバイスがそれぞれ持つ内部時計をある特定の基準クロックに合わせることを指す。一般的なデバイスでは、単に時刻合わせが行われていない場合のみならず、その内部時計が時間の経過とともに基準時刻から徐々にずれて行くクロックドリフト (clock drift) という現象が発生する。…
一貫性
Paxos
Paxos は分散システムにおいて複数のノード間で合意を形成するためのアルゴリズム。ノードの故障や通信遅延、部分的なネットワーク障害といった不確実性を許容する環境であっても、分散システム上の複数のノードが一貫した合意結果を得られるようにすることを目的とする。…
Version Vector
Version Vector (VV) は並行して発生するイベントの因果関係 (causality, happened-before relation) を追跡するための機構。因果一貫性 (causal consistency) と呼ばれる一貫性モデルにおいて、競合する更新の因果関係を追跡しながら表現するために使用されている。…
論文翻訳: Concise Server-Wide Causality Management for Eventually Consistent Data Stores
ノード論理クロックとキー論理クロックを使用して分散システムにおけるデータ更新の因果関係を追跡するための 2015 年の論文。
論文翻訳: Scalable and Accurate Causality Tracking for Eventually Consistent Stores
結果整合性を持つ Key-Value ストア間で更新の競合を検出し追跡するための機構である Version Vector を、空間的および時間的に効率化した Dotted Version Vectors (DVV) および Dotted Version Vector Sets (DVVS) に関する 2014 年の論文。…
論文翻訳: Detection of Mutual Inconsistency in Distributed Systems
バージョンベクトル (version vector) と起点 (origin point) を使用して、特定ファイルの複数のコピーに対して独立して行った操作による相互不整合 (mutual inconsistency) を検出する方法についての 1983 年の論文。…
論文翻訳: Conflict-free Replicated Data Types
因果一貫性を使用する Version Vector のような並行する更新を追跡できるシステムで自動的に競合を解決できるデータ型についての 2011 年の論文。
信頼性
分散ハッシュテーブル
分散ハッシュテーブル
分散データベースにおいて目的とするオブジェクトを効率的に検索するために特定のスキームに基づいてネットワークに配置する方法を分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) と呼ぶ。…
Tapestry
Tapestry(2,3) は PRR の論文(1)に基づいた Prefix ルーティングを行う分散ハッシュテーブルルゴリズム。RPP にノードの参加と離脱のアルゴリズムが追加されている。各ノードは SHA-1 を使用した ID (アドレス) が割り当てられ、アプリケーションにもエンドポイント GUID が割り当てられる。…
Chord
Chord はコンシステントハッシュ法 (consistent hashing) に基づく分散ハッシュテーブルである。対数メッシュのリンクを内包する論理リングで表される。
Kademlia
Kademlia は二分木構造に基づくシンプルで実用的な分散ハッシュテーブル (DHT; distributed hashtable) アルゴリズム。ネットワークの中から目的のノードを効率よく検索することのできる分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) の一つである。…
論文翻訳: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
Consistent Hashing を使用した分散ハッシュテーブルアルゴリズム Chord に関する 2001 年の論文。2003 年に似た内容で新しい論文 (2) が出ているのでそちらを参照したほうが良いかも知れない。…
論文翻訳: Kademlia: A Peer-to-peer Information System Based on the XOR Metric
二分探索木に基づき距離関数に XOR を使用する分散ハッシュテーブルアルゴリズム Kademlia に関する 2002 年の論文。ネットワーク全体では二分木の構造だが、個々のノードのルーティングテーブルはその部分木として見ることのできるリスト構造となる。…
コンシステントハッシュ法
コンシステントハッシュ法 (consistent hashing) は分散システムにおいて処理やデータを均等に分散させるためのハッシュ技術である。Chord のような分散ハッシュテーブルにおけるオブジェクトロケーションのアルゴリズムとして使用されている。…
分散データベース
分散データベース
HDFS
HDFS (Hadoop distributed file system) は Hadoop で使用されている分散ファイルシステム。データを複数の計算機上に分散配置し、MapReduce を用いて各計算機上で並列分散処理を行うことができる。…
論文翻訳: TiDB: A Raft-based HTAP Database
トランザクション処理と分析処理を統合した HTAP データベースであり、Raft アルゴリズムに基づいて高可用性とスケーラビリティを実現する TiDB に関する 2020 年の論文。行ストア (TiKV) と列ストア (TiFlash) を組み合わせ、最新のデータをリアルタイムで効率的に処理する。…
Peer to Peer
Peer to Peer
P2P (peer to peer) は対等な動作をする (明確な主従関係を持たない) ノードによるネットワークまたはシステムのモデル。従来のクライアント/サーバシステム (C/S システム) におけるサーバがクライアントに対して一方的にサービスを提供する役割だったのに対して、P2P ではそれぞれのピアが状況に応じてサーバとクライアント両方の役割を持つ。…
P2P ファイル共有
P2P ファイル共有は P2P ネットワーク技術を使用したファイルの配布と共有を行うサービス、アプリケーションまたはネットワーク。ダウンロードのネットワーク負荷をユーザ側で分散することから低コストでサービスを運営することができるが、一方で、データの管理を行うことができず、著作権管理や情報漏えいと言った法的な問題に巻き込まれることも多い。…
Winny
Winny (ウィニー) は Freenet をモデルに実装された P2P ファイル共有のためのアプリケーションまたはネットワークである。匿名性の高さと効率的で高速なキャッシュ機構で日本ユーザのコミュニティで広まり、日本の P2P ファイル共有ブーム、およびそれにまつわる違法コピー行為とハッキング被害の代名詞ともなった。…
InterPlanetary File System
IPFS (InterPlanetary File System) は Protocol Labs 社を中心に開発されている P2P 技術を使用したファイル配信のための分散ストレージおよびそのプロトコルの名称である。…
Blockchain
Blockchain
分散システムにおけるブロックチェーン (blockchain) とは、ビザンチン障害耐性をもつ分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。…
Blockchain: コンセンサス
一般的な分散システムの文脈でのコンセンサスは、一貫性 (consistency) を達成するための役割選出 (リーダー選挙)、合意、同期、競合の解決や調整といったメカニズムを包括的に指した言葉である。…
Proof of Work
Proof of Work (PoW) は何らかの作業を行ったことを証明することで目的の行為を行う許可が与えられるスキームである。サービス要求者に何らかの作業を強制することで、DoS 攻撃やスパムメールの送信といった短時間で大量の要求を繰り返して発行する悪意的なコンピューティング能力を利用を防止するための実用上の対策である。…
Bitcoin
Note: ビットコインのブロックチェーン
BCCC 2017 で行った bitcon のブロックチェーン技術に関するノート。
Tendermint
CometBFT 構造解説
CometBFT は強い一貫性を持つ分散システムを構築するためのソフトウェアおよびその SDK (software development kit)。プライベート/コンソーシアムブロックチェーン用途に特化している。…
Blockchain: Polkadot
Blockchain: 用語
Layer 2
マルチエージェントシステム
論文翻訳
論文翻訳: Impossibility of Distributed Consensus with One Faulty Process
コンセンサスの問題にはプロセスの非同期システムが含まれており、そのいくつかは信頼性が欠落していることがある。課題は、信頼できるプロセスが 2 値の下で合意することである。本論文では、この課題に対するどのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。…
論文翻訳: The Part-Time Parliament
Paxos に関する 1998 年の論文。戯曲めいた説明がしばしば理解を阻害すると言われるので Paxos Made Simple (2001) をあわせて読むと良い。Paxos 島やその議会は Lamport によるフィクションで実在しない。…
論文翻訳: Paxos Made Simple
Paxos に関する 2001 年の論文。独特のユーモラスにより世間にうまく伝わらなかった先の論文 "The part-time parliament" (5) をサマリーしたような内容となっている。…
論文翻訳: In Search of an Understandable Consensus Algorithm (Extended Version)
Raft は複製されたログを管理するためのコンセンサスアルゴリズムである。これは (Multi-) Paxosと同等の結果を生み出し Paxos と同程度に効率的だが、その構造は Paxos とは異なる; Raft によって Paxos よりも理解しやすく実用的なシステムを構築するためのより良い基盤が提供される。…
論文翻訳: Zab: High-performance broadcast for primary-backup systems
ZooKeeper のプライマリ-バックアップ間でトランザクションのアトミックブロードキャストに使われている ZAB に関する 2011 年の論文。
論文翻訳: 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 年の論文。
論文翻訳: DiemBFT v4: State Machine Replication in the Diem Blockchain
Diem Blockchain のコンセンサスアルゴリズム DiemBFT (旧名 LibraBFT) に関する 2021 年の論文。この v4 で 2 ラウンドで確定するように修正された。…
論文翻訳: The Sleepy Model of Consensus
暗号論的ハッシュ関数とゼロ知識証明を使ってプロセスごとに固有の乱数を内密に生成し、その値が既定のしきい値 \(\lambda\) より小さければ当選というスキーマの委員会選出を行う Sleepy Consensus に関する 2017 年の論文。…
論文翻訳: Constant Latency in Sleepy Consensus
検証可能な乱数を用いて委員会選出を行う Sleepy コンセンサスで動的な参加を可能にする 2022 年の論文。
論文翻訳: Synchronous Byzantine Agreement with Expected \(O(1)\) Rounds, Expected \(O(n^2)\) Communication, and Optimal Resilience ラウンド期待値 \(O(1)\)、通信期待値 \(O(n^2)\)、そして最適な回復力を備えた同期ビザンチン合意
2019 年の論文。
論文翻訳: XFT: Practical Fault Tolerance Beyond Crashes
ビザンチン障害耐性を持つ XPaxos の 2016 の論文。ビザンチン故障、非ビザンチン故障、パーティション分断障害の合計が \(f\) 以下であれば、全体で \(N=2f+1\) プロセスの構成で安全な SMR を行うことができる。…
論文翻訳: Consensus in the Presence of Partial Synchrony
DLS88 として知られる、部分同期モデルおよびクォーラムに関する 1988 年の論文。
論文翻訳: Authenticated Algorithms for Byzantine Agreement
非同期ビザンチンアトミックブロードキャストに関する 1983 年の論文。
論文翻訳: The Byzantine Generals Problem
ビザンチン将軍問題に関する 1982 年の論文。すべてのプロセスが完全グラフで接続している構成において、署名なしのアルゴリズムでビザンチン将軍問題を解くには \(n \ge 3m+1\) が必要。…
論文翻訳: Time, Clocks, and the Ordering of Events in a Distributed System
論理クロック (Lamport タイムスタンプ) に関する 1978 年の論文。
論文翻訳: Merkle-CRDTs: Merkle-DAGs meet CRDTs
分散システムにおけるデータの同期を効率的に行う、Merkle-DAG と CRDT を組み合わせたデータ構造である Merkle-CRDTs に関する 2020 年の論文。
論文翻訳: A Tree Clock Data Structure for Causal Orderings in Concurrent Executions
因果一貫性において、Version Vector の因果履歴をベクトルからツリー構造にすることで処理の計算量をレプリカ数に対する線形から劣線形に改善するという 2022 年の論文。
論文翻訳: GossipSub: A Secure PubSub Protocol for Unstructured, Decentralised P2P Overlays
非構造化分散型 P2P オーバーレイで使用される安全な pub/sub プロトコルである gosshipsub について説明する 2019 年の論文。
論文翻訳: FileDAG: A Multi-Version Decentralized Storage Network Built on DAG-based Blockchain
論文翻訳: Large-scale Incremental Processing Using Distributed Transactions and Notifications
小規模なデータ変更を効率的に反映しながら、分散トランザクションと通知メカニズムを追加してリアルタイムに近い更新を可能にした、従来の MapReduce によるバッチ処理システムの代替として設計された Google Percolator に関する 2010 年の論文。…
論文翻訳: Spanner: Google's Globally-Distributed Database
Google が開発したスケーラブルで広域に分散されたデータベース Spanner に関する 2013 年の論文。TrueTime API を用いて分散トランザクションと線形化可能な外部一貫性を表現している。…
論文翻訳: MultiPaxos Made Complete
リーダー選出、障害検出器、コミットフェーズなど、MultiPaxos を構成する各コンポーネントの詳細な分析とステップバイステップのコードを含むオープンソースによって正確な実装を提供することを目的とした 2024 年の論文。…
論文翻訳: Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency
分散ファイルキャッシュの整合性を効率的かつ耐障害性を持って維持するための「リース」という時間ベースのメカニズムを提案する 1989 年の論文。
論文翻訳: Consensus: Bridging Theory and Practice
分散システムにおける障害耐性を実現するコンセンサスアルゴリズム Raft を詳述した 2014 年の論文。従来の Paxos の複雑さを解消し「理解可能性」を最重視して設計されており、リーダー選挙、ログ複製、クラスタメンバーシップ変更、ログ圧縮など、実運用に必要なあらゆる側面を包括的に議論している。…
