分布式复习纲要_南京大学分布式系统期末复习

第3章

向量推进时间

考试内容：向量时间的推进计算

1. 接收到消息，以最大值更新本地

2. 发生本地事件，增大1

NTP时间同步

求t + t'的最小值

求O

第4章 全局快照

LAI-Yang 算法

每个进程开始是白色的，记录快照时变成红色，进程变红时发送标记发送规则，促进其他进程也变红

红色进程发送红色消息，白色进程发送白色消息（本地状态记录前和记录后的信息被分为两类）

每个进程必须在收到第一个红色消息之前记录本地状态

每个白色进程记录它沿着每个通道发送和接受的白色消息

通道状态：$S{C}_{ij}=p_i在通道C_{ij}上发送的白色消息-p_j在通道C_{ij}上接受的的白色消息$

（表示在PAST发送，却还没接收到的消息）

第5章 基于洪泛的异步单一启动者生成树算法

三种消息的类型：QUERY, ACCEPT, REJECT

1. 初始化：对于每个节点
   1. 因为自己还没加入生成树中，所以还不知道父节点，因此， parent⟸⊥
   2. Children、Unrelated均为空
   3. 记录自己的所有邻居节点，准备发送消息
2. 如果自己是根节点，启动QUERY洪泛
3. 若收到来自节点J的QUERY:
   1. 假如本节点已经有parents（已经加入生成树），则向J发送REJECT
   2. 假如本节点没有parents，则把J当作parents，向j发送ACCEPT，并向所有的邻居（除了j）发送QUERY
   3. 若所有的邻居节点已经都加入生成树，则终止
4. 若收到ACCEPT消息时，增加一个孩子节点
5. 若收到REJECT消息时，增加一个无关节点，因为该节点已经从其它路径加入了生成树
6. 所有邻居节点处理完成时，算法终止

第6章 基本图算法

全源最短路算法：异步FLoyd-Warshall

理解：

不依赖于生成树的受限洪泛算法

最小权重生成树算法（同步）

第8章P2P中的查询算法

Chord法

参考

目标：P2P环境下的对象查找问题

主要思路：

• 每个存储在集群中的对象，都有一个经哈希生成的ID（如160位SHA1）
• 每个组成集群的服务节点，也有一个经哈希生成的ID
• 存储对象与服务节点共享一个哈希空间，因此，可以将存储对象放置在与其具有相近哈希值的服务节点上

所有的N都是服务集群中的服务节点。要存储对象的某个key K，在环中找到K的大致位置，顺时针往下的第一个N就是这个对象要存储的位置。这就实现了节点与对象具有相近哈希值。

如何寻找：遍历所有服务节点，找到那个key。复杂度为：O(N)

如何优化（右边的图）：

为每个节点设置一个路由表（finger），路由表中存储着本节点之后的后续节点（按2的指数间隔存储）。因此寻找某个key时，直接到finger表寻找即可。此时的复杂度为O(logN)

第9章

最大独立集MIS

定义

对于图(N, L)，存在一个节点子集$N^{\prime }$， $N^{\prime }\subset N$ ，使得任何在$N^{\prime }$中的两个顶点i和j，边$(i,j)\notin L$，则$N^{\prime }$被称为一个独立集

独立集为原集合的一个子集，该子集中任何两个顶点在原图中不相邻

如果一个子集$N^{\prime }$是独立集，且没有一个更大的独立集$N^{′′} $ ，使得$N^′⊂N{′′} $，则$N^′$被称为一个最大独立集

一个图中可能存在多个“最大独立集”，这些“最大独立集”中的顶点个数可能是不同的，但寻找顶点数最多的那个“最大独立集”是一个NP问题

算法思路：

采用贪心算法，每当一个节点纳入最大独立集中时，将其邻居节点从原图中删除，因为这些节点不会再纳入最大独立集

重复以上过程，直到图中的顶点要么纳入最大独立集，要么被删除

算法分析：

三种消息类型：
RANDOM(real random): 向其他节点发送的随机数。以随机数最小者作为优选者
SELECTED(int pid, bool indicator): 告诉其他节点自己是否被选为独立节点
ELIMINATED(int pid, bool indicator): 告诉其他节点自己是否要自我消灭
1
2
3
4

if 没有邻居节点
	设置自己为独立节点并退出
else
	生成一个随机数，包装成RANDOM信息发送给其他节点。
	
