Introduction to Reliable and Secure Distributed Programming（信頼性と安全性のある分散プログラミング入門）

引用

Cachin, C., Guerraoui, R., & Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer.

章の要約

本書（約 320 ページ）は、プロセスがクラッシュしたり攻撃されたりしうる状況での分散プログラミングの抽象と、それを実装するアルゴリズムを扱う教科書である。序文によれば全体の中心的な主題は、不確実性と敵対的な影響への耐性、すなわちネットワークの遅延、故障、悪意ある攻撃への耐性である。著者は単純な環境での単純な抽象から、より難しい環境でのより高度な抽象へと進み、同じプリミティブを複数のシステムモデルで実装することも多く、モデルがアルゴリズムをどう変えるかを示している。本書は二部構成で、第I部（第1〜2章）が共通の土台を築き、第II部（第3〜6章）は一章につき一つの問題を扱う。第7章は短い結びの章である。第2版は初版『Introduction to Reliable Distributed Programming』（2006）に悪意ある振る舞いに対する安全性（ビザンチン耐故障性）を加えたもので、そのため書名に「Secure」が加わり、共著者も一人増えた。

第1章：はじめに

この章は、分散プログラミングの抽象を利用する応用を論じることで、その必要性を動機づける。分散プログラミングの抽象、エンド・ツー・エンド論、ソフトウェア部品、アルゴリズムの種類を扱い、本書全体でアルゴリズムの記述に使うモジュール式の記法と擬似コードを導入する。

第2章：基本的な抽象

この章は分散環境に関するさまざまな仮定と、システムモデルの一群を示す。序文はこの章を以降の章の参照用と見なしてよいとしている。主題は、分散計算、プロセスの抽象化、暗号の抽象、通信の抽象化、タイミングの仮定、時間の抽象化、そしてそこから得られる分散システムのモデルである。章末には演習と解答がある。

第3章：信頼できるブロードキャスト

メッセージをプロセスの集団に、さまざまな強さの配送保証でブロードキャストする。この章はベストエフォート型から、通常の、および一様（uniform）な信頼できるブロードキャスト、しつこい（stubborn）ブロードキャストとログ付きの変種、確率的ブロードキャスト、FIFO と因果ブロードキャスト、そして悪意ある故障に対するビザンチンの一貫ブロードキャスト、ビザンチンの信頼できるブロードキャスト、ビザンチンブロードキャストチャネルへと進む。序文の例は、送信者がクラッシュしても、あるプロセスに配送されたメッセージが全プロセスに配送されることを保証することである。

第4章：共有メモリ

共有メモリは、読み書き操作でアクセスされる分散ストレージのオブジェクトをモデル化する。たとえば分散ストレージシステムのファイルや、マルチプロセッサのレジスタである。この章は (1, N) の通常レジスタとアトミックレジスタ、(N, N) のアトミックレジスタ、ログ付きの通常レジスタ、そしてビザンチンの安全、通常、アトミックの各レジスタを構成し、一部のプロセスがクラッシュしたり、値を失ったり、誤ったデータを報告したりしても、値を取り出せるようにする。

第5章：合意

合意の抽象は、各プロセスが提案した値から、故障したプロセスがいても共通の値を決定できるようにする。この章は通常の合意、一様な合意（fail-noisy モデルでのものを含む）、ログ付き合意、ランダム化合意、ビザンチン合意、ビザンチンのランダム化合意を扱う。

第6章：合意の変種

合意を拡張または修正して得られる変種を扱う。全順序ブロードキャスト（とそのビザンチン版）、終了する信頼できるブロードキャスト、高速合意と高速ビザンチン合意、ノンブロッキングのアトミックコミット、グループメンバーシップ、ビュー同期通信である。

第7章：結び

Appia での実装、他の実装、さらに読むべき文献についての短い結びの章である。

主要概念

第1〜2章：抽象とモデル

• モジュールとイベントの記法：抽象とアルゴリズムを記述するためのモジュール式の擬似コードの書式。
• システムモデル：プロセスの抽象（クラッシュ故障とビザンチン故障）、リンクの抽象、タイミングの仮定。
• 暗号の抽象：ビザンチンのアルゴリズムが依拠する暗号プリミティブの抽象的な形。

第3〜4章：ブロードキャストとレジスタ

