匿名动态网络中的有意识和无意识计数算法解析

### 匿名动态网络中的有意识和无意识计数算法解析 #### 1. 背景与问题定义 在匿名动态网络中，存在一种强大的对手，它生成的图实例 $G(r) = (V, E(r))$ 中，每个节点 $v_i$ 的邻居数量总是被一个常数上界 $D$ 所限制，即 $\forall v_i \in V, \forall r \in N, |N_{v_i}(r)| \leq D$，我们称这种对手为有界度动态图对手。 计数问题可以通过以下两个性质来形式化： - **收敛性**：存在一轮 $r$，在此之后至少有一个进程 $p$ 对网络大小有永久正确的猜测，即 $g = |V|$。 - **意识性**：如果节点 $v$ 对 $|V|$ 有正确的猜测 $g$，那么存在一轮 $r'$（$r' \geq r$），使得 $v$ 意识到该猜测的正确性。 对于一个计数算法 $A$，如果它能同时满足这两个性质，我们称它为有意识的；如果只满足收敛性，我们称它为无意识的。 #### 2. 有意识计数算法 AD 算法 $AD$ 是一个分布式算法，它假设存在一个初始状态不同的领导节点，并且其他所有节点执行相同的程序。此外，所有进程都知道节点度的上界 $D$。 算法 $AD$ 由领导者执行一系列迭代 $i = 0 \cdots \ell$，每个迭代需要若干轮。每个迭代 $i$ 开始时考虑两个参数：节点度的上界 $D$ 和网络大小的上界 $K_i$，然后算法计算网络大小的猜测。如果猜测与当前考虑的上界 $K_i$ 匹配，则算法终止，$K_i$ 即为网络大小 $|V|$；否则，开始迭代 $i + 1$，输入为 $D$ 和 $K_{i+1} = K_i - 1$。 算法 $AD$ 利用能量转移的思想，并利用网络中全局存储能量的不变性：在算法执行期间，每轮结束时每个节点存储的能量总和保持不变。这里的能量并非节点实际拥有的能量，而是用于解释算法细节的抽象概念。 ##### 2.1 算法步骤 - **步骤 1**：算法以 $D$ 为输入，通过运行一个估计算法（如文献 [16] 中的算法）计算网络大小的上界 $K$。 - **步骤 2**：领导者和匿名节点在第 $r_{start}$ 轮开始步骤 2。 - **领导者**：维护以下局部变量： - $e_{v_l} \leftarrow 1$：表示初始能量电荷。 - $rcv_{v_l} \leftarrow \varnothing$：用于存储每轮收到的所有消息。 - $i \leftarrow 0$：迭代次数。 - $K_i \leftarrow K$：第 $i$ 次迭代时网络大小的上界。 - $r_{init_i} \leftarrow r_{start}$：第 $i$ 次迭代的开始轮。 - $r_{final_i}$：第 $i$ 次迭代的终止轮，领导者将在此时验证猜测是否正确。 领导者在第 $r_{init_i}$ 轮开始迭代 $i$，以 $D$ 和 $K_i$ 为输入，计算满足 $K_i - (1 - (\frac{B - 1}{B})^R)K_i < 1$ 的最小 $R \in N^+$（其中 $B = (2D)^K$），并设置 $r_{final_i} \leftarrow r_{init_i} + RK_i$。 对于每一轮 $r$： - **发送阶段**：在每轮开始时，领导者广播一个 $ENERGY RELEASE(0)$ 消息，不释放能量。 - **接收和计算阶段**：将 $ENERGY RELEASE(e')$ 消息存储在 $rcv_{v_l}$ 变量中。在轮结束时，当所有消息都收到后，领导者更新其局部能量电荷：$e_{v_l} \leftarrow e_{v_l} + \sum_{e' \in rcv_{v_l}} e'$。 - **终止条件**：当 $r = r_{final_i}$ 时，如果 $K_i - e_{v_l} < 1$，则领导者终止并广播 $STOP(K_i)$ 消息 $K_i$ 轮，然后输出 $count \leftarrow K_i$；否则，领导者向其他节点发送 $RE - START(r_{final_i} + K_i)$ 消息，宣布将开始新的迭代。 - **匿名节点**：每个非领导节点 $v_i$ 维护以下局部变量： - $e_{v_i} \leftarrow 1$：表示初始能量电荷。 - $rcv_{v_i} \leftarrow \varnothing$：用于存储每轮收到的所有消息。 对于每一轮 $r$：