分布式算法导论

✍ Scribed by 泰尔

• Publisher: 机械工业出版社
• Tongue: Chinese
• Leaves: 399
• Series: 计算机科学丛书
• Category: Library

✦ Synopsis

书签已装载，
书签制作方法请找 [email protected]
完全免费

分布式算法20多年来一直是倍受关注的主流方向。本书第二版不仅给出了算法的最新进展，还深入探讨了与之相关的理论知识。这本教材适合本科高年级和研究生使用，同时，本书所覆盖的广度和深度也十分适合从事实际工作的工程师和研究人员参考。书中重点讨论了点对点消息传递模型上的算法，也包括计算机通信网络的实现算法。其他重点讨论的内容包括分布式应用的控制算法（如波算法、广播算法、选举算法、终止检测算法、匿名网络的随机算法、快照算法、死锁检测算法、同步系统算法等），还涉及了利用分布式算法实现容错计算。第二版新增的关于方向感和故障检测器的内容都代表了当今最新技术发展水平，为在这些方向上从事研究的人员提供了很好的帮助。

✦ Table of Contents

封面
书名
版权
前言
目录
目录
第1章导论：分布式系统
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 OSI参考模型
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.2Toueg最短路径算法
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.1LeLann和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-Van Gasteren算法
8.3.2基本消息的计数：Safra算法
8.3.3利用确认
8.34带波动的终止检测
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多路径流量算法
1 1.3.4使用掩码的有效超立方体算法
1 1.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 α、β和y同步器
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 E1Gamal签名模式
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部分同步系统：最终完美检测
164.3 小结
习题
第17章稳定性
17.1引言
17.1.1定义
17.1.2稳定系统中的通信
17.1.3例子：Dijkstra令牌环
17.2图论算法
17.2.1环定向
17.2.2最大匹配
17.2.3选举和生成树构造
17.3稳定方法学
17.3.1协议组合
17.3.2计算最小路径
17.3.3结论和讨论
习题
第四部分附 录
附录A伪代码使用约定
附录B图和网络
参考文献
主题词索引