更新时间：2023-11-02 20:47:13
封面
版权信息
译者序
前言
第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 属性与证明方法
