| 失效链接处理 |
|
分布式算法 PDF 下载
下载地址：
版权归出版社和原作者所有，链接已删除，请购买正版
用户下载说明：
电子版仅供预览，下载后24小时内务必删除，支持正版，喜欢的请购买正版书籍：
https://product.dangdang.com/29581621.html
相关截图：  资料简介： 本书对分布式算法进行了全面介绍，包括同步模型、异步模型和部分同步模型，针对这些模型讨论互斥性、一致性和通信问题，为设计、实现和分析分布式算法提供了蓝图。本书对分布式算法领域的许多经典问题给出了多种解决算法或者不可能性结果，绝大部分的算法附有详细的证明过程，并且有jing确的复杂度衡量。本书还配有大量习题，并在每章后列出了详细的参考文献。本书可作为高等院校计算机专业的研究生教材，尤其适合对计算机理论或体系结构感兴趣的学生学习，还适合分布式领域的设计人员和研究人员参考 资料目录： 译者序 前言 第1章 引言 1 1.1 相关主题 1 1.2 我们的观点 2 1.3 本书内容综述 4 1.4 参考文献注释 7 1.5 标记 8 部分 同步网络算法 第2章 建模I：同步网络模型 10 2.1 同步网络系统 10 2.2 故障 11 2.3 输入和输出 11 2.4 运行 12 2.5 证明方法 12 2.6 复杂度度量 12 2.7 随机化 13 2.8 参考文献注释 13 第3章 同步环中的领导者选择 14 3.1 问题 14 3.2 相同进程的不可能性结果 15 3.3 基本算法 15 3.4 通信复杂度为O (nlogn）的算法 17 3.5 非基于比较的算法 20 3.5.1 时间片算法 20 3.5.2 变速算法 20 3.6 基于比较的算法的下界 22 3.7 非基于比较的算法的下界* 26 3.8 参考文献注释 27 3.9 习题 27 第4章 一般同步网络中的算法 29 4.1 一般网络中的领导者选举 29 4.1.1 问题 29 4.1.2 简单的洪泛算法 29 4.1.3 降低通信复杂度 31 4.2 广度优先搜索 32 4.2.1 问题 33 4.2.2 基本的广度优先搜索算法 33 4.2.3 应用 34 4.3 短路径 35 4.4 小生成树 36 4.4.1 问题 36 4.4.2 基本定理 36 4.4.3 算法 38 4.5 独立集 40 4.5.1 问题 40 4.5.2 随机化算法 41 4.5.3 分析* 42 4.6 参考文献注释 44 4.7 习题 44 第5章 链路故障时的分布式 一致性 46 5.1 协同攻击问题—确定性版本 46 5.2 协同攻击问题—随机化版本 48 5.2.1 形式化模型 49 5.2.2 算法 49 5.2.3 不一致的下限 52 5.3 参考文献注释 54 5.4 习题 54 第6章 进程故障下的分布式 一致性 56 6.1 问题 57 6.2 针对停止故障的算法 58 6.2.1 基本算法 58 6.2.2 减少通信 60 6.2.3 指数信息收集算法 61 6.2.4 带鉴别的Byzantine一致性 66 6.3 针对Byzantine故障的算法 66 6.3.1 举例 67 6.3.2 Byzantine一致性问题的EIG 算法 68 6.3.3 使用二元Byzantine一致性的 一般Byzantine一致性问题 71 6.3.4 减少通信开销 72 6.4 Byzantine一致性问题中进程的 个数 75 6.5 一般图中的Byzantine一致性 问题 78 6.6 弱Byzantine一致性 81 6.7 有停止故障时的轮数 82 6.8 参考文献注释 88 6.9 习题 89 第7章 更多的一致性问题 93 7.1 k一致性问题 93 7.1.1 问题 93 7.1.2 算法 94 7.1.3 下界* 95 7.2 近似一致性 103 7.3 提交问题 106 7.3.1 问题 106 7.3.2 两阶段提交 107 7.3.3 三阶段提交 108 7.3.4 消息数的下界 110 7.4 参考文献注释 112 7.5 习题 112 第二部分 异步算法 第8章 建模II：异步系统模型 116 8.1 输入/输出自动机 116 8.2 自动机的操作 120 8.2.1 合成 120 8.2.2 隐藏 123 8.3 公平性 123 8.4 问题的输入和输出 126 8.5 属性与证明方法 126 8.5.1 不变式断言 126 8.5.2 轨迹属性 126 8.5.3 安全与活性属性 127 8.5.4 合成推理 129 8.5.5 层次化证明 131 8.6 复杂度衡量 133 8.7 不可区分的运行 134 8.8 随机化 134 8.9 参考文献注释 134 8.10 习题 135 第二部分A?异步共享存储器算法 第9章 建模III：异步共享存储器 模型 138 9.1 共享存储器系统 138 9.2 环境模型 140 9.3 不可区分状态 141 9.4 共享变量类型 142 9.5 复杂度衡量 145 9.6 故障 146 9.7 随机化 146 9.8 参考文献注释 146 9.9 习题 146 第10章 互斥 148 10.1 异步共享存储器模型 148 10.2 问题 150 10.3 Dijkstra的互斥算法 153 10.3.1 算法 153 10.3.2 正确性证明 156 10.3.3 互斥条件的一个断言式 证明 158 10.3.4 运行时间 159 10.4 互斥算法的更强条件 160 10.5 锁定权互斥算法 162 10.5.1 双进程算法 162 10.5.2 n进程算法 165 10.5.3 锦标赛算法 169 10.6 使用单写者共享寄存器的算法 172 10.7 Bakery算法 174 10.8 寄存器数量的下界 176 10.8.1 基本事实 177 10.8.2 单写者共享变量 177 10.8.3 多写者共享变量 178 10.9 使用读–改–写共享变量的 互斥 182 10.9.1 基本问题 182 10.9.2 有界绕过次数 183 10.9.3 锁定权 188 10.9.4 模拟证明 190 10.10 参考文献注释 193 10.11 习题 193 第11章 资源分配 197 11.1?问题 197 11.1.1 显式资源规格说明和互斥规格说明 197 11.1.2 资源分配问题 198 11.1.3 哲学家用餐问题 199 11.1.4 解法的受限形式 200 11.2 对称哲学家用餐算法的 不存在性 200 11.3 右–左哲学家用餐算法 202 11.3.1 等待链 202 11.3.2 基本算法 203 11.3.3 扩展 205 11.4 随机哲学家用餐算法* 208 11.4.1 算法* 208 11.4.2 正确性* 210 11.5 参考文献注释 216 11.6 习题 216 第12章 一致性 218 12.1?问题 218 12.2 使用读/写共享存储器的一致性 问题 220 12.2.1 限制 221 12.2.2 术语 221 12.2.3 双价初始化 222 12.2.4 无等待终止性的不可能性 222 12.2.5 单故障终止性的不可能性 结果 224 12.3 读/改/写共享存储器上的 一致性问题 227 12.4 其他共享存储器类型 227 12.5 异步共享存储器系统中的可 计算性* 227 12.6 参考文献注释 229 12.7 习题 229 第13章 原子对象 232 13.1 定义和基本结论 232 13.1.1 原子对象的定义 233 13.1.2 规范无等待原子对象 自动机 238 13.1.3 原子对象的合成 240 13.1.4 原子对象和共享变量 240 13.1.5 显示原子性的一个充分 条件 245 13.2 用读/写变量实现读–改–写 原子对象 246 13.3 共享存储器的原子快照 247 13.3.1 问题 247 13.3.2 带无界变量的一个算法 248 13.3.3 带有界变量的一个算法* 251 13.4 读/写原子对象 254 13.4.1 问题 254 13.4.2 证明原子性的其他引理 255 13.4.3 带无界变量的一个算法 256 13.4.4 两个写者的有界算法 259 13.4.5 使用快照的算法 263 13.5 参考文献注释 264 13.6 习题 265 第二部分B 异步网络算法 第14章 建模IV：异步网络模型 268 14.1 发送/接收系统 268 14.1.1 进程 268 14.1.2 发送/接收通道 269 14.1.3 异步发送/接收系统 272 14.1.4 使用可靠FIFO通道的发送/ 接收系统的属性 272 14.1.5 复杂度度量 273 14.2 广播系统 274 14.2.1 进程 274 14.2.2 广播通道 274 14.2.3 异步广播系统 275 14.2.4 采用可靠广播通道的广播系统的属性 275 14.2.5 复杂度度量 275 14.3 多播系统 275 14.3.1 进程 276 14.3.2 多播通道 276 14.3.3 异步多播系统 276 14.4 参考文献注释 277 14.5 习题 277 第15章 基本异步网络算法 279 15.1 环中的领导者选举 279 15.1.1 LCR算法 279 15.1.2 HS算法 283 15.1.3 PetersonLeader算法 283 15.1.4 通信复杂度的下界 286 15.2 任意网络中的领导者选举 291 15.3 生成树的构造、广播和敛播 292 15.4 广度优先搜索和短路径 295 15.5 小生成树 300 15.5.1 问题描述 301 15.5.2 同步算法：回顾 301 15.5.3 GHS算法：概要 302 15.5.4 更详细的算法 303 15.5.5 特殊消息 305 15.5.6 复杂度分析 306 15.5.7 GHS算法的正确性证明 307 15.5.8 简单“同步”策略 308 15.5.9 应用到领导者选举算法中 308 15.6 参考文献注释 309 15.7 习题 309 第16章 同步器 313 16.1 问题 313 16.2 局部同步器 315 16.3 安全同步器 319 16.3.1 前端自动机 320 16.3.2 通道自动机 321 16.3.3 安全同步器的任务 321 16.3.4 正确性 322 16.4 安全同步器的实现 322 16.4.1 同步器Alpha 322 16.4.2 同步器Beta 323 16.4.3 同步器Gamma 323 16.5 应用 327 16.5.1 领导者选举 327 16.5.2 广度优先搜索 327 16.5.3 短路径 328 16.5.4 广播与确认 328 16.5.5 独立集 328 16.6 时间下界 328 16.7 参考文献注释 331 16.8 习题 331 第17章 共享存储器与网络 333 17.1 从异步共享存储器模型到异步 网络模型的转换 333 17.1.1 问题 333 17.1.2 无故障时的策略 334 17.1.3 容忍进程故障的算法 339 17.1.4 对于n/2故障的不可能性 结果 342 17.2 从异步网络模型到异步共享存储器模型的转换 343 17.2.1 发送/接收系统 344 17.2.2 广播系统 345 17.2.3 异步网络中一致性的 不可能性 346 17.3 参考文献注释 346 17.4 习题 346 第18章 |
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
