分布式系统中的波与传输算法

众所周知，分布式系统是一种由多个进程组成的系统，这些进程为了完成某项任务而相互之间进行通信。在Wave算法中，消息的交换以及决策的制定都取决于每个进程中发生的事件所涉及的消息数量。由于需要在连接的网络中进行通信，因此Wave算法在许多领域都有应用。分布式数据库无线网络等。

符号/表示法

• 在过程中进行的计算，用符号 ICI 来表示。
• 在计算过程中，过程(p)的任何子集都可以表示为C。p.
• 所有过程的集合被表示为P’。
• E.所拥有的频道列表。
• 该进程开始运行的节点被称为“启动器”或“起始点”。
• 在网络中，任何不是发起者的节点都被称为“跟随者”。
• “发起者所做的事情，就是发送一个事件。”
• 非发起者所引发的事件已经发生了。

波状算法

这些消息传递机制被称为“波式算法”，因为它们采用异步消息传递方式，不需要全局时钟或时间同步机制。

波状算法会交换有限数量的信息，然后根据每个过程中发生的某个事件来做出决策。

满足这三个要求的算法，被视作分布式算法中的“波状算法”。

• 终止/结束：每一次计算都是有限的。
  • ∀C : lC| < ∞
• 决定：每次计算过程中，至少会有一个决策步骤。
  • ∀C: 存在至少一个元素 e，属于集合 C，且 e 是一个决定性的事件。
• 依赖性：在每次计算中，每一个被决定的事件之前，都会有一个与该事件相关的事件发生。
  • ∀C: 对于C中的每一个元素e来说，如果e是一个可决定的事件，那么对于P’中的每一个元素q，都存在一个属于C中的元素f，使得q可以被f所决定。qf ≥ e)。

波算法从一个特定的节点开始，然后该波会传播到其相邻的节点，而相邻的节点又会继续将其波传播到更远的节点。当没有更多的节点需要接收这个波时，波就会停止传播。

Wave算法的优势在于其异步通信机制，在这种机制下，随机事件与消息之间的关联具有等价性。在Wave算法中，消息链的存在对于计算因果关系来说是必要的。不同版本的Wave算法可以在以下特性方面有所不同：

• 中央集权：如果算法中有且仅有一个发起者，那么这些算法的性质就会有所不同。
  • 如果一个算法在每次计算过程中都恰好只有一个发起者，那么这种算法被称为集中式算法。
  • 如果这种算法能够由那些被称为“去中心化”的进程的任意子集来自动启动的话，那么就可以实现该算法了。
• 初步了解：如果算法在处理的过程中拥有初始信息的话，那么这些算法之间就会有所不同。
  • 每个进程都有其独特的名称。
  • 邻居身份：每个进程都知道其邻居的姓名。
• 复杂性：该算法的复杂性需要考虑各种因素。
  • 交换的消息数量
  • 交换的位数，
  • 进行一次计算所需的时间。
• 拓扑学可以针对特定的拓扑结构来设计算法，比如环型结构、树状结构、团结构等。
• 决策的数量通常情况下，每个流程都会做出一个决策。在某些算法中，可能只有某个流程会执行决策操作；而在另一些算法中，则所有流程都会参与决策过程。而树形算法则会在恰好两个流程中做出决策。

波的特性：

• 在每次计算过程中，都会有一个由发起者发起的事件发生。
• 这是一种适用于任意网络的波束成形算法，无需事先知道邻居节点的身份信息。该算法在每次计算中至少会交换 lEI 条消息。

由于数据包的传播是通过节点网络来完成的，因此我们可以将其视为一种部分序关系。

现在，让我们考虑一个二元关系≤。*由 x ≤ 得出*y ⇐⇒ (x * y) = x。也就是说，在关系≤*中，X上存在着偏序关系。这意味着该关系是传递的、反对称的，并且是自反的。

• 传递性我们知道，如果x≤y且y≤z，那么x≤z。现在假设x≤。*y 且 y ≤*根据≤的定义，z；*(x * y) = x，且 (y * z) = y。根据这些性质以及结合律，我们可以得到：(x * z) = (x * y) * z = x * (y * z) = x * y = x。也就是说，x ≤* z.
• 反对称性假设 x ≤*y 且 y ≤*x；根据≤的定义*x * y = x，且 y * x = y。利用这些性质以及交换律，我们可以得出 x = y。
• 反射性x * x = x，即 x ≤ x。*x的反射性质可以通过幂等性来证明。

由于该算法满足所有三个性质，因此我们可以认为波算法可以被视为一种偏序关系。

不同波算法

• 环形算法
• 投票算法
• 树形算法
• Echo算法
• 阶段算法
• 芬恩的算法

环形算法

用于传播该过程的通道被选择为能够形成哈密顿回路（即遍历了所有的节点）。换句话说，过程p及其相邻状态（Next）就是这样被处理的。p这样的选择方式下，所选出的通道会构成一个哈密顿回路（即所有节点都恰好被遍历一次）。

• 它只有一个启动器。
• 每个节点都会将消息继续传递给下一个节点。
• Ring算法是一种集中式算法。
• 发起者就是那个具有决定权的节点。

对于发起者来说…
开始
发送（tok）到下一个步骤/环节p;
接收（令牌）；
决定；
结束

非启动器专用的Ring算法
开始
接收（令牌）
将“tok”发送到Nextp。
结束

投票算法

该算法会发送一个信号，这个信号会传播到所有节点上，然后再返回给发起信号的节点。当这个信号逐渐消失后，算法就会停止运行。

• 它运行在一个群集网络上。
• 它只有一个启动器。
• 投票算法是集中式的。
• 发起者就是那个具有决定权的节点。

在投票算法中，发起者会向每个邻居发送消息，然后在所有收到的消息都收到之后再进行决策。

用于Initiator的投票算法
var recp整数初始化为0；
开始
对于所有的q值来说，都是如此。p
请将其发送到 qf 那里。
而rec则不同。p<# 嘶嘶声/低吼声 >p do
开始
接收(tok);
记录/保存p:= 递归p +1；
结束
决定/选择
结束
// 这里，recp被用作计数变量。