Theory of distributed computing 学习笔记(4)

2023-1-18

Broadcast, Convergecast,and Spanning Trees

别问我③去哪了, 错过了课整理笔记很麻烦..

(资料图)

这篇笔记的核心内容是关于广播算法. 在很多很多的应用中,例如并行计算, 网络系统等, 我们需要让网络中的不同节点互相传递信息. 有时候我们会想要向网络中的所有成员广播一些信息，例如正确的计算结果或者是网络拓扑结构的变更. 

一个最简单最朴素的想法就是对整个网络进行广度优先搜索. 每个节点维护一个布尔变量用于记录是否见到需要传递的消息. 当节点收到消息M的时候，如果之前见过这个消息,那么我们便向周围的所有节点传递这个消息. 反之什么都不做. 这个算法类似与大水漫灌: 消息从根节点触发，灌向所有的节点，最终填满整个网络. 因此我们将这个朴素算法称之为flooding algrithom(洪水算法)。很蠢，但是一个有效的入门算法。

我们之前讨论过，衡量一个分布式算法的复杂度有两个层次的指标: 消息复杂度和时间复杂度.

Claim: flooding algrithm 将在D时间内使用|E|条消息将信息M广播到整个网络.其中D代表的是网络的直径, (网络中两两节点之间的最短路的最大值)，而|E|代表的是网络中的边的数量.

接下来我们来证明这两个复杂度的正确性

消息复杂度:

每个节点都会发送一次信息，每个信息的数量等于节点所连接的边的数量. 因此消息的数量和便是网络中的边总数|E|

时间复杂度/算法正确性

数学归纳法: 我们将对节点和边的距离d(v,root)使用数学归纳法.证明每个在网络里的节点必定能在d时间内收到消息

Case0:根节点在d(v,root)=0收到消息

Case i+1. d(v,root)=i的节点收到消息以后, d(v,root)=i+1的节点 会在i+1的时间收到消息. 

因此 网络中d(v,root)=d的节点必定能在d时间内收到消息, 如果d(v,root)>d 那么这个节点v并不处于网络中. 所以时间复杂度为D。

一个很显而易见的观察便是, flooding算法的消息复杂度并不算友好: 我们需要|E|的消息来传递信息，而边的数量有时候会远大于节点的数量, 那么我们要怎么样来优化它呢? 一个很简单的想法便是在执行flooding算法的同时构造一个生成树. 这样便能在|N|消息内完成往后的所有消息传递. 那么我们要怎么构造生成树呢? 

一个很简单的办法便是记录下每个节点第一次收到信息的来源并且将其记录为自己在生成树中的父节点. 我们可以通过在以上对flooding算法的证明中进行小幅度的修改来证明新生成的树中的每个节点都有一条去根节点的路径.留作读者习题自行证明:D

然而, 这样的生成树并不一定是一个好的生成树. 考虑一个不同步的分布式系统，我们可以很轻松的构造一个成链的生成树从而导致极差的时间复杂度.

以上的讨论中，我们并没有特别注明边的权重. 在现实的网络系统中，线路长度抑或是通过线路通讯的成本可能会导致不同的边拥有不同的权值. 在这样的情况下，我们可能会希望找到一个最小生成树来最小化广播的成本. 请注意, 尽管现实生活中边的权值可能相同，但是我们在算法讨论的时候经常性的让他们变成不重复的值(例如强行安排先后排序). 这样能在很多情况下方便我们解决各种问题(比如我们在比较大小的时候不需要再考虑相等情况，一些算法也有唯一解, 例如最小生成树是唯一的，方便我们讨论问题). 但是这并不意味着这类算法不适用于权值相等的情况.

复习一下常见的最小生成树算法Prim和Kruskal算法, Prim算法通过在未加入树的节点中选取最小边来构造生成树. 而Kruskal算法则是从最小的边开始，将连通两个不同的树的边加入生成树。

然而在分布式系统中，我们并不容易执行这样的算法，维护一个最小边的队列或者是未加入节点的队列在一般的系统中是一件简单的事情，然而在分布式系统中却伴随着巨大的开销. 因此在这里我们介绍一种Kruskal算法和Prim算法的结合体: Boruvka算法. 

Boruvka算法:

对于每一个连通块(一开始所有的节点都位于只有他自身的连通块内), 选择权最小的外向边将其加入连通树,并且将此连通块和外向边所连接的连通块结合成新的连通块. 这使得Boruvka算法是一种天然的分布式算法: 我们可以让每一个节点执行相同的代码，充分利用并行的优势.

然而在讨论Boruvka算法的性能之前，我们先来讨论一下具体的实现. 其中有两个比较值得注意的小细节. 第一个小细节是，我们如何去判断哪个边是外向边呢? 考虑我们的讨论的分布式模型中，节点并不知道网络的整体拓扑信息, 判断是否联通并不是一容易的事情. 然而有一个非常有效的解决方案：节点的id. 在大多数的分布式系统里面，节点或多或少都会有一个独特的id，例如ip地址或者机器的mac地址, 我们可以选取一个在当前连通块选取一个节点当作当前连通块的根, 在我们遍历外向边的时候就可以询问相邻节点，你的连通块的根是什么？

如果相邻节点返回的是相同的根，那么说明在一个连通块内，否则就是外向边.

其次我们想要考虑两个连通块组成一个大的连通块的时候的策略. 一个很显而易见的策略便是 使得其中一个连通块的根变成树的新根. 但是如何选择这个根呢？ 如果我们随机选择根的话 很容易导致较大的连通块需要多次更新. 一个很简单的策略就是选择id最小的那个根作为树的新根. 也许会有更加优秀的选择策略，但是只是会产生常数上的差别，在此不展开讨论.

接下来我们来分析同步系统下的消息和时间复杂度.

N：节点数, M:边数

消息复杂度:

每一轮执行至少有n/2个连通块消失，因此需要执行log_2(N)轮. 

每一轮每个连通块需要执行最小边查询M次同时执行广播N次来更新合并以后的根信息. 

因此我们的消息复杂度为log_2(N)(M+N)

时间复杂度.

最差情况同消息复杂度 考虑第一轮生成了一个N/2 尺寸的连通块 但是剩下连通块还是两两相连 需要执行log_2(N)轮. 消息复杂度为log_2(N)(M+N).

下一篇笔记我们将会讨论leader election问题. 选举问题

我们可以看到我们在分布式算法的学习中经常会希望一些根节点/主节点 起到一个"领导"的作用来帮助整个系统统筹问题, 所以下一篇笔记我们将会学习什么情况我们可以有效的采取这种思想，什么时候是不可能的，同时还有关于对称性的讨论.

标签： 时间复杂度 分布式系统 最小生成树