Distributed System

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

分散アルゴリズム

定理

CAP 定理

CAP 定理は分散データベースシステムにおいて一貫性 (consistensy)、可用性 (availability)、分断耐性 (partition-tolerance) の 3 つの特性のうち 2 つまでしか満たすことができないという概念。…

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

マルチキャスト

ゴシッププロトコル

ゴシッププロトコル (gossip protocol, gossipping) または感染プロトコル (epidemic protocol) はネットワーク上での情報マルチキャストの方法。実社会でうわさ話や感染症が伝播する過程と似たモデルである。…

2019年3月12日(Tue) #Gossip

Hadoop

HDFS

HDFS (Hadoop distributed file system) は Hadoop で使用されている分散ファイルシステム。データを複数の計算機上に分散配置し、MapReduce を用いて各計算機上で並列分散処理を行うことができる。…

2018年10月23日(Tue) #HDFS

Peer to Peer

Peer to Peer (P2P) は対等な動作をする (明確な主従関係を持たない) ノードによるネットワークまたはシステムのモデル。クライアント/サーバシステム (C/S システム) におけるサーバはクライアントに対して一方的にサービスを提供する役割だったのに対して、P2P では一方的にサービスの提供者となるサーバは存在せず、それぞれの Peer が状況に応じてサーバとクライアント両方の役割を持つ。…

2017年12月27日(Wed) #P2P 作業中

Blockchain

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

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

ブロックチェーンコンセンサス概要

ブロックチェーンのコンテキストでコンセンサスと呼ばれているものは、分散システムで言うところのリーダー選出と合意のアルゴリズムまたはより抽象的なスキームを意味する。バズワード的に使用されており曖昧であるため文脈には注意する必要がある。…

2019年9月26日(Thu) #Blockchain #Consensus

Proof of Work

Proof of Work (PoW) はサービス要求者に何らかの作業を強制することによって DoS 攻撃やスパムメールの送信といった悪意のあるコンピューティング能力を使用を防止する実用上の対策である。…

2018年12月29日(Sat) #Blockchain

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: 用語

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