• 信頼できるブロードキャストと一様ブロードキャスト：クラッシュがあっても守られる配送保証。一様版はより強い。
• FIFO と因果ブロードキャスト：信頼できるブロードキャストの上に重ねる順序保証。
• 通常レジスタとアトミックレジスタ：共有ストレージの正確な正しさの条件。

第5〜6章：合意

• 合意：故障したプロセスがいても、提案された値について一致すること。
• 全順序ブロードキャスト、アトミックコミット、グループメンバーシップ：合意を通じて定義される抽象。
• ビザンチンの変種：任意の、または悪意ある振る舞いに耐える対応版。

批判的分析

長所

• モジュール的で段階的な設計。 抽象の仕様がまず示され、次に最も単純なモデルでのアルゴリズム、そしてより難しいモデルでの同じプリミティブの再検討が続くので、仮定の効果が見える。
• クラッシュ故障もビザンチン故障も。 第2版は初版に悪意あるプロセスに対する安全性を加えており、第3〜6章はいずれもクラッシュ故障版に加えてビザンチン版の変種を含む。
• 解答付きの演習。 著者は演習に多くの時間を費やし、全問の解答を載せて、内容の一部にするつもりだとしている。易しい問題は授業に、難しい問題は個人学習に向く。
• 自己完結的。 序文は本書が自己完結的であり、アルゴリズム、論理、ネットワーク、セキュリティ、OS の背景知識がごくわずかでも、ほとんどの抽象とアルゴリズムが理解できると述べる。
• 補助資料。 書籍サイトにはスライド、チュートリアル資料、および初版の Appia フレームワークによる Java の実習実装（この版向けに更新）がある。

短所

• 形式的な証明ではない。 著者は本書に定理はなく、正しさの議論は形式的証明ではなく理解のためのものだと述べている。焦点は抽象とアルゴリズムであり、計算可能性や計算量ではない。不可能性の結果や計算量の上界を求める読者は他の資料が必要になる。
• 実践より形式寄り。 第2版の評者の一人（Alex Popescu）は、形式的な観点からの見事な入門であり、「プログラミング」や「エンジニアリング」ではなく、合意、レジスタ、ブロードキャストといった分散システムの基礎を扱うと評している。
• 範囲。 初版の評者の一人（Seif Haridi）は、自己安定化アルゴリズムや、分散トランザクションのより詳しい説明など、扱われていない話題があると指摘した。
• 講義の進度。 初版の別の評者（Felix Freiling）は、低水準の抽象から終了する信頼できるブロードキャストまでを進めるだけで、プログラミング演習を除いても、証明についての補足資料を加えて丸一学期かかったと報告している。

コースにおける位置づけ

分散システムの書目の中で、形式的でアルゴリズム寄りの端にある。『Understanding Distributed Systems』はネットワークアプリケーションを作る、または運用する開発者向けの簡潔な入門書。van Steen と Tanenbaum の『Distributed Systems』や Coulouris らの『Distributed Systems: Concepts and Design』は、アーキテクチャ、通信、命名、複製、セキュリティを扱う総合的な教科書。『Designing Data-Intensive Applications』はデータシステムの実用的な研究で、『An Introduction to Parallel Programming』はマルチコア、クラスタ、GPU のための並列プログラムの書き方を扱う。

まずシステムそのものを知りたいなら、より広い教科書や実用書を先に読む。ブロードキャスト、レジスタ、合意の正確な仕様とアルゴリズムが欲しいとき、また複製システムが故障や攻撃のもとでなぜそのように振る舞うのかを理解したいときに、本書を読む。

本書の使い方

著者は、学部または大学院初級の授業と独習のための教科書として本書を書いた。アルゴリズム、一階論理、プログラミング言語、ネットワーク、セキュリティ、OS の初歩的な知識があると役立つが、必須ではない。

実用的な進め方：

• 短い基礎コース： 第1〜2章、続いて第3〜6章のクラッシュ故障のみの版。序文はこれを短めのコースであり、実践寄りの分散プログラミングの講義の補完になると述べている。
• 完全なコース： ビザンチンおよびランダム化アルゴリズムを含む、すべての章と演習。
• 関心に応じて： 複製とメッセージングは第3章、ストレージは第4章、合意は第5章。

解答を見る前に演習を解くこと。著者は、受け身では相応の理解は得られないと述べている。サイトにある Appia の実習コードを使えば、アルゴリズムを動かしてみることができる。