封面
版权信息
译者序
前言
第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 广度优先搜索
- APP免费
4.2.1 问题
- APP免费
4.2.2 基本的广度优先搜索算法
- APP免费
4.2.3 应用
- APP免费
4.3 最短路径
- APP免费
4.4 最小生成树
- APP免费
4.4.1 问题
- APP免费
4.4.2 基本定理
- APP免费
4.4.3 算法
- APP免费
4.5 最大独立集
- APP免费
4.5.1 问题
- APP免费
4.5.2 随机化算法
- APP免费
4.5.3 分析＊
- APP免费
4.6 参考文献注释
- APP免费
4.7 习题
- APP免费
第5章 链路故障时的分布式一致性
- APP免费
5.1 协同攻击问题——确定性版本
- APP免费
5.2 协同攻击问题——随机化版本
- APP免费
5.2.1 形式化模型
- APP免费
5.2.2 算法
- APP免费
5.2.3 不一致的下限
- APP免费
5.3 参考文献注释
- APP免费
5.4 习题
- APP免费
第6章 进程故障下的分布式一致性
- APP免费
6.1 问题
- APP免费
6.2 针对停止故障的算法
- APP免费
6.2.1 基本算法
- APP免费
6.2.2 减少通信
- APP免费
6.2.3 指数信息收集算法
- APP免费
6.2.4 带鉴别的Byzantine一致性
- APP免费
6.3 针对Byzantine故障的算法
- APP免费
6.3.1 举例
- APP免费
6.3.2 Byzantine一致性问题的EIG算法
- APP免费
6.3.3 使用二元Byzantine一致性的一般Byzantine一致性问题
- APP免费
6.3.4 减少通信开销
- APP免费
6.4 Byzantine一致性问题中进程的个数
- APP免费
6.5 一般图中的Byzantine一致性问题
- APP免费
6.6 弱Byzantine一致性
- APP免费
6.7 有停止故障时的轮数
- APP免费
6.8 参考文献注释
- APP免费
6.9 习题
- APP免费
第7章 更多的一致性问题
- APP免费
7.1 k一致性问题
- APP免费
7.1.1 问题
- APP免费
7.1.2 算法
- APP免费
7.1.3 下界＊
- APP免费
7.2 近似一致性
- APP免费
7.3 提交问题
- APP免费
7.3.1 问题
- APP免费
7.3.2 两阶段提交
- APP免费
7.3.3 三阶段提交
- APP免费
7.3.4 消息数的下界
- APP免费
7.4 参考文献注释
- APP免费
7.5 习题
- APP免费
第二部分 异步算法
- APP免费
第8章 建模II：异步系统模型
- APP免费
8.1 输入/输出自动机
- APP免费
8.2 自动机的操作
- APP免费
8.2.1 合成
- APP免费
8.2.2 隐藏
- APP免费
8.3 公平性
- APP免费
8.4 问题的输入和输出
- APP免费
8.5 属性与证明方法
- APP免费
8.5.1 不变式断言
- APP免费
8.5.2 轨迹属性
- APP免费
8.5.3 安全与活性属性
- APP免费
8.5.4 合成推理
- APP免费
8.5.5 层次化证明
- APP免费
8.6 复杂度衡量
- APP免费
8.7 不可区分的运行
- APP免费
8.8 随机化
- APP免费
8.9 参考文献注释
- APP免费
8.10 习题
- APP免费
第二部分A 异步共享存储器算法
- APP免费
第9章 建模III：异步共享存储器模型
- APP免费
9.1 共享存储器系统
- APP免费
9.2 环境模型
- APP免费
9.3 不可区分状态
- APP免费
9.4 共享变量类型
- APP免费
9.5 复杂度衡量
- APP免费
9.6 故障
- APP免费
9.7 随机化
- APP免费
9.8 参考文献注释
- APP免费
9.9 习题
- APP免费
第10章 互斥
- APP免费
10.1 异步共享存储器模型
- APP免费
10.2 问题
- APP免费
10.3 Dijkstra的互斥算法
- APP免费
10.3.1 算法
- APP免费
10.3.2 正确性证明
- APP免费
10.3.3 互斥条件的一个断言式证明
- APP免费
10.3.4 运行时间
- APP免费
10.4 互斥算法的更强条件
- APP免费
10.5 锁定权互斥算法
- APP免费
10.5.1 双进程算法
- APP免费
10.5.2 n进程算法
- APP免费
10.6 使用单写者共享寄存器的算法
- APP免费
10.7 Bakery算法
- APP免费
10.8 寄存器数量的下界
- APP免费
10.8.1 基本事实
- APP免费
10.8.2 单写者共享变量
- APP免费
10.8.3 多写者共享变量
- APP免费
10.9 使用读-改-写共享变量的互斥
- APP免费
10.9.1 基本问题
- APP免费
10.9.2 有界绕过次数
- APP免费
10.9.3 锁定权
- APP免费
10.9.4 模拟证明
- APP免费
10.10 参考文献注释
- APP免费
10.11 习题
- APP免费
第11章 资源分配
- APP免费
11.1 问题
- APP免费
11.1.1 显式资源规格说明和互斥规格说明
- APP免费
11.1.2 资源分配问题
- APP免费
11.1.3 哲学家用餐问题
- APP免费
11.1.4 解法的受限形式
- APP免费
11.2 对称哲学家用餐算法的不存在性
- APP免费
11.3 右-左哲学家用餐算法
- APP免费
11.3.1 等待链
- APP免费
11.3.2 基本算法
- APP免费
11.3.3 扩展
- APP免费
11.4 随机哲学家用餐算法＊
- APP免费
11.4.1 算法＊
- APP免费
11.4.2 正确性＊
- APP免费
11.5 参考文献注释
- APP免费
11.6 习题
- APP免费
第12章 一致性
- APP免费
12.1 问题
- APP免费
12.2 使用读/写共享存储器的一致性问题
- APP免费
12.2.1 限制
- APP免费
12.2.2 术语
- APP免费
12.2.3 双价初始化
- APP免费
12.2.4 无等待终止性的不可能性
- APP免费
12.2.5 单故障终止性的不可能性结果
- APP免费
12.3 读/改/写共享存储器上的一致性问题
- APP免费
12.4 其他共享存储器类型
- APP免费
12.5 异步共享存储器系统中的可计算性＊
- APP免费
12.6 参考文献注释
- APP免费
12.7 习题
- APP免费
第13章 原子对象
- APP免费
13.1 定义和基本结论
- APP免费
13.1.1 原子对象的定义
- APP免费
13.1.2 规范无等待原子对象自动机
- APP免费
13.1.3 原子对象的合成
- APP免费
13.1.4 原子对象和共享变量
- APP免费
13.1.5 显示原子性的一个充分条件
- APP免费
13.2 用读/写变量实现读-改-写原子对象
- APP免费
13.3 共享存储器的原子快照
- APP免费
13.3.1 问题
- APP免费
13.3.2 带无界变量的一个算法
- APP免费
13.3.3 带有界变量的一个算法＊
- APP免费
13.4 读/写原子对象
- APP免费
13.4.1 问题
- APP免费
13.4.2 证明原子性的其他引理
- APP免费
13.4.3 带无界变量的一个算法
- APP免费
13.4.4 两个写者的有界算法
- APP免费
13.4.5 使用快照的算法
- APP免费
13.5 参考文献注释
- APP免费
13.6 习题
- APP免费
第二部分B 异步网络算法
- APP免费
第14章 建模IV：异步网络模型
- APP免费
14.1 发送/接收系统
- APP免费
14.1.1 进程
- APP免费
14.1.2 发送/接收通道
- APP免费
14.1.3 异步发送/接收系统
- APP免费
14.1.4 使用可靠FIFO通道的发送/接收系统的属性
- APP免费
14.1.5 复杂度度量
- APP免费
14.2 广播系统
- APP免费
14.2.1 进程
- APP免费
14.2.2 广播通道
- APP免费
14.2.3 异步广播系统
- APP免费
14.2.4 采用可靠广播通道的广播系统的属性
- APP免费
14.2.5 复杂度度量
- APP免费
14.3 多播系统
- APP免费
14.3.1 进程
- APP免费
14.3.2 多播通道
- APP免费
14.3.3 异步多播系统
- APP免费
14.4 参考文献注释
- APP免费
14.5 习题
- APP免费
第15章 基本异步网络算法
- APP免费
15.1 环中的领导者选举
- APP免费
15.1.1 LCR算法
- APP免费
15.1.2 HS算法
- APP免费
15.1.3 PetersonLeader算法
- APP免费
15.1.4 通信复杂度的下界
- APP免费
15.2 任意网络中的领导者选举
- APP免费
15.3 生成树的构造、广播和敛播
- APP免费
15.4 广度优先搜索和最短路径
- APP免费
15.5 最小生成树
- APP免费
15.5.1 问题描述
- APP免费
15.5.2 同步算法：回顾
- APP免费
15.5.3 GHS算法：概要
- APP免费
15.5.4 更详细的算法
- APP免费
15.5.5 特殊消息
- APP免费
15.5.6 复杂度分析
- APP免费
15.5.7 GHS算法的正确性证明
- APP免费
15.5.8 简单“同步”策略
- APP免费
15.5.9 应用到领导者选举算法中
- APP免费
15.6 参考文献注释
- APP免费
15.7 习题
- APP免费
第16章 同步器
- APP免费
16.1 问题
- APP免费
16.2 局部同步器
- APP免费
16.3 安全同步器
- APP免费
16.3.1 前端自动机
- APP免费
16.3.2 通道自动机
- APP免费
16.3.3 安全同步器的任务
- APP免费
16.3.4 正确性
- APP免费
16.4 安全同步器的实现
- APP免费
16.4.1 同步器Alpha
- APP免费
16.4.2 同步器Beta
- APP免费
16.4.3 同步器Gamma
- APP免费
16.5 应用
- APP免费
16.5.1 领导者选举
- APP免费
16.5.2 广度优先搜索
- APP免费
16.5.3 最短路径
- APP免费
16.5.4 广播与确认
- APP免费
16.5.5 最大独立集
- APP免费
16.6 时间下界
- APP免费
16.7 参考文献注释
- APP免费
16.8 习题
- APP免费
第17章 共享存储器与网络
- APP免费
17.1 从异步共享存储器模型到异步网络模型的转换
- APP免费
17.1.1 问题
- APP免费
17.1.2 无故障时的策略
- APP免费
17.1.3 容忍进程故障的算法
- APP免费
17.1.4 对于n/2故障的不可能性结果
- APP免费
17.2 从异步网络模型到异步共享存储器模型的转换
- APP免费
17.2.1 发送/接收系统
- APP免费
17.2.2 广播系统
- APP免费
17.2.3 异步网络中一致性的不可能性
- APP免费
17.3 参考文献注释
- APP免费
17.4 习题
- APP免费
第18章 逻辑时间
- APP免费
18.1 异步网络的逻辑时间
- APP免费
18.1.1 发送/接收系统
- APP免费
18.1.2 广播系统
- APP免费
18.2 使用逻辑时间的异步算法
- APP免费
18.2.1 时钟的走动
- APP免费
18.2.2 延迟未来事件
- APP免费
18.3 应用
- APP免费
18.3.1 银行系统
- APP免费
18.3.2 全局快照
- APP免费
18.3.3 模拟一台单状态机
- APP免费
18.4 从实际时间算法到逻辑时间算法的变换＊
- APP免费
18.5 参考文献注释
- APP免费
18.6 习题
- APP免费
第19章 一致全局快照和稳定属性检测
- APP免费
19.1 发散算法的终止检测
- APP免费
19.1.1 问题
- APP免费
19.1.2 DijkstraScholten算法
- APP免费
19.2 一致全局快照
- APP免费
19.2.1 问题
- APP免费
19.2.2 ChandyLamport算法
- APP免费
19.2.3 应用
- APP免费
19.3 参考文献注释
- APP免费
19.4 习题
- APP免费
第20章 网络资源分配
- APP免费
20.1 互斥
- APP免费
20.1.1 问题
- APP免费
20.1.2 模拟共享存储器
- APP免费
20.1.3 循环令牌算法
- APP免费
20.1.4 基于逻辑时间的算法
- APP免费
20.1.5 LogicalTimeME算法的改进
- APP免费
20.2 通用资源分配
- APP免费
20.2.1 问题
- APP免费
20.2.2 着色算法
- APP免费
20.2.3 基于逻辑时间的算法
- APP免费
20.2.4 无环有向图算法
- APP免费
20.2.5 哲学家饮水＊
- APP免费
20.3 参考文献注释
- APP免费
20.4 习题
- APP免费
第21章 带进程故障的异步网络计算
- APP免费
21.1 网络模型
- APP免费
21.2 有故障环境中一致性的不可能性
- APP免费
21.3 随机算法
- APP免费
21.4 故障检测器
- APP免费
21.5 k一致性
- APP免费
21.6 近似一致性
- APP免费
21.7 异步网络的计算能力＊
- APP免费
21.8 参考文献注释
- APP免费
21.9 习题
- APP免费
第22章 数据链路协议
- APP免费
22.1 问题阐述
- APP免费
22.2 Stenning协议
- APP免费
22.3 位变换协议
- APP免费
22.4 可容忍消息重排序的有界tag协议
- APP免费
22.4.1 关于可容忍消息重排序和重复的不可能性结论
- APP免费
22.4.2 可容忍消息丢失和重排序的有界tag协议
- APP免费
22.4.3 不存在可容忍消息丢失和重排序的高效协议
- APP免费
22.5 可容忍进程崩溃
- APP免费
22.5.1 简单的不可能性结论
- APP免费
22.5.2 更复杂的不可能性结论
- APP免费
22.5.3 实用的协议
- APP免费
22.6 参考文献注释
- APP免费
22.7 习题
- APP免费
第三部分 部分同步算法
- APP免费
第23章 建模V：部分同步系统模型
- APP免费
23.1 MMT定时自动机
- APP免费
23.1.1 基本定义
- APP免费
23.1.2 操作
- APP免费
23.2 通用定时自动机
- APP免费
23.2.1 基本定义
- APP免费
23.2.2 将MMT自动机转化为通用定时自动机
- APP免费
23.2.3 动作
- APP免费
23.3 属性和证明方法
- APP免费
23.3.1 不变式断言
- APP免费
23.3.2 定时轨迹属性
- APP免费
23.3.3 模拟关系
- APP免费
23.4 构造共享存储器和网络系统的模型
- APP免费
23.4.1 共享存储器系统
- APP免费
23.4.2 网络
- APP免费
23.5 参考文献注释
- APP免费
23.6 习题
- APP免费
第24章 部分同步的互斥性
- APP免费
24.1 问题
- APP免费
24.2 单寄存器算法
- APP免费
24.3 对定时故障的恢复性
- APP免费
24.4 不可能性结果
- APP免费
24.4.1 时间下界
- APP免费
24.4.2 最终时间界限的不可能性结果＊
- APP免费
24.5 参考文献注释
- APP免费
24.6 习题
- APP免费
第25章 部分同步的一致性
- APP免费
25.1 问题
- APP免费
25.2 故障检测器
- APP免费
25.3 基本结论
- APP免费
25.3.1 上界
- APP免费
25.3.2 下界
- APP免费
25.4 有效算法
- APP免费
25.4.1 算法
- APP免费
25.4.2 安全属性
- APP免费
25.4.3 活性和复杂度
- APP免费
25.5 涉及时间不确定性的下界＊
- APP免费
25.6 其他结果＊
- APP免费
25.6.1 同步进程、异步通道＊
- APP免费
25.6.2 异步进程、同步通道＊
- APP免费
25.6.3 最终时间界限＊
- APP免费
25.7 小结
- APP免费
25.8 参考文献注释
- APP免费
25.9 习题
- APP免费
参考文献
- APP免费
封底
更新时间：2023-11-02 20:47:13
完结共379章
倒序