Distributed System

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

分散システムに関するあれこれ。

分散アルゴリズム

アルゴリズムや定理

分散システム

2019年4月25日(Thu)

CAP 定理

CAP 定理は分散データベースシステムにおいてネットワーク分断 (partitioning) が発生したときに一貫性 (consistensy) か可用性 (availability) のどちらかしか取ることができないという原則。…

2019年6月18日(Tue) #CAPTheorem

ビザンチン合意問題

ビザンチン合意問題 (Byzantine agreement problem; ビザンチン将軍問題) は分散システムにおけるサブシステム間の合意の困難さを表す例として挙げられる想定問題である。…

2019年6月24日(Mon) #Byzantine #PBFT

Practical Byzantine Fault Tolerance

PBFT (practical Byzantine Fault Tolerance) はビザンチン障害耐性をもつ分散合意アルゴリズムの 1 つ。それ以前に提案されていた研究レベルのいくつかの BFT アルゴリズムを改良し、実用的に利用できる水準となった最初の BFT アルゴリズムである。…

2018年12月25日(Tue) #PBFT #BFT

Federated Byzantine Agreement

Federated Byzantine Agreement (FBA; 連合ビザンチン合意) は合意に参加する参加者それぞれの信頼に基づくクォーラム (quorum) と呼ばれる部分ネットワークを形成する P2P 向けのコンセンサス機構である。…

2021年9月20日(Mon) #FBA

ゴシッププロトコル

ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上で情報をマルチキャストする方法の一つ。…

2019年3月12日(Tue) #Gossip

分散ハッシュテーブル

分散データベースにおいて目的とするオブジェクトを効率的に検索するために特定のスキームに基づいてネットワークに配置する方法を分散オブジェクトロケーション/ルーティング (DOLR; decentralized object location and routing) と呼ぶ。…

2020年7月21日(Tue) #P2P #DHT #DOLR #Tapestry

Tapestry

Tapestry(2,3) は PRR の論文(1)に基づいた Prefix ルーティングを行う分散ハッシュテーブルルゴリズム。RPP にノードの参加と離脱のアルゴリズムが追加されている。各ノードは SHA-1 を使用した ID (アドレス) が割り当てられ、アプリケーションにもエンドポイント GUID が割り当てられる。…

2020年8月12日(Wed) #DHT #Tapestry

Chord

Chord は Consistent Hashing に基づく分散ハッシュテーブル。対数メッシュのリンクを内包する論理リングで表される。

2020年8月27日(Thu) #P2P #DHT #Chord

Kademlia

Kademlia は二分木構造に基づく実用的な分散ハッシュテーブルアルゴリズム。P2P ファイル共有では Gnutella, BitTorrent, IPFS で使用されており、ブロックチェーンではアイディアや PoC として Ethereum 1 や Storj, Dfinity などのノード検索で検討されている。…

2020年8月30日(Sun) #P2P #DHT #Kademlia

論文翻訳: Kademlia: A Peer-to-peer Information System Based on the XOR Metric

二分探索木に基づき距離関数に XOR を使用する分散ハッシュテーブルアルゴリズム Kademlia に関する 2002 年の論文。ネットワーク全体では二分木の構造だが、個々のノードのルーティングテーブルはその部分木として見ることのできるリスト構造となる。…

2020年8月30日(Sun) 2002年の論文 #P2P #DHT #Kademlia

Version Vector

Version Vector (VV) は並行して発生するイベントの因果関係 (causality, happened-before relation) を追跡するための機構。因果一貫性 (causal consistency) と呼ばれる一貫性モデルにおいて、競合する更新の因果関係を追跡しながら表現するために使用されている。…

2021年8月28日(Sat) #VV #VersionVector

論文翻訳: Concise Server-Wide Causality Management for Eventually Consistent Data Stores

ノード論理クロックとキー論理クロックを使用して分散システムにおけるデータ更新の因果関係を追跡するための 2015 年の論文。

2021年7月18日(Sun) 2015年の論文 #BVV

論文翻訳: Scalable and Accurate Causality Tracking for Eventually Consistent Stores

結果整合性を持つ Key-Value ストア間で更新の競合を検出し追跡するための機構である Version Vector を、空間的および時間的に効率化した Dotted Version Vectors (DVV) および Dotted Version Vector Sets (DVVS) に関する 2014 年の論文。…

2021年8月22日(Sun) 2014年の論文 #DVV

論文翻訳: Detection of Mutual Inconsistency in Distributed Systems

バージョンベクトル (version vector) と起点 (origin point) を使用して、特定ファイルの複数のコピーに対して独立して行った操作による相互不整合 (mutual inconsistency) を検出する方法についての 1983 年の論文。…

2021年8月19日(Thu) 1983年の論文 #VersionVector #VV

論文翻訳: Conflict-free Replicated Data Types

因果一貫性を使用する Version Vector のような並行する更新を追跡できるシステムで自動的に競合を解決できるデータ型についての 2011 年の論文。

2021年9月4日(Sat) 2011年の論文 #CRDT

Hadoop

Peer to Peer

Blockchain

Blockchain

分散システムにおけるブロックチェーン (blockchain) とは、ビザンチン障害耐性をもつ分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。…

2019年1月5日(Sat) #Blockchain #Bitcoin #Ethereum #DistributedLedger #暗号通貨

Blockchain: コンセンサス

一般的な分散システムの文脈でのコンセンサスは、一貫性 (consistency) を達成するための役割選出 (リーダー選挙)、合意、同期、競合の解決や調整といったメカニズムを包括的に指した言葉である。…

