本书全面且深入地介绍分布式计算系统的理论基础、关键技术和实践应用。内容共分为两部分。第一部分为基础知识，详细阐述分布式计算系统的基本概念、基本模型和典型系统，介绍分布式计算使能技术，包括通信技术、远程过程调用和资源抽象等，为构建高效分布式计算系统提供技术支持；第二部分聚焦于分布式计算算法，包括时钟同步及快照算法、共识算法、图算法等，为读者揭示分布式计算系统中的核心算法原理。本书内容丰富、结构清晰，通过阅读本书，读者将能够全面掌握分布式计算系统的核心知识和技能，为未来的学 习和工作奠定坚实的基础。
样章试读
目录
- 目录
第一部分 分布式计算系统基础
第1章 绪论 2
1.1 分布式计算系统的基本概念 2
1.1.1 基本定义 2
1.1.2 基本特征 3
1.1.3 分布式计算与其他计算范式 16
1.2 分布式计算系统的基本模型 20
1.2.1 分布式程序的形式化定义 20
1.2.2 分布式程序执行过程中事件的顺序 20
1.2.3 分布式计算系统的全局状态 22
1.2.4 分布式计算的运行分割 23
1.3 典型的分布式计算系统 23
1.3.1 分布式数据库系统 24
1.3.2 分布式文件系统 25
1.3.3 分布式计算框架 27
1.4 本章小结 28
习题 29
第2章 分布式计算使能技术 30
2.1 通信技术 30
2.1.1 通信方式 30
2.1.2 通信协议 38
2.2 远程过程调用 46
2.2.1 RPC的基本原理 47
2.2.2 RPC的设计问题 50
2.2.3 典型的RPC实现 56
2.3 各类资源抽象 62
2.3.1 计算抽象 62
2.3.2 数据抽象 69
2.4 本章小结 82
习题 83
**第二部分 分布式计算算法**
第3章 分布式计算系统中的时钟 85
3.1 逻辑时钟 85
3.1.1 定义 85
3.1.2 基本性质 86
3.1.3 逻辑时钟的实现 87
3.2 标量时间 88
3.2.1 定义 88
3.2.2 标量时间的性质 89
3.3 向量时间 90
3.3.1 定义 91
3.3.2 向量时间的性质 92
3.3.3 向量时间压缩 93
3.4 矩阵时间 94
3.4.1 定义 94
3.4.2 矩阵时间的性质 95
3.5 NTP物理时钟同步 95
3.5.1 概述及原理 96
3.5.2 NTP同步方法 96
3.6 全局状态与快照 97
3.6.1 一致性全局状态 97
3.6.2 FIFO信道的快照算法—Chandy-Lamport算法 99
3.6.3 非FIFO信道的快照算法—Lai-Yang算法 101
3.7 本章小结 104
习题 105
第4章 共识算法 106
4.1 分布式共识问题简介 106
4.1.1 共识问题的重要性 107
4.1.2 共识问题的核心问题 107
4.1.3 共识问题的挑战 108
4.2 Paxos算法 109
4.2.1 Paxos算法的主要角色 109
4.2.2 Paxos算法的基本流程 110
4.2.3 Paxos算法的例子 110
4.2.4 Paxos算法的优点 111
4.2.5 Paxos算法的缺点 112
4.2.6 Paxos算法的应用场景 112
4.2.7 Paxos算法的实现 113
4.3 Raft算法 114
4.3.1 Raft算法的主要角色 114
4.3.2 Raft算法的关键机制 115
4.3.3 Raft算法的例子 116
4.3.4 Raft算法的优点 117
4.3.5 Raft算法的缺点 118
4.3.6 Raft算法的应用场景 119
4.3.7 Raft算法的实现 120
4.3.8 Raft算法对比Paxos算法的优化和改进 122
4.4 拜占庭容错算法 124
4.4.1 拜占庭容错算法的核心思想 125
4.4.2 拜占庭容错算法的基本流程 126
4.4.3 拜占庭容错算法的例子 127
4.4.4 拜占庭容错算法的优点 129
4.4.5 拜占庭容错算法的缺点 130
4.4.6 拜占庭容错算法的应用场景 131
4.4.7 拜占庭容错算法的实现 132
4.5 本章小结 133
习题 134
第5章 图算法 135
5.1 基本概念 135
5.1.1 分布式计算系统中的图 135
5.1.2 分布式算法复杂度 136
5.1.3 一些术语与约定 139
5.2 基于洪泛的同步单一启动者生成树算法 140
5.2.1 算法描述 140
5.2.2 算法复杂度分析 142
5.2.3 思考与小结 143
5.3 基于洪泛的异步单一启动者生成树算法 143
5.3.1 算法描述 143
5.3.2 算法复杂度分析 146
5.3.3 思考与小结 147
5.4 基于洪泛的异步并发启动者生成树算法 147
5.4.1 算法描述 147
5.4.2 算法复杂度分析 151
5.4.3 思考与小结 151
5.5 异步并发启动者深度优先搜索生成树算法 152
5.5.1 算法描述 152
5.5.2 算法复杂度分析 154
5.6 单源最短路径算法：同步Bellman-Ford算法 154
5.6.1 算法描述 154
5.6.2 算法复杂度分析 155
5.6.3 思考与小结 155
5.7 单源最短路径算法：异步Bellman-Ford算法 156
5.7.1 算法描述 156
5.7.2 算法复杂度分析 157
5.7.3 思考与小结 157
5.8 全源最短路径算法：异步分布式Floyd-Warshall算法 158
5.8.1 集中式Floyd-Warshall算法 158
5.8.2 异步分布式Floyd-Warshall算法 159
5.8.3 算法复杂度分析 161
5.9 不依赖于生成树的受限洪泛算法 162
5.9.1 算法描述 162
5.9.2 算法复杂度分析 163
5.10 同步最小权重生成树算法 163
5.10.1 单节点上的最小生成树算法 163
5.10.2 分布式计算系统中的最小生成树算法 164
5.10.3 算法复杂度分析 166
5.11 异步最小权重生成树算法 167
5.12 本章小结 168
习题 168
京公网安备 11010102004214号