分散システム古典論文リスト2017
原題: Distributed Systems Classics (2017)
なぜ重要か
分散システム設計の基礎理論を10本に絞った本リストは、エンジニアが理論的根拠を正確に把握するための実用的な出発点となる。
エンジニアのNicolae Vartolomeiが2017年に公開し2022年に更新した分散システムの古典論文選集。Lamportの1978年論文「時刻・クロック・分散システムにおけるイベント順序」を筆頭に、Byzantine将軍問題（1982年）、FLP不可能性定理（1985年）、Paxos（1998年・2001年）、Bitcoin論文（2008年）、CRDT（2011年）、Raft（2014年）など計10本を収録する。
Vartolomeiが公開したこのリストは、分散システム研究の骨格を形成した10本の論文を年代順に並べた入門ガイドだ。
最古はLeslie Lamportが1978年に発表した「Time, Clocks, and the Ordering of Events in a Distributed System」。ネットワーク上でのイベント順序付けの基礎概念を定義し、後続研究のほぼすべてに引用される。1982年にはLamport・Shostak・Peaseが「Byzantine Generals Problem」を提示し、悪意あるノードが混在する環境での合意形成問題を形式化した。
1985年には二つの重要論文が登場する。ChandyとLamportによる「Distributed Snapshots」は、稼働中の分散システムのグローバル状態を整合的に記録する手法を示した。FisherとLynchとPatersonによるFLP不可能性定理は「障害プロセスが1つでも存在すれば非同期分散システムでの合意は不可能」と証明し、以降の設計指針を根本から変えた。
1988年のViewstamped Replication（OkiとLiskov）は後のPaxosやRaftに直接つながる一次コピー方式を提案。Lamportは1998年に「The Part-Time Parliament」でPaxosを発表し、2001年に平易な解説版「Paxos Made Simple」を公開した。
2008年にはSatoshi NakamotoのBitcoin論文がP2P型電子現金の設計を提示。2011年のCRDT論文（Shapiroら）は競合なく複製可能なデータ型を定義し、分散データベースやコラボレーションツールの実装に広く採用された。2014年のRaft論文（OngaroとOusterhout）はPaxosより理解しやすい合意アルゴリズムとして設計され、現在多くのプロダクションシステムで使われている。