等待其他节点发来的RANDOM信息
if 自己的RANDOM数小于所有的邻居节点发来的RANDOM
	设置自己为独立节点
	发送SELECTED(self, true)给邻居节点
else
	发送SELECTED(self, false)给邻居节点 // 自己无望称为独立节点

等待其他节点发来的SELECTED信息
if 收到来自其他节点的SELECTED(j, true) // 表示可以自灭了
	向自己的所有邻居节点发送ELIMINATED(self, true)
	自灭
else
	发送ELIMINATED(self, false)给其他所有邻居

等待其他节点发来的ELIMINATED信息
if 收到来自某个节点的ELIMINATED(j, true)
	将该节点从Neighbor节点数组中删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第10章

Gossip协议的优势分析

1. 可扩展性
   1. gossip协议是可扩展的，一般仅需要O(log⁡N)轮就可以将信息传播到所有的节点，其中N代表节点的个数
   2. 每个节点仅发送固定数量的消息，并且与网络中节点数目无关
   3. 在数据传送的时候，节点无需等待消息的ack，允许消息传送失败，因为可以通过其他节点将消息传递给之前传送失败的节点
   4. 系统很容易扩展到数百万个进程
2. 容错性
   1. 网络中任何节点的重启或者宕机都不会影响gossip协议的运行
3. 健壮性
   1. gossip协议是去中心化的协议，集群中的所有节点都是对等的，任何节点出现问题都不会阻止其他节点继续发送消息，任何节点都可以随时加入或离开
4. 最终一致性
   1. Gossip协议实现信息指数级的快速传播，但不能应用于强一致性场景

第11章 因果依赖模型

例子：三副本机制

思路：

保证因果序的基本思路

• 每条消息M携带一个日志，该日志中记录了所有在因果关系上比M更早发送的消息
• 当M到达目的地时，先将自己缓存起来，检测携带的日志中在因果关系中先于M、且目的地也是本进程的消息是否到达
• 当所有先于M的消息都已经到达、且已经Deliver到进程后，将消息M也Deliver到进程

Raynal-Schiper-Toueg算法

消息发送：

• 发送消息，附带上SENT

• 更新SENT

接收过程：

• ST表示的是消息发送者J所知道的不同进程间的发送情况。

• 因此假如本进程所有$DELIV[X]$都大于等于$ST[X,i]$，那么表示j所知道的i的前置进程都已发送完成，因此它就可以deliver自己的信息给i

• 然后，更新本地的SENT和DELIV

第13章

基于生成树的终止检测算法

基本思想：

• 所有进程根据关联关系组成图，在图中生成一棵树

• 树根向叶子节点发送广播消息

• 收到广播消息的叶子节点一旦变为空闲，向父节点报告

• 每个内部节点收到所有子节点空闲报告、且自己也变为空闲后，向父节点报告

• 根节点收到所有子节点报告后，宣布程序终止

以上思想的漏洞：

一个内部节点已经向父节点报告空闲，但是，以其为根的子树上的某个节点收到了一个消息，节点状态因此有空闲变为活跃

改进方法：

通过给每个节点标记白色黑色来避免 某个节点报告之后的变化，因为假如收到黑色消息，会重新发起一轮广播

基于快照的终止检验算法

思路：

• 在一个程序的所有进程中，肯定存在一个特定的进程，它是最后一个结束的
• 由于每个进程都不具备全局信息，当一个进程由活跃变为空闲时，假定自己就是最后一个结束的那个进程，向其它进程发送消息，收集全局快照
• 收集全局快照过程中，如果遇到还没结束的进程，则宣布本次快照收集过程失败
• 最后一个结束的进程能够成功收集到程序终止的全局快照

代码：

解释：每个进程都有一个时钟X来互相判断自己是不是最后结束的。k则标明自己的进程号。

当本进程i活跃并向其他进程（假设为j）发送信息时，那么j就知道自己要比i 更晚结束，因此它的时钟在i的时钟上递增1

当本进程i将要休息时，它假定自己是最后一个进程并发出收集全局快照请求。假如本进程真的是最后的进程，那么它的时钟一定并其他进程大。

• 若快照请求遇到一个活跃的进程，那么本轮收集失败，本进程不是最后一个结束的。正在活跃的进程更替它的时钟为最大值（R4）
• 若发送请求遇到一个静止进程(假设为j)，并且j的时钟较大，那么这个快照请求被忽略，因此i不是最后结束的，没资格收集
• 若遇到一个静止进程，并且i的大，那么i的请求通过了j的考验，j继续帮i把请求传递下去