第1章 导论：分布式系统
1. 1 分布式系统的定义
1. 1. 1 动机
1. 2 计算机网络
1. 1. 3 广域网络
1. 1. 4 局域网
1. 1. 5 多处理器计算机
1. 1. 6 协同操作进程
1. 2 体系结构和语言
1. 2. 1 结构
1. 2. 2 0SI参考模型
1. 2. 3 局域网络OSI模型：IEEE标准
1. 2. 4 语言支持
1. 3 分布式算法
1. 3. 1 分布式算法与集中式算法
1. 3. 2 一个例子：单消息通信
1. 3. 3 研究领域
1. 4 本书概要
第一部分 协 议
第2章 模型
2. 1 转移系统和算法
2. 1. 1 转移系统
2. 1. 2 异步消息传递系统
2. 1. 3 同步消息传递系统
2. 1. 4 公平性
2. 2 转移系统性质的证明
2. 2. 1 安全性
2. 2. 2 活动性
2. 3 事件的因果序和逻辑时钟
2. 3. 1 事件的独立性和相关性
2. 3. 2 执行的等价性：计算
2. 3. 3 逻辑时钟
2. 4 附加假设, 复杂度
2. 4. 1 网络拓扑结构
2. 4. 2 信道性质
2. 4. 3 实时性假设
2. 4. 4 进程知识
2. 4. 5 分布式算法的复杂度
习题
第3章 通信协议
3. 1 平衡滑动窗口协议
3. 1. 1 协议表示
3. 1. 2 协议的正确性证明
3. 1. 3 协议讨论
3. 2 基于计时器的协议
3. 2. 1 协议表示
3. 2. 2 协议的正确性证明
3. 2. 3 协议讨论
习题
第4章 路由算法
4. 1 基于目的节点的路由
4. 2 所有点对之间的最短路径问题
4. 2. 1 Floyd-Warshall算法
4. 2. 2 Toueg最短路径算法
4. 2. 3 讨论以及更多算法
4. 3 变更算法
4. 3. 1 算法描述
4. 3. 2 变更算法的正确性
4. 3. 3 算法讨论
4. 4 带有压缩路由表的路由
4. 4. 1 树标号模式
4. 4. 2 区间路由
4. 4. 3 前缀路由
4. 5 分级路由
习题
第5章 无死锁的包交换
5. 1 引言
5. 2 有结构的方法
5. 2. 1 缓冲图
5. 2. 2 图G的定向
5. 3 无结构的方法
5. 3. 1 前向计数控制器和后向计数
控制器
5. 3. 2 前向状态控制器和后向状态
控制器
5. 4 需进一步研究的问题
5. 4. 1 拓扑变化
5. 4. 2 其他类型的死锁
5. 4. 3 活锁
习题
第二部分 基本算法
第6章 波动算法与遍历算法
6. 1 波动算法的定义和使用
6. 1. 1 波动算法定义
6. 1. 2 波动算法的一些基本结果
6. 1. 3 具有反馈的信息传播
6. 1. 4 同步
6. 1. 5 计算下确界函数
6. 2 波动算法集
6. 2. 1 环网算法
6. 2. 2 树算法
6. 2. 3 回波算法
6. 2. 4 轮询算法
6. 2. 5 相位算法
6. 2. 6 Finn算法
6. 3 遍历算法
6. 3. 1 遍历团
6. 3. 2 遍历圆环
6. 3. 3 遍历超立方体
6. 3. 4 遍历连通网络
6. 4 深度优先搜索的时间复杂度
6. 4. 1 分布式深度优先搜索
6. 4. 2 线性时间的深度优先搜索算法
6. 4. 3 具有近邻知识的深度优先搜索
6. 5 遗留问题
6. 5. 1 波动算法综述
6. 5. 2 计算和
6. 5. 3 时间复杂度的另一种定义
习题
第7章 选举算法
7. 1 引言
7. 1. 1 本章所做假设
7. 1. 2 选举和波动
7. 2 环网
7. 2. 1 LeLann和Chang-Roberts算法
7. 2. 2 Peterson／Dolev-Klawe-Rodeh算法
7. 2. 3 一个下界
7. 3 任意网
7. 3. 1 废止和快速算法
7. 3. 2 Gallager-Humblet-Spira算法
7. 3. 3 GHS算法的全局描述
7. 3. 4 GHS算法的详细描述
7. 3. 5 GHS算法的讨论和变化
7. 4 Korach-Kutten-Moran算法
7. 4. 1 模块构造
7. 4. 2 KKM算法的应用
习题
第8章 终止检测
8. 1 预备知识
8. 1. 1 定义
8. 1. 2 两个下界
8. 1. 3 终止进程
8. 2 计算树和森林
8. 2. 1 Dijkstra-Scholten算法
8. 2. 2 Shavit-Francez算法
8. 3 基于波动的方法
8. 3. 1 Dijkstra-Feijen-VanGasteren算法
8. 3. 2 基本消息的计数：Safra算法
8. 3. 3 利用确认
8. 3. 4 带波动的终止检测
8. 4 其他方法
8. 4. 1 信用-恢复算法
8. 4. 2 基于时戳的终止检测方法
习题
第9章 匿名网络
9. 1 预备知识
9. 1. 1 定义
9. 1. 2 概率算法的分类
9. 1. 3 本章考虑的问题
9. 1. 4 同步消息传递与异步消息传递
9. 2 确定算法
9. 2. 1 确定性的选举：否定性的结果
9. 2. 2 环上函数计算
9. 3 概率选举算法
9. 4 网络规模计算
9. 4. 1 否定性结果
9. 4. 2 计算环规模的算法
习题
第10章 快照
10. 1 预备知识
10. 2 两个快照算法
10. 2. 1 Chandy-Lamport算法
10. 2. 2 Lai-Yang算法
10. 3 使用快照算法
10. 3. 1 计算信道状态
10. 3. 2 快照的适时性
10. 3. 3 稳定性检测
10. 4 应用：死锁检测
10. 4. 1 基本计算模型和问题阐述
10. 4. 2 全局-标记算法
10. 4. 3 受限模型的死锁检测
习题
第11章 方向侦听与定向
11. 1 引言和定义
11. 1. 1 方向侦听的定义和特性
11. 1. 2 利用方向侦听
11. 1. 3 具有方向侦听的广播
11. 2 环和弦环的选举算法
11. 2. 1 Franklin算法
11. 2. 2 Attiya改进
11. 2. 3 最小化弦数
11. 2. 4 1-弦线性算法
11. 3 超立方体上的计算
11. 3. 1 基线：没有拓扑知识
11. 3. 2 进行比赛的算法
11. 3. 3 多路径流量算法
11. 3. 4 使用掩码的有效超立方体算法
11. 3. 5 无标号超立方体上的选举算法
11. 4 与复杂度有关的问题
11. 4. 1 团或任意图的定向
11. 4. 2 位复杂度和多路径流量算法
11. 4. 3 Verweij随机漫步算法
11. 5 结论和未解决的问题
11. 5. 1 利用方向侦听
11. 5. 2 复杂度归约
11. 5. 3 当前研究
习题
第12章 网络中的同步
12. 1 预备知识
12. 1. 1 同步网络
12. 1. 2 通过同步提高效率
12. 1. 3 异步有限延迟网络
12. 2 同步网络中的选举
12. 2. 1 网络规模已知
12. 2. 2 网络规模未知
12. 2. 3 补充结果
12. 3 同步器算法
12. 3. 1 简单同步器
12. 3. 2 a. B和r同步器
12. 4 应用：广度优先搜索
12. 4. 1 同步BFS算法
12. 4. 2 与同步器组合
12. 4. 3 异步BFS算法
12. 5 Archimedean假设
习题
第三部分 容 错
第13章 分布式系统中的容错
13. 1 利用容错算法的原因
13. 2 健壮算法
13. 2. 1 故障模型
13. 2. 2 判定问题
13. 2. 3 第14章到第16章综述
13. 2. 4 本书中没有涉及的主题
13. 3 稳定算法
第14章 异步系统中的容错
14. 1 一致性的不可能性
14. 1. 1 表示. 定义及基本结果
14. 1. 2 不可能性证明
14. 1. 3 讨论
14. 2 初始死进程
14. 3 确定可实现实例
14. 3. 1 可解问题：重命名
14. 3. 2 扩展的不可能性结果
14. 4 概率一致性算法
14. 4. 1 损毁-健壮一致协议
14. 4. 2 Byzantine-健壮一致性协议
14. 5 弱终止性
习题
第15章 同步系统中的容错
15. 1 同步判定协议
15. 1. 1 弹性界限
15. 1. 2 Byzantine广播算法
15. 1. 3 多项式级的广播算法
15. 2 鉴别协议
15. 2. 1 高度弹性的协议
15. 2. 2 数字签名的实现
15. 2. 3 ElGamal签名模式
15. 2. 4 RSA签名模式
15. 2. 5 Fiat-Shamir签名模式
15. 2. 6 概述和讨论
15. 3 时钟同步
15. 3. 1 读取远程时钟
15. 3. 2 分布式时钟同步
15. 3. 3 轮模型的实现
习题
第16章 故障检测
16. 1 模型和定义
16. 1. 1 四种基本检测器类型
16. 1. 2 故障检测器的用途和缺陷
16. 2 用弱精确检测器解一致性问题
16. 3 最终弱精确检测器
16. 3. 1 弹性上界
16. 3. 2 一致算法
16. 4 故障检测器的实现
16. 4. 1 同步系统：完美检测
16. 4. 2 部分同步系统：最终完美检测
16. 4. 3 小结
习题
第17章 稳定性
17. 1 引言
17. 1. 1 定义
17. 1. 2 稳定系统中的通信
17. 1. 3 例子：Dijjstra令牌环
17. 2 图论算法
17. 2. 1 环定向
17. 2. 2 最大匹配
17. 2. 3 选举和生成树构造
17. 3 稳定方法学
17. 3. 1 协议组合
17. 3. 2 计算最小路径
17. 3. 3 结论和讨论
习题
第四部分 附 录
附录A 伪代码使用约定
附录B 图和网络
参考文献
主题词索引
鄂公网安备 42010302001612号 