2021年8月31日(Tue) #Blockchain #Consensus

Proof of Work

Proof of Work (PoW) は何らかの作業を行ったことを証明することで目的の行為を行う許可が与えられるスキームである。サービス要求者に何らかの作業を強制することで、DoS 攻撃やスパムメールの送信といった短時間で大量の要求を繰り返して発行する悪意的なコンピューティング能力を利用を防止するための実用上の対策である。…

2018年12月29日(Sat) #Blockchain #PoW

Bitcoin

2019年6月4日(Tue) #Blockchain #Bitcoin #暗号通貨

Note: ビットコインのブロックチェーン

BCCC 2017 で行った bitcon のブロックチェーン技術に関するノート。

2017年10月27日(Fri) #bitcoin #blockchain

Tendermint

2019年7月16日(Tue) Tendermint 0.32 #Blockchain #Tendermint 作業中

Blockchain: Polkadot

2019年9月26日(Thu) #polkadot

Blockchain: 用語

2019年9月17日(Tue) #Blockchain

論文翻訳

論文翻訳: Impossibility of Distributed Consensus with One Faulty Process

コンセンサスの問題にはプロセスの非同期システムが含まれており、そのいくつかは信頼性が欠落していることがある。課題は、信頼できるプロセスが 2 値の下で合意することである。本論文では、この課題に対するどのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。…

2019年4月25日(Thu) 1985年の論文 #FLP #Reliability

論文翻訳: In Search of an Understandable Consensus Algorithm (Extended Version)

Raft は複製されたログを管理するためのコンセンサスアルゴリズムである。これは (Multi-) Paxosと同等の結果を生み出し Paxos と同程度に効率的だが、その構造は Paxos とは異なる; Raft によって Paxos よりも理解しやすく実用的なシステムを構築するためのより良い基盤が提供される。…

2019年5月20日(Mon) 2014年の論文 #Raft

論文翻訳: Zab: High-performance broadcast for primary-backup systems

ZooKeeper のプライマリ-バックアップ間でトランザクションのアトミックブロードキャストに使われている ZAB に関する 2011 年の論文。

2021年9月21日(Tue) 2011年の論文 #ZAB #ZooKeeper

論文翻訳: Practical Byzantine Fault Tolerance

Byzantine Fault Tolerance 合意アルゴリズムを実装面で補強した 1999 年の論文。

2019年7月7日(Sun) 1999年の論文 #PBFT

論文翻訳: HotStuff: BFT Consensus in the Lens of Blockchain

State Machine Replication を行うための BFT 合意アルゴリズム HotStuff に関する 2019 年の論文。ブロックチェーンのような頻繁なリーダー変更を行う環境向けに、通信コストが \(O(n^2)\) から \(O(n)\) となっている。…

2019年8月25日(Sun) 2019年の論文 #HotStuff #LibraBFT

論文翻訳: Skip Graphs

Skip Graph は、要素を格納する分散システムでバランスツリーの全機能を提供する、Skip List に基づく新しい分散データ構造である。要素はいつでも失敗する可能性のある別々のノードに格納される。…

2019年4月21日(Sun) 2003年の論文 #SkipGraph 作業中

論文翻訳: Reaching Agreement in the Presence of Faults

ビザンチン故障を含むネットワークでの分散合意が可能な条件についての 1979 年の論文。

2019年6月16日(Sun) 1979年の論文 #BFT

論文翻訳: DFINITY Technology Overview Series Consensus System

Dfinity のテクニカルオーバービューを記述した 2018 年の論文。公証 (notalization) がブロックの承認を表している? 少し用語の言い替えがある。

2020年2月16日(Sun) 2018年の論文 #Blockchain #DFINITY 作業中

翻訳: The ZILLIQA Technical Whitepaper

既存の暗号通貨及びスマートコントラクトプラットフォームはスケーラビリティの問題を抱えている。すなはち、1秒間に処理できるトランザクションの数が制限されており、通常 10 未満であることが知られている。…

2019年1月28日(Mon) 2017年の論文 #Blockchain #Zilliqa

論文翻訳: Byzantine Finality Gadgets

Polkadot で検討されている、重み付き PoW を使った分岐の発生するコンセンサスにファイナリティ特性を追加するための PoS に基づいたアルゴリズムに関する 2019 年の提示文書。…

2019年9月26日(Thu) 2019年の論文 #Blockchain #Polkadot #GRANDPA 作業中

論文翻訳: Algorand: Scaling Byzantine Agreements for Cryptocurrencies

PoS に VRF (Verifiable Random Function) を組み合わせた選出を行う BFT 合意アルゴリズム Algorand に関する 2017 年の論文。

2019年8月20日(Tue) 2017年の論文 #Algorand 作業中

翻訳: Introduction to Transaction Management

2019年10月7日(Mon) 作業中

論文翻訳: The latest gossip on BFT consensus

Tendermint のコンセンサスに関する 2018 年の論文。

2021年4月17日(Sat) 2018年の論文 #Blockchain #Tendermint #BFT

論文翻訳: Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin

優先度を重みづけされたプロセッサにラウンドロビンでジョブを割り当てるアルゴリズムに関する 2009 年の論文。

2020年4月25日(Sat) 2009年の論文

論文翻訳: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Consistent Hashing を使用した分散ハッシュテーブルアルゴリズム Chord に関する 2001 年の論文。2003 年に似た内容で新しい論文 (2) が出ているのでそちらを参照したほうが良いかも知れない。…

2020年8月18日(Tue) 2001年の論文 #P2P #DHT #Chord
F