译者序
前言
第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
展开
