[
-
内容大纲
本书对分布式算法进行全面介绍，包含同步模型、异步模型和部分同步模型，针对这些模型讨论互斥性、一致性和通信问题，为设计、实现和分析分布式算法提供了蓝图，适合学生、程序员、系统分析人员和研究人员等不同类型的读者阅读。书中涉及该领域重要的算法和不可能解，而且采用简单的自动机理论进行论述，其中涉及的问题包括资源分配、通信、分布式处理器之间的一致性、数据一致性、死锁检测、领导者进程的选取、全局快照等。 -
作者介绍
南希·A.林奇（Nancy A.Lynch） 麻省理工学院电子工程和计算机科学系教授，领导麻省理工学院的分布式系统理论研究组，在分布式算法和不可能解以及分布式系统的形式化建模和证明方面编写了大量著作。 -
目录
译者序
前言
第1章 引言
1.1 相关主题
1.2 我们的观点
1.3 本书内容综述
1.4 参考文献注释
1.5 标记
第一部分 同步网络算法
第2章 建模I：同步网络模型
2.1 同步网络系统
2.2 故障
2.3 输入和输出
2.4 运行
2.5 证明方法
2.6 复杂度度量
2.7 随机化
2.8 参考文献注释
第3章 同步环中的领导者选择
3.1 问题
3.2 相同进程的不可能性结果
3.3 基本算法
3.4 通信复杂度为O (nlogn）的算法
3.5 非基于比较的算法
3.5.1 时间片算法
3.5.2 变速算法
3.6 基于比较的算法的下界
3.7 非基于比较的算法的下界*
3.8 参考文献注释
3.9 习题
第4章 一般同步网络中的算法
4.1 一般网络中的领导者选举
4.1.1 问题
4.1.2 简单的洪泛算法
4.1.3 降低通信复杂度
4.2 广度优先搜索
4.2.1 问题
4.2.2 基本的广度优先搜索算法
4.2.3 应用
4.3 最短路径
4.4 最小生成树
4.4.1 问题
4.4.2 基本定理
4.4.3 算法
4.5 独立集
4.5.1 问题
4.5.2 随机化算法
4.5.3 分析*
4.6 参考文献注释
4.7 习题
第5章 链路故障时的分布式一致性
5.1 协同攻击问题—确定性版本
5.2 协同攻击问题—随机化版本
5.2.1 形式化模型
5.2.2 算法
5.2.3 不一致的下限
5.3 参考文献注释
5.4 习题
第6章 进程故障下的分布式一致性
6.1 问题
6.2 针对停止故障的算法
6.2.1 基本算法
6.2.2 减少通信
6.2.3 指数信息收集算法
6.2.4 带鉴别的Byzantine一致性
6.3 针对Byzantine故障的算法
6.3.1 举例
6.3.2 Byzantine一致性问题的EIG算法
6.3.3 使用二元Byzantine一致性的一般Byzantine一致性问题
6.3.4 减少通信开销
6.4 Byzantine一致性问题中进程的个数
6.5 一般图中的Byzantine一致性问题
6.6 弱Byzantine一致性
6.7 有停止故障时的轮数
6.8 参考文献注释
6.9 习题
第7章 更多的一致性问题
7.1 k一致性问题
7.1.1 问题
7.1.2 算法
7.1.3 下界*
7.2 近似一致性
7.3 提交问题
7.3.1 问题
7.3.2 两阶段提交
7.3.3 三阶段提交
7.3.4 消息数的下界
7.4 参考文献注释
7.5 习题
第二部分 异步算法
第8章 建模II：异步系统模型
8.1 输入/输出自动机
8.2 自动机的操作
8.2.1 合成
8.2.2 隐藏
8.3 公平性
8.4 问题的输入和输出
8.5 属性与证明方法
8.5.1 不变式断言
8.5.2 轨迹属性
8.5.3 安全与活性属性
8.5.4 合成推理
8.5.5 层次化证明
8.6 复杂度衡量
8.7 不可区分的运行
8.8 随机化
8.9 参考文献注释
8.10 习题
第二部分A 异步共享存储器算法
第9章 建模III：异步共享存储器模型
9.1 共享存储器系统
9.2 环境模型
9.3 不可区分状态
9.4 共享变量类型
9.5 复杂度衡量
9.6 故障
9.7 随机化
9.8 参考文献注释
9.9 习题
第10章 互斥
10.1 异步共享存储器模型
10.2 问题
10.3 Dijkstra的互斥算法
10.3.1 算法
10.3.2 正确性证明
10.3.3 互斥条件的一个断言式证明
10.3.4 运行时间
10.4 互斥算法的更强条件
10.5 锁定权互斥算法
10.5.1 双进程算法
10.5.2 n进程算法
10.5.3 锦标赛算法
10.6 使用单写者共享寄存器的算法
10.7 Bakery算法
10.8 寄存器数量的下界
10.8.1 基本事实
10.8.2 单写者共享变量
10.8.3 多写者共享变量
10.9 使用读–改–写共享变量的互斥
10.9.1 基本问题
10.9.2 有界绕过次数
10.9.3 锁定权
10.9.4 模拟证明
10.10 参考文献注释
10.11 习题
第11章 资源分配
11.1 ?问题
11.1.1 显式资源规格说明和互斥规格说明
11.1.2 资源分配问题
11.1.3 哲学家用餐问题
11.1.4 解法的受限形式
11.2 对称哲学家用餐算法的不存在性
11.3 右–左哲学家用餐算法
11.3.1 等待链
11.3.2 基本算法
11.3.3 扩展
11.4 随机哲学家用餐算法*
11.4.1 算法*
11.4.2 正确性*
11.5 参考文献注释
11.6 习题
第12章 一致性
12.1 问题
12.2 使用读/写共享存储器的一致性问题
12.2.1 限制
12.2.2 术语
12.2.3 双价初始化
12.2.4 无等待终止性的不可能性
12.2.5 单故障终止性的不可能性结果
12.3 读/改/写共享存储器上的一致性问题
12.4 其他共享存储器类型
12.5 异步共享存储器系统中的可计算性*
12.6 参考文献注释
12.7 习题
第13章 原子对象
13.1 定义和基本结论
13.1.1 原子对象的定义
13.1.2 规范无等待原子对象自动机
13.1.3 原子对象的合成
13.1.4 原子对象和共享变量
13.1.5 显示原子性的一个充分条件
13.2 用读/写变量实现读–改–写原子对象
13.3 共享存储器的原子快照
13.3.1 问题
13.3.2 带无界变量的一个算法
13.3.3 带有界变量的一个算法*
13.4 读/写原子对象
13.4.1 问题
13.4.2 证明原子性的其他引理
13.4.3 带无界变量的一个算法
13.4.4 两个写者的有界算法
13.4.5 使用快照的算法
13.5 参考文献注释
13.6 习题
第二部分B 异步网络算法
第14章 建模IV：异步网络模型
14.1 发送/接收系统
14.1.1 进程
14.1.2 发送/接收通道
14.1.3 异步发送/接收系统
14.1.4 使用可靠FIFO通道的发送接收系统的属性
14.1.5 复杂度度量
14.2 广播系统
14.2.1 进程
14.2.2 广播通道
14.2.3 异步广播系统
14.2.4 采用可靠广播通道的广播系统的属性
14.2.5 复杂度度量
14.3 多播系统
14.3.1 进程
14.3.2 多播通道
14.3.3 异步多播系统
14.4 参考文献注释
14.5 习题
第15章 基本异步网络算法
15.1 环中的领导者选举
15.1.1 LCR算法
15.1.2 HS算法
15.1.3 PetersonLeader算法
15.1.4 通信复杂度的下界
15.2 任意网络中的领导者选举
15.3 生成树的构造、广播和敛播
15.4 广度优先搜索和最短路径
15.5 最小生成树
15.5.1 问题描述
15.5.2 同步算法：回顾
15.5.3 GHS算法：概要
15.5.4 更详细的算法
15.5.5 特殊消息
15.5.6 复杂度分析
15.5.7 GHS算法的正确性证明
15.5.8 简单“同步”策略
15.5.9 应用到领导者选举算法中
15.6 参考文献注释
15.7 习题
第16章 同步器
16.1 问题
16.2 局部同步器
16.3 安全同步器
16.3.1 前端自动机
16.3.2 通道自动机
16.3.3 安全同步器的任务
16.3.4 正确性
16.4 安全同步器的实现
16.4.1 同步器Alpha
16.4.2 同步器Beta
16.4.3 同步器Gamma
16.5 应用
16.5.1 领导者选举
16.5.2 广度优先搜索
16.5.3 最短路径
16.5.4 广播与确认
16.5.5 独立集
16.6 时间下界
16.7 参考文献注释
16.8 习题
第17章 共享存储器与网络
17.1 从异步共享存储器模型到异步网络模型的转换
17.1.1 问题
17.1.2 无故障时的策略
17.1.3 容忍进程故障的算法
17.1.4 对于n/2故障的不可能性结果
17.2 从异步网络模型到异步共享存储器模型的转换
17.2.1 发送/接收系统
17.2.2 广播系统
17.2.3 异步网络中一致性的不可能性
17.3 参考文献注释
17.4 习题
第18章 逻辑时间
18.1 异步网络的逻辑时间
18.1.1 发送/接收系统
18.1.2 广播系统
18.2 使用逻辑时间的异步算法
18.2.1 时钟的走动
18.2.2 延迟未来事件
18.3 应用
18.3.1 银行系统
18.3.2 全局快照
18.3.3 模拟一台单状态机
18.4 从实际时间算法到逻辑时间算法的变换*
18.5 参考文献注释
18.6 习题
第19章 一致全局快照和稳定属性检测
19.1 发散算法的终止检测
19.1.1 问题
19.1.2 DijkstraScholten算法
19.2 一致全局快照
19.2.1 问题
19.2.2 ChandyLamport算法
19.2.3 应用
19.3 参考文献注释
19.4 习题
第20章 网络资源分配
20.1 互斥
20.1.1 问题
20.1.2 模拟共享存储器
20.1.3 循环令牌算法
20.1.4 基于逻辑时间的算法
20.1.5 LogicalTimeME算法的改进
20.2 通用资源分配
20.2.1 问题
20.2.2 着色算法
20.2.3 基于逻辑时间的算法
20.2.4 无环有向图算法
20.2.5 哲学家饮水*
20.3 参考文献注释
20.4 习题
第21章 带进程故障的异步网络计算
21.1 网络模型
21.2 有故障环境中一致性的不可能性
21.3 随机算法
21.4 故障检测器
21.5 k一致性
21.6 近似一致性
21.7 异步网络的计算能力*
21.8 参考文献注释
21.9 习题
第22章 数据链路协议
22.1 问题阐述
22.2 Stenning协议
22.3 位变换协议
22.4 可容忍消息重排序的有界tag协议
22.4.1 关于可容忍消息重排序和重复的不可能性结论
22.4.2 可容忍消息丢失和重排序的有界tag协议
22.4.3 不存在可容忍消息丢失和重排序的高效协议
22.5 可容忍进程崩溃
22.5.1 简单的不可能性结论
22.5.2 更复杂的不可能性结论
22.5.3 实用的协议
22.6 参考文献注释
22.7 习题
第三部分 部分同步算法
第23章 建模V：部分同步系统模型
23.1 MMT定时自动机
23.1.1 基本定义
23.1.2 操作
23.2 通用定时自动机
23.2.1 基本定义
23.2.2 将MMT自动机转化为通用定时自动机
23.2.3 动作
23.3 属性和证明方法
23.3.1 不变式断言
23.3.2 定时轨迹属性
23.3.3 模拟关系
23.4 构造共享存储器和网络系统的模型
23.4.1 共享存储器系统
23.4.2 网络
23.5 参考文献注释
23.6 习题
第24章 部分同步的互斥性
24.1 问题
24.2 单寄存器算法
24.3 对定时故障的恢复性
24.4 不可能性结果
24.4.1 时间下界
24.4.2 最终时间界限的不可能性结果*
24.5 参考文献注释
24.6 习题
第25章 部分同步的一致性
25.1 问题
25.2 故障检测器
25.3 基本结论
25.3.1 上界
25.3.2 下界
25.4 有效算法
25.4.1 算法
25.4.2 安全属性
25.4.3 活性和复杂度
25.5 涉及时间不确定性的下界*
25.6 其他结果*
25.6.1 同步进程、异步通道*
25.6.2 异步进程、同步通道*
25.6.3 最终时间界限*
25.7 小结
25.8 参考文献注释
25.9 习题
参考文献
同类热销排行榜
- C语言与程序设计教程(高等学校计算机类十二五规划教材)16
- 电机与拖动基础(教育部高等学校自动化专业教学指导分委员会规划工程应用型自动化专业系列教材)13.48
- 传感器与检测技术(第2版高职高专电子信息类系列教材)13.6
- ASP.NET项目开发实战(高职高专计算机项目任务驱动模式教材)15.2
- Access数据库实用教程(第2版十二五职业教育国家规划教材)14.72
- 信号与系统(第3版下普通高等教育九五国家级重点教材)15.08
- 电气控制与PLC(普通高等教育十二五电气信息类规划教材)17.2
- 数字电子技术基础(第2版)17.36
- VB程序设计及应用(第3版十二五职业教育国家规划教材)14.32
- Java Web从入门到精通(附光盘)/软件开发视频大讲堂27.92
推荐书目
-
孩子你慢慢来/人生三书 华人世界率性犀利的一枝笔，龙应台独家授权《孩子你慢慢来》20周年经典新版。她的《...
-
时间简史(插图版) 相对论、黑洞、弯曲空间……这些词给我们的感觉是艰深、晦涩、难以理解而且与我们的...
-
本质(精) 改革开放40年，恰如一部四部曲的年代大戏。技术突变、产品迭代、产业升级、资本对接...