拥塞团模型中的代数算法研究

### 拥塞团模型中的代数算法研究 #### 1. 预备知识 - **符号表示**： - 用 \(n\) 表示网络中的节点数量，节点记为 \(1, 2, \cdots, n\)。 - \(F\) 表示一个有限域，其阶数由 \(n\) 的多项式上界限定，意味着每个域元素可用 \(O(\log n)\) 位编码，在拥塞团模型中可用一条消息发送。 - 对于正整数 \(p\)，\([p]\) 表示集合 \(\{1, 2, \cdots, p\}\)。对于 \(p \times p'\) 矩阵 \(A\)，其元素记为 \(A[i, j]\)，\(A[i, *]\) 表示第 \(i\) 行，\(A[*, j]\) 表示第 \(j\) 列。 - **图论问题**：在拥塞团模型中，主要解决的图论问题里，图的顶点数和网络节点数均为 \(n\)。输入时，每个节点 \(\ell \in [n]\) 初始拥有图邻接矩阵的第 \(\ell\) 行和第 \(\ell\) 列。Dolev 等人的引理表明，若消息源和目的地提前为所有节点所知，且每个节点作为源和目的地的消息数不超过 \(n\)，则一组消息可在两轮内传递。 - **代数问题**： | 问题名称 | 输入 | 输出 | | --- | --- | --- | | MM(n, m, k, F) | 矩阵 \(A_1, \cdots, A_k \in F^{n\times m}\) 和 \(B_1, \cdots, B_k \in F^{m\times n}\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A_1[\ell, *], \cdots, A_k[\ell, *]\) 和 \(B_1[*, \ell], \cdots, B_k[*, \ell]\)） | 矩阵 \(A_1B_1, \cdots, A_kB_k\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A_1B_1[\ell, *], \cdots, A_kB_k[\ell, *]\) 和 \(A_1B_1[*, \ell], \cdots, A_kB_k[*, \ell]\)） | | DET(n, F) | 矩阵 \(A \in F^{n\times n}\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A[\ell, *]\) 和 \(A[*, \ell]\)） | \(\det(A)\)（网络中每个节点都有 \(\det(A)\)） | | Rank(n, F) | 矩阵 \(A \in F^{n\times n}\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A[\ell, *]\) 和 \(A[*, \ell]\)） | \(\text{rank}(A)\)（网络中每个节点都有 \(\text{rank}(A)\)） | | INV(n, F) | 可逆矩阵 \(A \in F^{n\times n}\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A[\ell, *]\) 和 \(A[*, \ell]\)） | 矩阵 \(A^{-1}\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A^{-1}[\ell, *]\) 和 \(A^{-1}[*, \ell]\)） | | SYS(n, F) | 可逆矩阵 \(A \in F^{n\times n}\) 和向量 \(b \in F^{n\times 1}\) 分布在 \(n\) 个节点上（节点 \(\ell \in [n]\) 有 \(A[\ell, *], A[*, \ell]\) 和 \(b\)） | 向量 \(x \in F^{n\times 1}\) 使得 \(Ax = b\)（节点 \(\ell \in [n]\) 有 \(x[\ell]\)） | - **距离积**：设 \(m\) 和 \(n\) 为正整数，\(A\) 是 \(n \times m\) 矩阵，\(B\) 是 \(m\times n\) 矩阵，元素在 \(\mathbb{R} \cup \{\infty\}\) 中。\(A\) 和 \(B\) 的距离积 \(A*B\) 是 \(n\times n\) 矩阵 \(C\)，满足 \(C[i, j] = \min_{s\in [m]}\{A[i, s] + B[s, j]\}\)。我们主要关注矩阵元素为整数的情况，定义问题 DIST(n, m, M)，输入为元素在 \(\{-M, \cdots, -1, 0, 1, \cdots, M\} \cup \{\infty\}\) 的 \(n \times m\) 矩阵 \(A\) 和 \(m \times n\) 矩阵 \(B\)，输出为矩阵 \(C = A * B\) 分布在 \(n\) 个节点上。 - **矩阵乘法的集中式代数算法**：计算 \(n \times m\) 矩阵和 \(m \times n\) 矩阵在域 \(F\) 上的乘积的代数算法由三组系数 \(\{\alpha_{ij\mu}\}, \{\beta_{ij\mu}\}\) 和 \(\{\lambda_{ij\mu}\}\) 描述，使得 \(C[i, j] = \sum_{\mu=1}^{t} \lambda_{ij\mu}S^{(\mu)}T^{(\mu)}\)，其中 \(C = AB\)，\(S^{(\mu)} = \sum_{i=1}^{n} \sum_{j=1}^{m} \alpha_{ij\mu}A[i, j]\)，\(T^{(\m