分布式计算

作者简介

《分布式计算:原理、算法与系统》内容简介：分布式计算是指由计算机网络连接的多处理平台的各种形式的计算、信息访问与信息交换。《分布式计算:原理、算法与系统》覆盖了分布式计算中的理论、算法以及系统方面的基本原理和模型。兼顾理论的广度与深度，注重实际，包括了互斥、死锁检测、认证和失效恢复等常见问题。算法经过认真选择，描述清晰，使用简单的解释和图表来说明算法。

书籍目录

第一章引言 1.1定义 1.2与计算机系统部件的关系 1.3动机 1.4与并行多处理器／多计算机系统的关系 1.4.1并行系统的特性 1.4.2 Flynn的分类法 1.4.3耦合、并行、并发及粒度 1.5 消息传递系统与共享内存系统的对比 1.5.1在共享内存的系统上仿真消息传递 1.5.2在消息传递系统上仿真共享内存 1.6分布式通信的原语 1.6.1阻塞／非阻塞，同步／异步原语  1.6.2处理器同步性 1.6.3库与标准 1.7同步与异步执行 1.7.1通过同步系统仿真异步系统 1.7.2通过异步系统仿真同步系统 1.7.3仿真 1.8设计主题与挑战 1.8.1从系统角度看分布式系统的挑战 1.8.2分布式计算中的算法挑战 1.8.3分布式计算的应用以及更新的挑战 1.9关于主题的选择与覆盖 1.10本章小结 1.11习题 1.12参考文献说明 参考文献 第二章分布式计算模型 2.1分布式程序 2.2分布式运行模型 2.3通信网络模型 2.4分布式系统的全局状态 2.4.1全局状态 2.5分布式计算的运行分割 2.6事件的过去和未来锥面 2.7进程通信模型 2.8本章小结 2.9习题 2.10参考文献说明 参考文献 第三章逻辑时间 3.1引言 3.2逻辑时钟框架 3.2.1定义 3.2.2实现逻辑时钟 3.3标量时间 3.3.1定义 3.3.2基本性质 3.4向量时间 3.4.1定义 3.4.2基本性质 3.4.3有关向量时钟的大小  3.5向量时钟的有效实现 3.5.1 Singhal-Kshemkalyani的差量技术 3.5.2 Fowler-Zwaenepoel的直接依赖技术 3.6 Jard-Jourdan的自适应技术 3.7矩阵时间 3.7.1定义 3.7.2基本性质 3.8虚拟时间 3.8.1虚拟时间的定义 3.8.2与Lamport逻辑时钟比较 3.8.3时间变形机制 3.8.4本地控制机制 3.8.5全局控制机制 3.9物理时钟同步：NTP 3.9.1动机 3.9.2定义及术语 3.9.3时钟不准确性 3.10本章小结 3.11习题 3.12参考文献说明 参考文献 第四章记录全局状态与快照算法 4.1引言 4.2系统模型和定义 4.2.1系统模型 4.2.2一致性全局状态 4.2.3有关分割的解 4.2.4记录全局快照时遇到的问题 4.3 FIFO通道的快照算法 4.3.1 Chandy-Lamport算法 4.3.2被记录全局状态的性质 4.4 Chandy-Lamport算法的变种 4.4.1 Spezialetti-Kearns算法 4.4.2 Venkatesan快照增量算法 4.4.3 Helary波同步方法 4.5非FIFO通道的快照算法 4.5.1 Lai-Yang算法 4.5.2 Li等人的算法 4.5.3 Mattern算法 4.6因果传递系统快照 4.6.1进程状态记录 4.6.2 Acharya-Badrinath算法中的通道状态记录 4.6.3 Alagar-Venkatesan算法中的通道状态记录  4.7监控全局状态 4.8一致性全局快照的必要和充分条件 4.8.1 Zigzag路径和一致性全局快照 4.9找出分布式计算中的一致性全局快照 4.9.1找出一致性全局快照  4.9.2枚举式一致性快照Manivannan-Netzer-Singhal算法 4.9.3在分布式计算中找出Z路径 4.10本章小结 4.11习题 4.12参考文献说明 参考文献 第五章术语和基本算法 5.1拓扑抽象和覆盖 5.2分类和基本概念 5.2.1应用执行和控制算法执行 5.2.2集中式算法和分布式算法 5.2.3对称算法和非对称算法 5.2.4匿名算法 5.2.5一致算法 5.2.6自适应算法 5.2.7确定性执行对非确定性执行  5.2.8执行抑制 5.2.9同步系统和异步系统 5.2.10联机算法与脱机算法 5.2.11故障模型 5.2.12无需等待算法 5.2.13通信通道 5.3复杂度测量和度量 5.4程序结构 5.5图的基本算法 5.5.1使用洪泛法的同步单一启动者生成树算法 5.5.2使用洪泛法的异步单一启动者生成树算法 5.5.3使用洪泛法的异步并发启动者生成树算法 …… 第六章消息序与组通信 第七章终止检测 第八章知识推理 第九章分布式互斥算法 第十章死锁检测 第十一章全局谓词的检测 第十二章分布式共享内存 第十三章检查点和卷回恢复 第十四章共识和协定算法 第十五章失效检测 第十六章分布式系统中的验证 第十七章自稳定 第十八章对等计算及覆盖网络

