迭代拜占庭向量共识与共享队列模型中的互斥算法

### 迭代拜占庭向量共识与共享队列模型中的互斥算法 在分布式计算领域，拜占庭向量共识（BVC）以及处理器间资源共享的互斥问题都是极为重要的研究方向。下面我们将深入探讨迭代拜占庭向量共识在不完全图中的相关内容，以及共享队列模型下的互斥算法。 #### 迭代拜占庭向量共识 ##### 1. 关键矩阵与状态表达 在不完全图的迭代拜占庭向量共识问题中，存在一个关键的 $(n - \psi)×(n - \psi)$ 行随机矩阵 $M[t]$。它具有这样的性质：存在一个简化图 $H[t]$ 以及一个仅依赖于图 $G(V, E)$ 的常数 $\beta$（$0 < \beta ≤1$），当 $j = i$ 或者边 $(j, i)$ 在 $H[t]$ 中时，$M_{ij}[t] ≥\beta$。这个矩阵 $M[t]$ 被称为转移矩阵。 对于任意无故障进程 $i$，在第 $t$ 次迭代结束时的状态 $v_i[t]$ 可以表示为：$v_i[t] = M_i[t] v[t - 1]$。这意味着无故障进程 $i$ 在第 $t$ 次迭代结束时的状态可以表示为仅无故障进程在第 $t - 1$ 次迭代结束时状态的凸组合。这里的向量 $v$ 仅包含无故障进程的状态。 ##### 2. Byz - Iter 算法的条件满足性 Byz - Iter 算法需要满足终止、有效性和 $\epsilon$ - 一致性条件。下面我们分别来看其证明过程。 - **有效性条件**： 通过对 $M[t + 1] (M[t]v[t - 1]) = (M[t + 1]M[t]) v[t - 1]$ 进行重复应用，对于 $t ≥1$，可以得到 $v[t] = (\Pi_{τ = 1}^{t}M[τ]) v[0]$。由于每个 $M[τ]$ 都是行随机矩阵，所以矩阵乘积 $\Pi_{τ = 1}^{t}M[τ]$ 也是行随机矩阵。这就表明每个无故障进程 $i$ 在第 $t$ 次迭代结束时的状态可以表示为无故障进程初始状态的凸组合，从而满足有效性条件。 - **终止条件**： Byz - Iter 算法在有限次数（$t_{end}$）的迭代后停止，其中 $t_{end}$ 是一个仅依赖于 $G(V, E)$、$U$、$\mu$ 和 $\epsilon$ 的常数。所以，该算法显然满足终止条件。后续会使用公式 (10) 来确定 $t_{end}$ 的合适值。 - **$\epsilon$ - 一致性条件**： 证明结构源于之前关于标量拜占庭共识的迭代算法正确性证明工作。首先定义了一些关键概念，如 $R_F$ 表示图 $G(V, E)$ 对应故障集 $F$ 的所有简化图的集合，$r = \max_{|F| ≤ f} |R_F|$，$r$ 仅依赖于 $G(V, E)$ 和 $f$ 且是有限的。 对于每个简化图 $H \in R_F$，定义了连通性矩阵 $H$。通过一系列引理，如引理 8 表明对于任意 $H \in R_F$ 和任意 $k ≥n - \psi$，矩阵乘积 $H^k$ 至少有一个非零列；引理 9 指出对于任意 $t ≥1$，存在一个简化图 $H[t] \in R_F$ 使得 $\beta H[t] ≤M[t]$；引理 10 说明矩阵乘积 $\Pi_{t = u}^{u + r(n - \psi) - 1} H[t]$ 至少有一个非零列。