Introduction to Distributed Algorithms

第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 图和网络

参考文献

主题词索引