分布式系统设计

作者简介
译者序
前言
第1章 概论 
1.1 推动因素 
1.2 基本计算机组成 
1.3 分布式系统的定义 
1.4 我们的模型 
1.5 互连网络 
1.6 应用与标准 
1.7 范围 
1.8 参考资料来源 
参考文献 
习题 
第2章 分布式程序设计语言 
2.1 分布式程序设计支持的需求 
2.2 并行/分布式程序设计语言概述 
2.3 并行性的表示 
2.4 进程通信与同步 
2.5 远程过程调用 
2.6 健壮性 
参考文献 
习题 
第3章 分布式系统设计的形式方法 
3.1 模型的介绍 
3.1.1 状态机模型 
3.1.2 佩特里网 
3.2 因果相关事件 
3.2.1 发生在先关系 
3.2.2 时空视图 
3.2.3 交叉视图 
3.3 全局状态 
3.3.1 时空视图中的全局状态 
3.3.2 全局状态：一个形式定义 
3.3.3 全局状态的"快照" 
3.3.4 一致全局状态的充要条件 
3.4 逻辑时钟 
3.4.1 标量逻辑时钟 
3.4.2 扩展 
3.4.3 有效实现 
3.4.4 物理时钟 
3.5 应用 
3.5.1 一个全序应用：分布式互斥 
3.5.2 一个逻辑向量时钟应用：消息的排序 
3.6 分布式控制算法的分类 
3.7 分布式算法的复杂性 
参考文献 
习题 
第4章 互斥和选举算法 
4.1 互斥 
4.2 非基于权标的解决方案 
4.2.1 Lamport算法的简单扩展 
4.2.2 Ricart和Agrawala的第一个算法 
4.2.3 Maekawa的算法 
4.3 基于权标的解决方案 
4.3.1 Ricart和Agrawala的第二个算法 
4.3.2 一个简单的基于权标环的算法 
4.3.3 一个基于权标环的容错算法 
4.3.4 基于权标的使用其他逻辑结构的互斥 
4.4 选举 
4.4.1 Chang和Roberts的算法 
4.4.2 非基于比较的算法 
4.5 投标 
4.6 自稳定 
参考文献 
习题 
第5章 死锁的预防、避免和检测 
5.1 死锁问题 
5.1.1 死锁发生的条件 
5.1.2 图论模型 
5.1.3 处理死锁的策略 
5.1.4 请求模型 
5.1.5 资源和进程模型 
5.1.6 死锁条件 
5.2 死锁预防 
5.3 一个死锁预防的例子：分布式数据库系统 
5.4 死锁避免 
5.5 一个死锁避免的例子：多机器人的灵活装配单元 
5.6 死锁检测和恢复 
5.6.1 集中式方法 
5.6.2 分布式方法 
5.6.3 等级式方法 
5.7 死锁检测和恢复的例子 
5.7.1 AND模型下的Chandy，Misra和Hass算法 
5.7.2 AND模型下的Mitchell和Merritt算法 
5.7.3 OR模型下的Chandy，Misra和Hass算法 
参考文献 
习题 
第6章 分布式路由算法 
6.1 导论 
6.1.1 拓扑 
6.1.2 交换 
6.1.3 通信类型 
6.1.4 路由 
6.1.5 路由函数 
6.2 一般类型的最短路径路由 
6.2.1 Dijkstra集中式算法 
6.2.2 Ford的分布式算法 
6.2.3 ARPAnet的路由策略 
6.3 特殊类型网络中的单播 
6.3.1 双向环 
6.3.2 网格和圆环 
6.3.3 超立方 
6.4 特殊类型网络中的广播 
6.4.1 环 
6.4.2 2维网格和圆环 
6.4.3 超立方 
6.5 特殊类型网络中的组播 
6.5.1 一般方法 
6.5.2 基于路径的方法 
6.5.3 基于树的方法 
参考文献 
习题 
第7章 自适应、无死锁和容错路由 
7.1 虚信道和虚网络 
7.2 完全自适应和无死锁路由 
7.2.1 虚信道类 
7.2.2 逃逸信道 
7.3 部分自适应和无死锁路由 
7.4 容错单播：一般方法 
7.5 2维网格和圆环中的容错单播 
7.5.1 基于局部信息的路由 
7.5.2 基于有限全局信息的路由 
7.5.3 基于其他故障模型的路由 
7.6 超立方中的容错单播 
7.6.1 基于局部信息的模型 
7.6.2 基于有限全局信息的模型：安全等级 
7.6.3 基于扩展安全等级模型的路由：安全向量 
7.7 容错广播 
7.7.1 一般方法 
7.7.2 使用全局信息的广播 
7.7.3 使用安全等级进行广播 
7.8 容错组播 
7.8.1 一般方法 
7.8.2 基于路径的路由 
7.8.3 使用安全等级在超立方中进行组播 
参考文献 
习题 
第8章 分布式系统的可靠性 
8.1 基本模型 
8.2 容错系统设计的构件模块 
8.2.1 稳定存储器 
8.2.2 故障-停止处理器 
8.2.3 原子操作 
8.3 节点故障的处理 
8.3.1 向后式恢复 
8.3.2 前卷式恢复 
8.4 向后恢复中的问题 
8.4.1 检查点的存储 
8.4.2 检查点方法 
8.5 处理拜占庭式故障 
8.5.1 同步系统中的一致协议 
8.5.2 对一个发送者的一致 
8.5.3 对多个发送者的一致 
8.5.4 不同模型下的一致 
8.5.5 对验证消息的一致 
8.6 处理通信故障 
8.7 处理软件故障 
参考文献 
习题 
第9章 静态负载分配 
9.1 负载分配的分类 
9.2 静态负载分配 
9.2.1 处理器互连 
9.2.2 任务划分 
9.2.3 任务分配 
9.3 不同调度模型概述 
9.4 基于任务优先图的任务调度 
9.5 案例学习：两种最优调度算法 
9.6 基于任务相互关系图的任务调度 
9.7 案例学习：域划分 
9.8 使用其他模型和目标的调度 
9.8.1 网络流量技术：有不同处理器能力的任务相互关系图 
9.8.2 速率单调优先调度和期限驱动调度：带实时限制的定期任务 
9.8.3 通过任务复制实现故障安全调度：树结构的任务优先图 
9.9 未来的研究方向 
参考文献 
习题 
第10章 动态负载分配 
10.1 动态负载分配 
10.1.1 动态负载分配的组成要素 
10.1.2 动态负载分配算法 
10.2 负载平衡设计决策 
10.2.1 静态算法对动态算法 
10.2.2 多样化信息策略 
10.2.3 集中控制算法和分散控制算法 
10.2.4 移植启动策略 
10.2.5 资源复制 
10.2.6 进程分类 
10.2.7 操作系统和独立任务启动策略 
10.2.8 开环控制和闭环控制 
10.2.9 使用硬件和使用软件 
10.3 移植策略：发送者启动和接收者启动 
10.4 负载平衡使用的参数 
10.4.1 系统大小 
10.4.2 系统负载 
10.4.3 系统交通强度 
10.4.4 移植阈值 
10.4.5 任务大小 
10.4.6 管理成本 
10.4.7 响应时间 
10.4.8 负载平衡视界 
10.4.9 资源要求 
10.5 其他相关因素 
10.5.1 编码文件和数据文件 
10.5.2 系统稳定性 
10.5.3 系统体系结构 
10.6 负载平衡算法实例 
10.6.1 直接算法 
10.6.2 最近邻居算法：扩散 
10.6.3 最近邻居算法：梯度 
10.6.4 最近邻居算法：维交换 
10.7 案例学习：超立方体多计算机上的负载平衡 
10.8 未来的研究方向 
参考文献 
习题 
第11章 分布式数据管理 
11.1 基本概念 
11.2 可串行性理论 
11.3 并发控制 
11.3.1 基于锁的并发控制 
11.3.2 基于时戳的并发控制 
11.3.3 乐观的并发控制 
11.4 复制和一致性管理 
11.4.1 主站点方法 
11.4.2 活动复制 
11.4.3 选举协议 
11.4.4 网络划分的乐观方法：版本号向量 
11.4.5 网络分割的悲观方法：动态选举 
11.5 分布式可靠性协议 
参考文献 
习题 
第12章 分布式系统的应用 
12.1 分布式操作系统 
12.1.1 服务器结构 
12.1.2 八种服务类型 
12.1.3 基于微内核的系统 
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 存储器相关性问题 
12.3.2 Stumm和Zhou的分类 
12.3.3 Li和Hudak的分类 
12.4 分布式数据库系统 
12.5 异构型处理 
12.6 分布式系统的未来研究方向 
参考文献 
习题 
附录 DCDL中的通用符号列表 
索引