01 / 導讀
導讀
引用
Cachin, C., Guerraoui, R., & Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer.
章節概要
本書（約 320 頁）是一本教科書，講分散式程式設計的抽象，以及行程可能崩潰或遭受攻擊時實現這些抽象的演算法。前言指出，貫穿全書的主題是對不確定性和對抗性影響的容忍：網路延遲、故障和惡意攻擊。作者由簡單環境中的簡單抽象，逐步推進到更具挑戰性環境中的更復雜抽象，並常常在多種系統模型下實現同一個原語，以展示模型如何改變演算法。全書分兩部分：第一部分（第1–2章）建立共同基礎，第二部分（第3–6章）每章討論一個問題。第7章是簡短的結束章。第二版在第一版《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章：共識
- 共識：在存在故障行程的情況下，就提出的值達成一致。
- 全序廣播、原子提交、組成員關係：通過共識定義的抽象。
- 拜占庭變體：能容忍任意或惡意行為的對應版本。
評析
優點
- 模組化、漸進的設計。 先給出抽象的規約，然後在最簡單的模型中給出演算法，再在更難的模型中重新討論同一個原語，因此假設產生的影響清晰可見。
- 同時涵蓋崩潰與拜占庭故障。 第二版在第一版的基礎上增加了對惡意行程的安全性，第3–6章每章都在崩潰故障的版本之外給出拜占庭變體。
- 附解答的習題。 作者為習題花了大量時間，並附有全部習題的解答，意圖是把它們作為內容的一部分。容易的習題適合課堂，較難的適合自學。
- 自成一體。 前言稱本書是自足的，只需很少的演算法、邏輯、網路、安全和作業系統背景，就能理解其中的抽象。
- 配套材料。 書的網站提供講義、教程材料，以及第一版中基於 Appia 框架的 Java 實踐實現（已為本版更新）。
侷限
- 不是形式證明。 作者宣告書中沒有定理，正確性論證的目的是幫助理解而非形式證明；重點是抽象和演算法，而不是可計算性和複雜度。想了解不可能性結果或複雜度界的讀者需要參考其他資料。
- 偏形式而非實踐。 第二版的一位評論者（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 系統編寫並行程式。
想先了解各類系統，可先讀那些更寬泛的教材或實踐書；當你想要廣播、暫存器和共識的精確規約與演算法，並理解複製系統在故障和攻擊下為什麼會那樣表現時，再讀本書。
如何使用本書
作者把本書寫成面向本科或基礎研究生教學以及個人自學的教科書。具備演算法、一階邏輯、程式語言、網路、安全和作業系統的初步知識會有幫助，但不是必需的。
實用安排：
- 較短的基礎課程： 第1–2章，然後是第3至6章中僅涉及崩潰故障的版本；前言認為這是一門較短的課程，可以作為偏實踐的分散式程式設計課程的配套。
- 完整課程： 所有章節和習題，包括拜占庭演算法和隨機演算法。
- 按興趣選讀： 想了解複製與訊息傳遞讀第3章，儲存讀第4章，一致性協議讀第5章。
先做習題再看解答；作者說，被動學習無法獲得像樣的理解。網站上的 Appia 實踐程式碼可用來執行這些演算法。