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 实践代码可用来运行这些算法。