基本信息
- 作者： [瑞士]罗杰·沃滕霍弗（Roger Wattenhofer）
- 译者： 黄智濒
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111705895
- 上架时间：2022-6-7
- 出版日期：2022 年5月
- 开本：16开
- 页码：205
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
编辑推荐
聚焦于分布式算法原理和下界技术，涵盖核心思想及重要概念
内容简介
作译者
[瑞士]罗杰·沃滕霍弗（Roger Wattenhofer） 著：---作者简介---
罗杰·沃滕霍弗（Roger Wattenhofer） 博士，苏黎世联邦理工学院信息技术和电气工程系教授。之前曾任职于微软研究院、布朗大学和麦考瑞大学。他的研究兴趣是算法和系统，涉及分布式系统、定位系统、容错分布式系统、高效网络算法和比特币等。他已发表学术论文300多篇，曾获得包括“分布式计算创新奖”在内的众多奖项。除本书外，他还著有Blockchain Science: Distributed Ledger Technology（2017）一书。
---译者简介---
黄智濒 计算机系统结构博士，北京邮电大学计算机学院讲师。长期从事机器学习、超大规模并行计算、GPU加速计算以及三维计算机视觉和深度学习架构方面的研究。
罗杰·沃滕霍弗（Roger Wattenhofer） 博士，苏黎世联邦理工学院信息技术和电气工程系教授。之前曾任职于微软研究院、布朗大学和麦考瑞大学。他的研究兴趣是算法和系统，涉及分布式系统、定位系统、容错分布式系统、高效网络算法和比特币等。他已发表学术论文300多篇，曾获得包括“分布式计算创新奖”在内的众多奖项。除本书外，他还著有Blockchain Science: Distributed Ledger Technology（2017）一书。
---译者简介---
黄智濒 计算机系统结构博士，北京邮电大学计算机学院讲师。长期从事机器学习、超大规模并行计算、GPU加速计算以及三维计算机视觉和深度学习架构方面的研究。
目录
译者序
前言
第1章 顶点着色1
1.1 问题和模型1
1.2 着色树3
1.3 本章注释8
1.4 参考文献9
第2章 树算法13
2.1 广播13
2.2 融合广播15
2.3 广度优先搜索树的构建15
2.4 最小生成树的构建17
2.5 本章注释20
2.6 参考文献20
第3章 领导人选举23
3.1 匿名领导人选举23
3.2 异步环24
3.3 下界27
3.4 同步环29
3.5 本章注释30
前言
第1章 顶点着色1
1.1 问题和模型1
1.2 着色树3
1.3 本章注释8
1.4 参考文献9
第2章 树算法13
2.1 广播13
2.2 融合广播15
2.3 广度优先搜索树的构建15
2.4 最小生成树的构建17
2.5 本章注释20
2.6 参考文献20
第3章 领导人选举23
3.1 匿名领导人选举23
3.2 异步环24
3.3 下界27
3.4 同步环29
3.5 本章注释30
前言
什么是分布式算法
在过去的几十年里，我们在分布式系统和网络领域经历了前所未有的增长。目前分布式计算涵盖了当今计算机和通信领域中发生的许多活动。事实上，分布式计算具有相当多样化的应用领域。互联网是分布式系统，无线通信、云计算或并行计算、多核系统、移动网络也是如此。此外，蚁群、大脑甚至人类社会都可以被建模为分布式系统。
这些应用的共同点是，系统中的许多处理器或实体(通常称为节点)在任何时刻都是活跃的。节点有一定的自由度：有自己的硬件和软件。然而，这些节点可以共享共同的资源和信息，为了解决涉及几个甚至所有节点的问题，协调是必要的。
尽管有这些共性，但人脑与多核处理器当然有很大的不同。由于这种差异，人们在分布式计算领域研究了许多不同的模型和参数。在一些系统中，节点是同步运行的，在另一些系统中，节点是异步运行的。有简单的同构系统，也有异构系统，异构系统中包含不同类型的节点，它们可能具有不同的能力、目标等，需要进行交互。有不同的通信技术：节点可以通过交换消息进行通信，也可以通过共享内存进行通信。偶尔通信基础设施是为某一应用量身定做的，有时人们不得不使用给定的基础设施。分布式系统中的节点经常共同解决一个全局性的任务，偶尔节点是自主的代理，有自己的议程，并竞争共同的资源。
有时可以认为节点工作正常，有时节点可能发生故障。与单节点系统相比，分布式系统在发生故障的情况下仍可能正常工作，因为其他节点可以接管故障节点的工作。故障有不同的种类：节点可能只是崩溃，也可能表现出一种任意的、错误的行为，甚至可能达到无法与恶意（也就是拜占庭）行为区分的程度。也有可能节点确实遵循了规则，然而它们调整参数以获得系统的最大收益，换句话说，节点的行为是自私的。
显然，可以研究的模型有很多（甚至还有更多的模型组合）。我们现在不对它们进行详细讨论，只是在使用它们时进行定义。学完本书，读者应该知道最重要的概念，并且应该有一个大致的印象。
本书概览
本书介绍分布式计算的基本原理，突出常见的主题和技术。特别是，我们研究了分布式系统设计的一些基本问题:
●通信：通信不是免费的，通信成本往往决定了本地处理或存储的成本。有时我们甚至认为除了通信之外的一切都免费。
●协调：如何协调一个分布式系统，让它有效地执行一些任务？有多少开销是不可避免的？
●容错性：分布式系统的一个主要优点是即使在出现故障的情况下系统作为一个整体也能生存下来。
●本地性：网络在不断发展。幸运的是，完成一个任务并不总是需要全局信息，通常情况下，如果节点能与邻居通信就足够了。本地性解决方案是否可行，是本书的核心话题之一。
●并行性：如果提高计算能力，比如增加可以分担工作量的节点数量，那么完成一个任务的速度有多快？对于一个给定的问题，并行性有多大可能？
●打破对称性：有时需要选择一些节点来协调计算或通信。这是由一种叫作打破对称性的技术来实现的。
●同步：如何在异步环境中实现同步算法？
●不确定性：如果用一个词来恰当地描述本书，那大概就是“不确定性”。由于整个系统是分布式的，一个节点不可能知道其他节点在这个确切的时刻在做什么，尽管缺乏全局知识，但还是需要节点完成手头的任务。
最后，还有一些领域我们不会在本书中涉及，主要是因为这些主题非常重要，有单独的书来讲述它们。这类主题的例子是分布式编程或安全/密码学。
综上所述，在本书中，我们探讨基本的算法思想和下界技术，这两方面可以说是分布式计算和网络算法的“珠玑”。
前言注释
关于本书主题已经有许多优秀的教科书。最密切相关的书是由David Peleg\[Pel00\]所著的，它提供了一些素材。Peleg的书重点讨论网络分区、覆盖、分解和跨接器(这是一个有趣的领域，我们在本书中只是有所提及)。有大量的教科书与本书的一两章内容重叠，例如，[Lei92，Bar96，Lyn96，Tel01，AW04，HKP+05，CLRS09，Suo12，TR18]。另一门相关课程是由James Aspnes[Asp]所作，还有一门课程是由Jukka Suomela[Suo14]所作。
在过去的几十年里，我们在分布式系统和网络领域经历了前所未有的增长。目前分布式计算涵盖了当今计算机和通信领域中发生的许多活动。事实上，分布式计算具有相当多样化的应用领域。互联网是分布式系统，无线通信、云计算或并行计算、多核系统、移动网络也是如此。此外，蚁群、大脑甚至人类社会都可以被建模为分布式系统。
这些应用的共同点是，系统中的许多处理器或实体(通常称为节点)在任何时刻都是活跃的。节点有一定的自由度：有自己的硬件和软件。然而，这些节点可以共享共同的资源和信息，为了解决涉及几个甚至所有节点的问题，协调是必要的。
尽管有这些共性，但人脑与多核处理器当然有很大的不同。由于这种差异，人们在分布式计算领域研究了许多不同的模型和参数。在一些系统中，节点是同步运行的，在另一些系统中，节点是异步运行的。有简单的同构系统，也有异构系统，异构系统中包含不同类型的节点，它们可能具有不同的能力、目标等，需要进行交互。有不同的通信技术：节点可以通过交换消息进行通信，也可以通过共享内存进行通信。偶尔通信基础设施是为某一应用量身定做的，有时人们不得不使用给定的基础设施。分布式系统中的节点经常共同解决一个全局性的任务，偶尔节点是自主的代理，有自己的议程，并竞争共同的资源。
有时可以认为节点工作正常，有时节点可能发生故障。与单节点系统相比，分布式系统在发生故障的情况下仍可能正常工作，因为其他节点可以接管故障节点的工作。故障有不同的种类：节点可能只是崩溃，也可能表现出一种任意的、错误的行为，甚至可能达到无法与恶意（也就是拜占庭）行为区分的程度。也有可能节点确实遵循了规则，然而它们调整参数以获得系统的最大收益，换句话说，节点的行为是自私的。
显然，可以研究的模型有很多（甚至还有更多的模型组合）。我们现在不对它们进行详细讨论，只是在使用它们时进行定义。学完本书，读者应该知道最重要的概念，并且应该有一个大致的印象。
本书概览
本书介绍分布式计算的基本原理，突出常见的主题和技术。特别是，我们研究了分布式系统设计的一些基本问题:
●通信：通信不是免费的，通信成本往往决定了本地处理或存储的成本。有时我们甚至认为除了通信之外的一切都免费。
●协调：如何协调一个分布式系统，让它有效地执行一些任务？有多少开销是不可避免的？
●容错性：分布式系统的一个主要优点是即使在出现故障的情况下系统作为一个整体也能生存下来。
●本地性：网络在不断发展。幸运的是，完成一个任务并不总是需要全局信息，通常情况下，如果节点能与邻居通信就足够了。本地性解决方案是否可行，是本书的核心话题之一。
●并行性：如果提高计算能力，比如增加可以分担工作量的节点数量，那么完成一个任务的速度有多快？对于一个给定的问题，并行性有多大可能？
●打破对称性：有时需要选择一些节点来协调计算或通信。这是由一种叫作打破对称性的技术来实现的。
●同步：如何在异步环境中实现同步算法？
●不确定性：如果用一个词来恰当地描述本书，那大概就是“不确定性”。由于整个系统是分布式的，一个节点不可能知道其他节点在这个确切的时刻在做什么，尽管缺乏全局知识，但还是需要节点完成手头的任务。
最后，还有一些领域我们不会在本书中涉及，主要是因为这些主题非常重要，有单独的书来讲述它们。这类主题的例子是分布式编程或安全/密码学。
综上所述，在本书中，我们探讨基本的算法思想和下界技术，这两方面可以说是分布式计算和网络算法的“珠玑”。
前言注释
关于本书主题已经有许多优秀的教科书。最密切相关的书是由David Peleg\[Pel00\]所著的，它提供了一些素材。Peleg的书重点讨论网络分区、覆盖、分解和跨接器(这是一个有趣的领域，我们在本书中只是有所提及)。有大量的教科书与本书的一两章内容重叠，例如，[Lei92，Bar96，Lyn96，Tel01，AW04，HKP+05，CLRS09，Suo12，TR18]。另一门相关课程是由James Aspnes[Asp]所作，还有一门课程是由Jukka Suomela[Suo14]所作。
媒体评论
在过去的几十年里，分布式系统和网络领域经历了前所未有的增长。互联网是分布式系统，云计算、并行计算、多核系统、移动网络也是分布式系统。此外，蚁群、大脑甚至人类社会都可以被建模为分布式系统。
本书聚焦于分布式算法思想和下界技术，强调常见主题和基本原理，并讨论了树、图、社交网络和无线协议等问题。书中涉及的基本问题包括通信、协调、容错性、本地性、并行性、打破对称性、同步和不确定性。通过书中清晰的阐释，读者将熟悉重要的概念，并逐步掌握分布式算法的精髓。
作者简介
罗杰·沃滕霍弗（Roger Wattenhofer）博士，苏黎世联邦理工学院信息技术和电气工程系教授。之前曾任职于微软研究院、布朗大学和麦考瑞大学。他的研究兴趣是算法和系统，涉及分布式系统、定位系统、容错分布式系统、高效网络算法和比特币等。他已发表学术论文300多篇，曾获得包括“分布式计算创新奖”在内的众多奖项。除本书外，他还著有Blockchain Science: Distributed Ledger Technology（2017）一书。
译者简介
黄智濒计算机系统结构博士，北京邮电大学计算机学院讲师。长期从事机器学习、超大规模并行计算、GPU加速计算以及三维计算机视觉和深度学习架构方面的研究。
本书聚焦于分布式算法思想和下界技术，强调常见主题和基本原理，并讨论了树、图、社交网络和无线协议等问题。书中涉及的基本问题包括通信、协调、容错性、本地性、并行性、打破对称性、同步和不确定性。通过书中清晰的阐释，读者将熟悉重要的概念，并逐步掌握分布式算法的精髓。
作者简介
罗杰·沃滕霍弗（Roger Wattenhofer）博士，苏黎世联邦理工学院信息技术和电气工程系教授。之前曾任职于微软研究院、布朗大学和麦考瑞大学。他的研究兴趣是算法和系统，涉及分布式系统、定位系统、容错分布式系统、高效网络算法和比特币等。他已发表学术论文300多篇，曾获得包括“分布式计算创新奖”在内的众多奖项。除本书外，他还著有Blockchain Science: Distributed Ledger Technology（2017）一书。
译者简介
黄智濒计算机系统结构博士，北京邮电大学计算机学院讲师。长期从事机器学习、超大规模并行计算、GPU加速计算以及三维计算机视觉和深度学习架构方面的研究。
