前辅文
 第一章 引言
  1.1 定义
  1.2 与计算机系统部件的关系
  1.3 动机
  1.4 与并行多处理器/多计算机系统的关系
   1.4.1 并行系统的特性
   1.4.2 Flynn的分类法
   1.4.3 耦合、并行、并发及粒度
  1.5 消息传递系统与共享内存系统的对比
   1.5.1 在共享内存的系统上仿真消息传递
   1.5.2 在消息传递系统上仿真共享内存
  1.6 分布式通信的原语
   1.6.1 阻塞/非阻塞,同步/异步原语
   1.6.2 处理器同步性
   1.6.3 库与标准
  1.7 同步与异步执行
   1.7.1 通过同步系统仿真异步系统
   1.7.2 通过异步系统仿真同步系统
   1.7.3 仿真
  1.8 设计主题与挑战
   1.8.1 从系统角度看分布式系统的挑战
   1.8.2 分布式计算中的算法挑战
   1.8.3 分布式计算的应用以及更新的挑战
  1.9 关于主题的选择与覆盖
  1.10 本章小结
  1.11 习题
  1.12 参考文献说明
  参考文献
 第二章 分布式计算模型
  2.1 分布式程序
  2.2 分布式运行模型
  2.3 通信网络模型
  2.4 分布式系统的全局状态
   2.4.1 全局状态
  2.5 分布式计算的运行分割
  2.6 事件的过去和未来锥面
  2.7 进程通信模型
  2.8 本章小结
  2.9 习题
  2.10 参考文献说明
  参考文献
 第三章 逻辑时间
  3.1 引言
  3.2 逻辑时钟框架
   3.2.1 定义
   3.2.2 实现逻辑时钟
  3.3 标量时间
   3.3.1 定义
   3.3.2 基本性质
  3.4 向量时间
   3.4.1 定义
   3.4.2 基本性质
   3.4.3 有关向量时钟的大小
  3.5 向量时钟的有效实现
   3.5.1 Singhal-KshemkalyaniSinghal-Kshemkalyani的差量技术
   3.5.2 Fowler-ZwaenepoelFowler-Zwaenepoel的直接依赖技术
  3.6 Jard-Jourdan的自适应技术
  3.7 矩阵时间
   3.7.1 定义
   3.7.2 基本性质
  3.8 虚拟时间
   3.8.1 虚拟时间的定义
   3.8.2 与Lamport逻辑时钟比较
   3.8.3 时间变形机制
   3.8.4 本地控制机制
   3.8.5 全局控制机制
  3.9 物理时钟同步：NTP
   3.9.1 动机
   3.9.2 定义及术语
   3.9.3 时钟不准确性
  3.10 本章小结
  3.11 习题
  3.12 参考文献说明
  参考文献
 第四章 记录全局状态与快照算法
  4.1 引言
  4.2 系统模型和定义
   4.2.1 系统模型
   4.2.2 一致性全局状态
   4.2.3 有关分割的解
   4.2.4 记录全局快照时遇到的问题
  4.3 FIFO通道的快照算法
   4.3.1 Chandy-LamportChandy-Lamport算法
   4.3.2 被记录全局状态的性质
  4.4 Chandy-Lamport算法的变种
   4.4.1 Spezialetti-KearnsSpezialetti-Kearns算法
   4.4.2 Venkatesan快照增量Venkatesan快照增量算法
   4.4.3 HelaryHelary波同步方法
  4.5 非FIFO通道的快照算法
   4.5.1 Lai-YangLai-Yang算法
   4.5.2 Li等人的算法
   4.5.3 MatternMattern算法
  4.6 因果传递系统快照
   4.6.1 进程状态记录
   4.6.2 Acharya-BadrinathAcharya-Badrinath算法中的通道状态记录通道状态记录
   4.6.3 Alagar-VenkatesanAlagar-Venkatesan算法中的通道状态记录
  4.7 监控全局状态
  4.8 一致性全局快照的必要和充分条件
   4.8.1 Zigzag路径和一致性全局快照
  4.9 找出分布式计算中的一致性全局快照
   4.9.1 找出一致性全局快照
   4.9.2 枚举式一致性快照Manivannan-Netzer-Singhal算法
   4.9.3 在分布式计算中找出Z路径
  4.10 本章小结
  4.11 习题
  4.12 参考文献说明
  参考文献
 第五章 术语和基本算法
  5.1 拓扑抽象和覆盖
  5.2 分类和基本概念
   5.2.1 应用执行和控制算法执行
   5.2.2 集中式算法和分布式算法
   5.2.3 对称算法和非对称算法
   5.2.4 匿名算法匿名算法
   5.2.5 一致算法一致算法
   5.2.6 自适应算法自适应算法
   5.2.7 确定性执行确定性执行对非确定性执行非确定性执行
   5.2.8 执行抑制抑制
   5.2.9 同步系统和异步系统异步系统
   5.2.10 联机算法与脱机算法
   5.2.11 故障模型
   5.2.12 无需等待算法无需等待算法
   5.2.13 通信通道
  5.3 复杂度测量和度量
  5.4 程序结构
  5.5 图的基本算法
   5.5.1 使用洪泛法的同步单一启动者生成树算法
   5.5.2 使用洪泛法的异步单一启动者生成树算法
   5.5.3 使用洪泛法的异步并发启动者生成树算法
   5.5.4 异步并发启动者深度优先搜索生成树算法
   5.5.5 在一棵树上广播广播和聚播聚播
   5.5.6 单一源最短路径算法：同步Bellman-Ford
   5.5.7 距离向量路径选择
   5.5.8 单一源最短路径算法：异步Bellman-Ford
   5.5.9 全源最短路径：异步分布式Floyd-Warshall
   5.5.10 有约束的异步和同步洪泛法（W/O一棵生成树）
   5.5.11 同步系统的最小权重生成树算法
   5.5.12 异步系统的最小权重树
  5.6 同步同步工具
  5.7 最大独立集合
  5.8 连通支配集
  5.9 紧凑路由表
  5.10 选领导者
  5.11 设计分布式图算法图算法的挑战
  5.12 对象副本对象副本问题
   5.12.1 问题定义
   5.12.2 算法概要
   5.12.3 读和写
   5.12.4 收敛到一个副本模式
  5.13 本章小结
  5.14 习题
  5.15 参考文献说明
  参考文献
 第六章 消息序与组通信
  6.1 消息序消息序的模式
   6.1.1 异步执行过程
   6.1.2 先进先出执行过程
   6.1.3 因果序执行过程
   6.1.4 同步执行过程
  6.2 使用同步通信的异步执行过程
   6.2.1 用同步通信可实现的执行过程
   6.2.2 序样式的层次体系
   6.2.3 两种仿真
  6.3 异步系统中同步程序的序
   6.3.1 会合会合
   6.3.2 双路会合算法
  6.4 组通信组通信
  6.5 因果序因果序
   6.5.1 Raynal-Schiper-Toueg算法［22］
   6.5.2 Kshemkalyani-Singhai最优算法［20,21］
  6.6 全序全序
   6.6.1 为全序设计的集中式算法
   6.6.2 三阶段分布式算法
  6.7 多播多播相关术语
  6.8 多播传播树
  6.9 应用层多播算法的分类
  6.10 容错组通信的语义
  6.11 网络层的分布式多播算法
   6.11.1 泛洪约束的反向路径转发
   6.11.2 Steiner树
   6.11.3 多播的成本函数
   6.11.4 有界延迟的Steiner树
   6.11.5 核基树
  6.12 本章小结
  6.13 习题
  6.14 参考文献说明
  参考文献
 第七章 终止检测
  7.1 引言
  7.2 分布式计算的系统模型
  7.3 基于快照的终止检测终止检测算法
   7.3.1 非形式化描述
   7.3.2 形式化描述
   7.3.3 讨论
  7.4 信用-传递终止检测算法
   7.4.1 形式化描述
   7.4.2 算法的正确性
  7.5 基于生成树生成树的终止检测算法
   7.5.1 定义
   7.5.2 一个简单的算法
   7.5.3 正确的算法
   7.5.4 一个例子
   7.5.5 算法性能分析
  7.6 消息-优化终止检测算法
   7.6.1 主要思想
   7.6.2 算法描述
   7.6.3 算法性能分析
  7.7 通用分布式计算模型中的终止检测
   7.7.1 模型定义和假设
   7.7.2 符号
   7.7.3 终止定义
   7.7.4 一个静态终止检测静态终止检测算法
   7.7.5 一个动态终止检测动态终止检测算法
  7.8 原子计算模型中的终止检测
   7.8.1 执行的原子模型
   7.8.2 一个简单的计数方法
   7.8.3 四计数器方法
   7.8.4 怀疑论者算法
   7.8.5 时间算法
   7.8.6 向量计数算法
   7.8.7 信道计数算法
  7.9 带错分布式系统中的终止检测
   7.9.1 流检测方案
   7.9.2 捕获快照快照
   7.9.3 算法描述
   7.9.4 算法性能分析
  7.10 本章小结
  7.11 习题
  7.12 参考文献说明
  参考文献
 第八章 知识推理
  8.1 Muddy children难题Muddy children难题
  8.2 知识的逻辑
   8.2.1 知识操作符
   8.2.2 回到muddy children难题
   8.2.3 克里普克结构
   8.2.4 使用克里普克结构解决muddy children难题
   8.2.5 知识的属性
  8.3 同步系统中的知识
  8.4 异步系统中的知识
   8.4.1 逻辑和定义
   8.4.2 异步系统中的达成一致
   8.4.3 共同知识共同知识的变体
   8.4.4 并发共同知识
  8.5 知识转移
  8.6 知识和时钟
  8.7 本章小结
  8.8 习题
  8.9 参考文献说明
  参考文献
 第九章 分布式互斥算法
  9.1 引言
  9.2 预备知识
   9.2.1 系统模型
   9.2.2 互斥算法的必备条件
   9.2.3 性能指标
  9.3 LamportLamport算法
  9.4 Ricart-AgrawalaRicart-Agrawala算法
  9.5 SinghalSinghal动态信息结构算法
   9.5.1 算法描述
   9.5.2 正确性
   9.5.3 性能分析
   9.5.4 异构流量模式下的适应性
  9.6 LodhaLodha和KshemkalyaniKshemkalyani的公平互斥算法
   9.6.1 系统模型
   9.6.2 算法描述
   9.6.3 安全性、公平性与活性
   9.6.4 消息复杂性
  9.7 基于仲裁团的互斥算法
  9.8 MaekawaMaekawa算法
   9.8.1 死锁死锁问题
  9.9 Agarwal-EI AbbadiAgarwal-EI Abbadi基于仲裁团的算法
   9.9.1 构造树状结构仲裁团
   9.9.2 构造树状结构仲裁团算法分析
   9.9.3 有效性
   9.9.4 树状结构仲裁团的例子
   9.9.5 分布式互斥算法
   9.9.6 正确性证明
  9.10 基于令牌的算法
  9.11 Suzuki-KasamiSuzuki-Kasami广播算法
  9.12 基于树的RaymondRaymond算法
   9.12.1 HOLDER变量
   9.12.2 算法操作
   9.12.3 算法描述
   9.12.4 正确性
   9.12.5 开销和性能分析
   9.12.6 算法初始化
   9.12.7 错误和恢复
  9.13 本章小结
  9.14 习题
  9.15 参考文献说明
  参考文献
 第十章 死锁检测
  10.1 简介
  10.2 系统模型
   10.2.1 等待图等待图
  10.3 预备知识
   10.3.1 死锁处理策略
   10.3.2 死锁检测问题死锁检测
  10.4 死锁模型
   10.4.1 单资源模型
   10.4.2 AND模型
   10.4.3 OR模型
   10.4.4 AND-OR模型
   10.4.5 pq模型
   10.4.6 无限制模型
  10.5 KnappKnapp分布式死锁检测算法分类
   10.5.1 路径推送算法
   10.5.2 边探测算法
   10.5.3 基于计算分散的算法
   10.5.4 基于全局状态检测的算法
  10.6 单资源模型下的MitchellMitchell-MerrittMerritt算法
  10.7 针对AND模型的ChandyChandy-MisraMisra-HaasHaas算法
  10.8 针对OR模型的ChandyChandy-MisraMisra-HaasHaas算法
  10.9 针对pq模型的KshemkalyaniKshemkalyani-SinghalSinghal算法
   10.9.1 算法的非正式描述
   10.9.2 算法描述
  10.10 本章小结
  10.11 习题
  10.12 参考文献说明
  参考文献
 第十一章 全局谓词的检测
  11.1 稳定谓词和不稳定谓词谓词
   11.1.1 稳定谓词谓词
   11.1.2 不稳定谓词
  11.2 谓词的形态
   11.2.1 谓词检测的复杂性
  11.3 关系谓词的集中式算法
  11.4 合取谓词
   11.4.1 合取谓词基于区间的集中式算法
   11.4.2 Possibly(Φ)基于全局状态的集中式算法
  11.5 合取谓词的分布式算法
   11.5.1 Possibly(Φ)基于状态的分布式令牌算法
   11.5.2 Definitely(Φ)基于区间的分布式令牌算法
   11.5.3 Possibly(Φ)基于区间的分布式捎带算法
  11.6 谓词的进一步分类
  11.7 本章小结
  11.8 习题
  11.9 参考文献说明
  参考文献
 第十二章 分布式共享内存
  12.1 抽象化及其优势
  12.2 内存一致性模型
   12.2.1 强一致性、原子一致性及线性
   12.2.2 顺序一致性
   12.2.3 因果一致性
   12.2.4 处理器一致性
   12.2.5 慢内存
   12.2.6 一致性模型的层次结构
   12.2.7 其他基于同步指令的一致性模型
  12.3 共享内存的互斥共享内存的互斥
   12.3.1 Lamport面包店算法
   12.3.2 Lamport’s WRWM技术和快速互斥
   12.3.3 互斥的硬件支持
  12.4 等待无关性
  12.5 寄存器层次寄存器层次和无等待模拟无等待模拟
   12.5.1 构造1：SRSW安全寄存器到MRSW安全寄存器
   12.5.2 构造2：SRSW普通寄存器到MRSW普通寄存器
   12.5.3 构造3：布尔MRSW安全寄存器到整数MRSW安全寄存器
   12.5.4 构造4：布尔MRSW安全寄存器到布尔MRSW普通寄存器
   12.5.5 构造5：布尔MRSW普通寄存器到整数MRSW普通寄存器
   12.5.6 构造6：布尔MRSW普通寄存器到整数MRSW原子寄存器
   12.5.7 构造7：整数MRSW原子寄存器到整数MRMW原子寄存器
   12.5.8 构造8：整数SRSW原子寄存器到整数MRSW原子寄存器
  12.6 共享对象的无等待原子快照无等待原子快照
  12.7 本章小结
  12.8 习题
  12.9 参考文献说明
  参考文献
 第十三章 检查点和卷回恢复
  13.1 介绍
  13.2 背景和定义
   13.2.1 系统模型
   13.2.2 本地检查点检查点
   13.2.3 一致的系统状态
   13.2.4 与外部世界的交互
   13.2.5 不同消息类型
  13.3 错误恢复错误恢复中的问题
  13.4 基于检查点的恢复
   13.4.1 无协作检查点
   13.4.2 协作式检查点
   13.4.3 最小处理无阻塞检查点的不可能性
   13.4.4 通信引导检查点
  13.5 基于日志的卷回恢复基于日志的卷回恢复
   13.5.1 确定事件和非确定事件
   13.5.2 悲观日志
   13.5.3 乐观日志
   13.5.4 因果日志
  13.6 KooKoo-TouegToueg协同检查点算法
   13.6.1 检查点算法
   13.6.2 卷回恢复算法
  13.7 异步检查点和恢复的JuangJuang-VenkatesanVenkatesan算法
   13.7.1 系统模型和假设
   13.7.2 异步检查点
   13.7.3 恢复算法
  13.8 ManivannanManivannan-SinghalSinghal准同步检查点算法
   13.8.1 检查点算法
   13.8.2 恢复算法
   13.8.3 复杂消息处理
  13.9 基于矢量时间矢量时间的PetersonPeterson-KearnsKearns算法
   13.9.1 系统模型
   13.9.2 算法的非形式化描述
   13.9.3 卷回协议的形式化描述
   13.9.4 正确性证明
  13.10 Helary-Mostefaoui-Netzer-RaynalHelary-Mostefaoui-Netzer-Raynal通信引导协议
   13.10.1 设计原则
   13.10.2 检查点协议
  13.11 本章小结
  13.12 习题
  13.13 参考文献说明
  参考文献
 第十四章 共识和协定算法
  14.1 问题定义
   14.1.1 拜占庭协定及相关问题
   14.1.2 问题的等价性及标示
  14.2 结果概观
  14.3 无故障系统(同步或者异步)中的协定问题
  14.4 有故障的同步系统(消息传输机制)中的协定问题
   14.4.1 针对崩溃故障(同步系统)的共识算法
   14.4.2 针对拜占庭错误的共识算法(同步系统)
  14.5 有故障的异步消息传输系统中的协定问题
   14.5.1 得到一致解的不可能性
   14.5.2 结束可靠的广播结束可靠的广播
   14.5.3 分布式事务提交事务提交
   14.5.4 kset共识k-set共识问题
   14.5.5 近似共识近似共识
   14.5.6 重命名问题重命名问题
   14.5.7 可靠广播可靠广播
  14.6 异步系统异步系统中无等待共享内存的共识问题
   14.6.1 不可能有解
   14.6.2 共识数以及共识层级共识层级
   14.6.3 共识对象的通用性共识对象的通用性
   14.6.4 共享内存中的kset共识共享内存中的k-set共识
   14.6.5 共享内存的重命名问题
   14.6.6 使用分裂器分裂器解决共享内存重命名问题
  14.7 本章小结
  14.8 习题
  14.9 参考文献说明
  参考文献
 第十五章 失效检测
  15.1 引言
  15.2 非可靠失效检测程序
   15.2.1 系统模型
   15.2.2 失效检测程序失效检测
   15.2.3 完备性完备性的准确性准确性
   15.2.4 失效检测程序类型
   15.2.5 失效检测程序的可简约性
   15.2.6 简约弱失效检测程序W成强失效检测程序S
   15.2.7 简约最终弱失效检测程序◇W成最终强失效检测程序◇S
  15.3 共识问题共识问题
   15.3.1 解共识问题
   15.3.2 使用强失效检测程序S的解决方案
   15.3.3 使用最终强失效检测程序◇S的解决方案
  15.4 原子广播原子广播
  15.5 原子广播的解决方案
  15.6 解决基本一致问题的最弱失效检测程序
   15.6.1 实际的失效检测程序
   15.6.2 对一致的最弱失效检测程序
   15.6.3 终止可靠广播的最弱失效检测程序
  15.7 失效检测程序的实现
  15.8 自适应失效检测程序协议
   15.8.1 懒惰失效检测协议懒惰失效检测协议
  15.9 习题
  15.10 参考文献说明
  参考文献
 第十六章 分布式系统中的验证
  16.1 简介
  16.2 背景和定义
   16.2.1 认证的基础
   16.2.2 主体的类型
   16.2.3 认证协议的简单分类
   16.2.4 标记法
   16.2.5 密码协议的设计原则
  16.3 基于对称密码系统的协议
   16.3.1 基本协议
   16.3.2 使用noncenonce的修正协议
   16.3.3 Widemouth frog协议Widemouth frog协议
   16.3.4 基于认证服务器的协议
   16.3.5 一次性口令一次性口令方案
   16.3.6 OtwayRees协议OtwayRees协议
   16.3.7 Kerberos认证服务Kerberos认证服务
  16.4 基于非对称密码系统的协议
   16.4.1 基本协议
   16.4.2 使用认证授权的修改协议
   16.4.3 Needham-Schroeder协议Needham-Schroeder协议
   16.4.4 SSL协议SSL协议
  16.5 基于口令认证
   16.5.1 加密密钥交换协议加密密钥交换协议
   16.5.2 安全远程口令协议安全远程口令协议
  16.6 认证协议失效
  16.7 本章小结
  16.8 习题
  16.9 参考文献说明
  参考文献
 第十七章 自稳定
  17.1 介绍
  17.2 系统模型
  17.3 自稳定自稳定性定义
   17.3.1 随机自稳定性及概率自稳定性概率自稳定性
  17.4 自稳定性算法设计中的问题
   17.4.1 个体单元中的状态数
   17.4.2 一致与非一致网络
   17.4.3 中央和分布式守护程序
   17.4.4 减少令牌环中的状态数
   17.4.5 共享内存模型
   17.4.6 互斥
   17.4.7 自稳定的开销
  17.5 设计自稳定系统的方法
   17.5.1 分层分层和模块化模块化
  17.6 通信协议
  17.7 自稳定分布式生成树自稳定分布式生成树
  17.8 构建生成树的自稳定算法
   17.8.1 DolevDolev、Israelilsraeli和MoranMoran算法
   17.8.2 构建生成树的AfekAfek、KuttenKutten和YangYang算法
   17.8.3 构建生成树的AroraArora和GoudaGouda算法
   17.8.4 构建生成树的HuangHuang等人算法
   17.8.5 构建生成树的AfekAfek和BremlerBremler算法
  17.9 1-最大独立集合的匿名自稳定算法1-最大独立集合的匿名自稳定算法
  17.10 概率自稳定头标选择算法
  17.11 编译在自稳定中的作用
   17.11.1 顺序程序的编译程序
   17.11.2 异步消息传递系统的编译程序
   17.11.3 异步共享内存系统编译程序
  17.12 自稳定作为容错的一个解法
  17.13 阻碍自稳定的因素
  17.14 自稳定的局限
  17.15 本章小结
  17.16 习题
  17.17 参考文献说明
  参考文献
 第十八章 对等计算及覆盖网络
  18.1 概述
   18.1.1 NapsterNapster
   18.1.2 应用层覆盖网络
  18.2 数据索引数据索引和覆盖网络覆盖网络
   18.2.1 分布式索引
  18.3 非结构化覆盖网络
   18.3.1 非结构化覆盖网络：属性
   18.3.2 Gnutella
   18.3.3 GnutellaGnutella以及非结构化覆盖网络中的查找
   18.3.4 复制策略
   18.3.5 复制策略实现
  18.4 ChordChord分布式哈希表
   18.4.1 概述
   18.4.2 简单查找
   18.4.3 可扩展的查找
   18.4.4 管理网络扰动网络扰动
   18.4.5 复杂度
  18.5 内容寻址网络内容寻址网络
   18.5.1 概述
   18.5.2 CAN初始化
   18.5.3 CAN路由
   18.5.4 CAN维护
   18.5.5 CAN优化
   18.5.6 CAN复杂度
  18.6 TapestryTapestry
   18.6.1 概述
   18.6.2 覆盖网络和路由
   18.6.3 对象发布和对象查找
   18.6.4 节点插入
   18.6.5 节点删除
  18.7 P2P系统设计中的其他挑战
   18.7.1 公平：一个博弈游戏
   18.7.2 信任或者声誉管理声誉管理
  18.8 在存储空间及路由长度间折中
   18.8.1 统一DHT协议
   18.8.2 有关DHT存储和路由距离的约束
  18.9 复杂网络的图结构
  18.10 Internet图
   18.10.1 基本定理和其定义
   18.10.2 Internet的特性
   18.10.3 复杂网络的错误和攻击容忍
  18.11 通用随机图网络通用随机图网络
  18.12 小世界网络小世界网络
  18.13 规模无关网络
   18.13.1 主方程法
   18.13.2 速率方程法
  18.14 演化网络演化网络
   18.14.1 扩展的Barabasi-Albert模型
  18.15 本章小结
  18.16 习题
  18.17 参考文献说明
  参考文献
 索引