当前位置：首页 > news >正文

分布式算法精髓

news 来源：原创 2024/5/18 20:02:18

随着比特币和区块链在社会上的影响力越来越广泛，分布式系统和分布式算法引起很多人的关注。区块链本质上是一个分布式网络，区块链共识算法是分布式算法中一个特殊的类。掌握必要的分布式算法对理解目前广泛使用的互联网/物联网的诸多处理算法非常有帮助。

什么是分布式算法？在过去的几十年里，我们在分布式系统和网络领域经历了前所未有的增长。目前分布式计算涵盖了当今计算机和通信领域中发生的许多活动。事实上，分布式计算具有相当多样化的应用领域。互联网是分布式系统，无线通信、云计算或并行计算、多核系统、移动网络也是如此。此外，蚁群、大脑甚至人类社会都可以被建模为分布式系统。

这些应用的共同点是，系统中的许多处理器或实体(通常称为节点)在任何时刻都是活跃的。节点有一定的自由度：有自己的硬件和软件。然而，这些节点可以共享共同的资源和信息，为了解决涉及几个甚至所有节点的问题，协调是必要的。

尽管有这些共性，但人脑与多核处理器当然有很大的不同。由于这种差异，人们在分布式计算领域研究了许多不同的模型和参数。在一些系统中，节点是同步运行的，在另一些系统中，节点是异步运行的。有简单的同构系统，也有异构系统，异构系统中包含不同类型的节点，它们可能具有不同的能力、目标等，需要进行交互。有不同的通信技术：节点可以通过交换消息进行通信，也可以通过共享内存进行通信。偶尔通信基础设施是为某一应用量身定做的，有时人们不得不使用给定的基础设施。分布式系统中的节点经常共同解决一个全局性的任务，偶尔节点是自主的代理，有自己的议程，并竞争共同的资源。

有时可以认为节点工作正常，有时节点可能发生故障。与单节点系统相比，分布式系统在发生故障的情况下仍可能正常工作，因为其他节点可以接管故障节点的工作。故障有不同的种类：节点可能只是崩溃，也可能表现出一种任意的、错误的行为，甚至可能达到无法与恶意（也就是拜占庭）行为区分的程度。也有可能节点确实遵循了规则，然而它们调整参数以获得系统的最大收益，换句话说，节点的行为是自私的。

显然，可以研究的模型有很多（甚至还有更多的模型组合）。我们现在不对它们进行详细讨论，只是在使用它们时进行定义。学完《分布式算法精髓》这本书，读者应该知道最重要的概念，并且应该有一个大致的印象。

扫码查看 ↑

内容概览

本书介绍分布式计算的基本原理，突出常见的主题和技术。特别是，我们研究了分布式系统设计的一些基本问题:

●通信：通信不是免费的，通信成本往往决定了本地处理或存储的成本。有时我们甚至认为除了通信之外的一切都免费。

●协调：如何协调一个分布式系统，让它有效地执行一些任务？有多少开销是不可避免的？

●容错性：分布式系统的一个主要优点是即使在出现故障的情况下系统作为一个整体也能生存下来。

●本地性：网络在不断发展。幸运的是，完成一个任务并不总是需要全局信息，通常情况下，如果节点能与邻居通信就足够了。本地性解决方案是否可行，是本书的核心话题之一。

●并行性：如果提高计算能力，比如增加可以分担工作量的节点数量，那么完成一个任务的速度有多快？对于一个给定的问题，并行性有多大可能？

●打破对称性：有时需要选择一些节点来协调计算或通信。这是由一种叫作打破对称性的技术来实现的。

●同步：如何在异步环境中实现同步算法？

●不确定性：如果用一个词来恰当地描述本书，那大概就是“不确定性”。由于整个系统是分布式的，一个节点不可能知道其他节点在这个确切的时刻在做什么，尽管缺乏全局知识，但还是需要节点完成手头的任务。

最后，还有一些领域我们不会在本书中涉及，主要是因为这些主题非常重要，有单独的书来讲述它们。这类主题的例子是分布式编程或安全/密码学。

综上所述，在本书中，我们探讨基本的算法思想和下界技术，这两方面可以说是分布式计算和网络算法的“珠玑”。

作者简介

罗杰·沃滕霍弗（Roger Wattenhofer） 　博士，苏黎世联邦理工学院信息技术和电气工程系教授。之前曾任职于微软研究院、布朗大学和麦考瑞大学。他的研究兴趣是算法和系统，涉及分布式系统、定位系统、容错分布式系统、高效网络算法和比特币等。他已发表学术论文300多篇，曾获得包括“分布式计算创新奖”在内的众多奖项。除本书外，他还著有Blockchain Science: Distributed Ledger Technology（2017）一书。

上拉下滑查看 ↓

译者序

前言

第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