波与遍历算法详解

### 波与遍历算法详解 #### 1. 下确界函数与相关算法性质 在分布式系统的算法设计中，下确界函数有着重要的应用。若 * 是集合 X 上的二元运算符，且满足以下三个条件： - 交换律：a * b = b * a； - 结合律：(a * b) * c = a * (b * c)； - 幂等律：a * a = a。 那么在集合 X 上存在一个偏序 ≤，使得 * 成为下确界函数。满足这些条件的运算符包括逻辑与或、整数的最小值或最大值、整数的最大公约数或最小公倍数，以及集合的交集或并集等。由此可得推论，对于进程本地值的逻辑与（∧）、逻辑或（∨）、最小值（min）、最大值（max）、最大公约数（gcd）、最小公倍数（km）、交集（∩）和并集（∪），都可以在单个波中进行计算。 构建的 INF 算法与算法 A 具有相同的性质，除了位复杂度，因为在算法 A 的每个消息中都附加了集合 X 的一个元素。 #### 2. 环形网络算法 环形网络算法是一种适用于环形网络的波算法，同样也可用于编码了固定哈密顿环的哈密顿网络。假设每个进程 p 都有一个指定的邻居 Nextp，所有这样选择的通道构成一个哈密顿环。该算法是集中式的，具体如下： - **发起者**： ```plaintext begin send ( tok ) to Nextp ; receive ( tok ) ; decide end ``` - **非发起者**： ```plaintext begin receive ( tok ) ; send ( tok ) to Nextp end ``` 该算法的正确性证明如下：设发起者为 P0，由于每个进程最多发送一条消息，所以算法总共最多交换 N 条消息。在有限步骤内，算法会达到一个终止配置。在这个配置中，P0 已经发送了令牌，且没有（tok）消息在任何通道中传输，除 P0 外没有进程“持有”令牌。由此可推出每个进程都发送并接收了令牌，P0 接收令牌后执行了决策语句，且每个非 P0 进程的接收和发送（tok）操作都先于 P0 的接收操作，满足依赖条件。 #### 3. 树形网络算法 树形网络算法适用于树形网络，若能获取任意网络的生成树，也可使用该算法。假设树的所有叶子节点发起算法，每个进程在算法中恰好发送一条消息。当一个进程通过除一条通道外的所有相邻通道接收到消息时，它会通过剩余的通道发送消息；当一个进程通过所有相邻通道接收到消息时，它会进行决策。算法代码如下： ```plaintext var recp[q] for each q E Neighp : boolean init false ; (* recp[q] is true if p has received a message from q *) begin while #{ q : recp[q] is false} > 1 do begin receive ( tok ) from q ; recp[q] := true end ; (* Now there is one qo with recp[qo] is false *) send ( tok ) to qo with recp[qo] is false ; x : receive ( tok ) from qo ; recp[qo] := true ; decide (* Inform other processes of decision: forall q E Neighp, q -=I- qo do send ( tok ) to q *) end ``` 为证明该算法是波算法，引入了一些符号。设 fpq 是进程 p 向 q 发送消息的事件，gpq 是进程 q 从 p 接收消息的事件，Tpq 表示不穿过边 pq 可从 p 到达的进程子集。算法使用最多 N 条消息，在有限步骤内会达到终止配置 γ。通过分析 rec 位的状态，可证明在 γ 中至少有一个进程执行了决策事件。并且可以通过归纳法证明，每个决策事件都先于每个进程中的一个事件。 #### 4. 回声算法 回声算法是一种适用于任意拓扑网络的集中式波算法。该算法由 Chang 首次提出，Segall 给出了更高效的版本。算法通过向所有进程泛洪（tok）消息来定义一个生成树，令牌沿着树的边“回声”返回，类似于树形算法中的消息流。具体算法如下： - **发起者**： ```plaintext var recp : integer init 0 ; (* for initiator only *) begin forall q E Neighp do send ( tok ) to q ; while recp < #Neighp do begin receive ( tok ) ; recp := recp + 1 end ; decide end ``` - **非发起者**： ```plaintext begin receive ( tok ) from neighbor q ; father p := q ; recp := recp + 1 ; forall q E Neighp, q =1= father p do send ( tok ) to q ; while recp < #Neighp do begin receive ( tok ) ; recp := recp + 1 end ; send ( tok ) to father p end ``` 该算法的正确性证明如下：每个进程通过每个相邻通道最多发送一条消息，所以每次计算中交换的消息数量是有限的。在终止配置 γ 中，定义一个图 T = (lP, ET)，其中 pq ∈ ET 当且仅当 fatherp = q。可以证明该图是一棵树，且每个进程都发送了消息。通过归纳法可以证明，每个非发起者都会向其父节点发送消息，发起者会接收所有邻居的消息并执行决策，且决策事件先于每个进程中的一个事件。 #### 5. 轮询算法 在完全图网络中，每个进程对之间都存在通道，进程在接收到每个邻居的消息后可以进行决策。轮询算法中，发起者向每个邻居请求回复消息，在收到所有消息后进行决策。具体如下： - **发起者**： ```plaintext var recp : integer init 0 ; begin forall q E Neighp do send ( tok ) to q ; while recp < #Neighp do begin receive ( tok ) ; recp := rec ```