编辑推荐

《分布式计算:原理、算法与系统》涵盖了最新的算法、大量的图解以及丰富的示例和习题，将有助于电子与计算机工程和计算机科学等专业研究生学习该课程，数据网络及传感器网络等方面的科研工作者也可参考使用。

内容概要

作者：（美国）克谢姆卡亚尼（Ajay D.Kshemkalyani） （美国）辛哈（Mukesh Singhal） 译者：余宏亮 张冬艳  克谢姆卡亚尼，伊利诺伊大学计算机科学系副教授。1991年获俄亥俄州立大学计算机与信息科学博士学位，1999年获得美国国家科学基金会的CAREER奖。IEEE高级会员。研究领域包括分布式计算、算法、计算机网络和并行系统。现任Computer Networks编辑委员会委员。 辛哈，肯塔基大学计算机科学系教授，Gartner Group Endowed主席。1986年获马里兰大学计算机科学博士学位。IEEEFellow，于2003年获IEEE技术成就奖。现任IEEE Transactions on Parallel and Distributed Systems及IEEE Transactions on Computers编辑委员会委员。研究领域包括分布式系统、计算机网络、无线及移动计算系统、性能评价和计算机安全等。

媒体关注与评论

　　“本书比较适合于进行分布式系统的教学以及加深相关工程人员对分布式系统原理的理解。由于现在市面上有关分布式算法方面的书还很少，而与系统相结合方面就更少了。因此，建议翻译本书，方便相关的学生、研究人员与工程技术人面参考。”　　——清华大学 郑纬民

名人推荐

“本书比较适合于进行分布式系统的教学以及加深相关工程人员对分布式系统原理的理解。由于现在市面上有关分布式算法方面的书还很少，而与系统相结合方面的就更少了。因此，建议翻译本书，方便相关的学生、研究人员与工程技术人员参考。” --清华大学 郑纬民

章节摘录

版权页：   插图：   3.8.3 时间变形机制 在使用时间变形机制实现虚拟时间时，消息的虚拟接收事件被认为是其时间戳。虚拟时间正确实现的充分和必要条件是每个进程必须按时间戳次序处理输入的信息，因处理的速度和消息延迟的变数很大，故该条件的限制非常严格也很不理想。所以有些进程在虚拟时间上快于其他进程也是很自然的。 因为我们假定虚拟时间是实数，所以一个进程仅凭本地信息就阻塞并等待带有下一个时间戳的消息是不可能的。带有较早时间戳的消息迟到的可能性也总是存在。这样，当进程执行一个消息时，确定带有较早时间戳的消息是否会迟到是非常困难的。这就是时间变形机制将要解决的虚拟时问的中心问题。 时间变形机制的优点是它具有不依赖于下层计算机结构且很容易实现于不同系统的可移植性。总之，消息通信被认为是可靠的，但消息的传送可能不按FIFO次序进行。 时间变形机制由两部分组成：本地控制机制和全局控制机制。本地控制机制保证按正确的次序执行事件和处理消息；全局控制机制处理全局进展、终止检测、I／O错误处理及流控制等全局问题。 3.8.4 本地控制机制 在本地控制机制的实现过程中，不存在全局时钟变量。每个进程有一个本地时钟，一个进程的本地虚拟时钟在该进程上的一个事件存在期间不发生变化，仅在两个事件之间改变。在处理来自输入队列的下一消息时，进程把它的时钟增加到这个消息的时间戳的值。在任一瞬间，每个进程的虚拟时间值可能不同，但该值对系统中其他进程是透明的。 当一个消息被发送时，拷贝发送方的时钟为虚拟发送时间，而接收方的名称和虚拟接收时间根据应用特定的上下文赋值。 在一个进程上的所有到达消息按时间戳（收到时间）增序存储在输入队列中。理想的情况是应当没有过去（称为迟到的消息）的消息到达一个进程。然而，由于进程不同的计算速度以及网络延迟等因素，进程会接收到迟到的消息。虚拟时间的语义要求输入消息严格按时间戳次序被每个进程接收。实现该要求的唯一方法是：在收到一个迟到的消息时，接受者回滚到较早的一个虚拟时间，撤销其间所产生的一切附带的影响，然后通过以合适的顺序执行这个迟到的消息并再次向前执行。

---

 分布式计算下载 精选章节试读

---