集合一致性的意见数量研究

# 集合一致性的意见数量研究 ## 1. 集合一致性实例分析 在集合一致性问题中，存在一系列实例 \(s_1, s_2, \cdots, s_{min\{2k + 1, n\}}\)。对于 \(s_{2i + 1}\)，它不属于 \(L_{n,k}\)，因为在这种情况下，值 \(i + 1\) 被决定，但它并未被提议。而对于 \(s_{2i}\)，有 \(i\) 个值被决定，且每个值都是被提议过的。所以，当决定的值的数量小于等于 \(k\)（即 \(i \leq k\)）时，\(s_{2i} \in L_{n,k}\)。由此可知，递增序列 \(s_1, s_2, \cdots, s_{min\{2k + 1, n\}}\) 在合法和非法实例之间交替。因此，\(\#altern(L_{n,k}) \geq min\{2k + 1, n\}\)。 设 \(s_1 \subset \cdots \subset s_x\) 是一个递增实例序列，对于每个 \(i\)（\(1 \leq i < x\)），要么 \(s_i \in L_{n,k}\) 且 \(s_{i + 1} \notin L_{n,k}\)，要么 \(s_i \notin L_{n,k}\) 且 \(s_{i + 1} \in L_{n,k}\)。用 \(D(i)\) 表示在 \(s_i\) 中决定的值的集合的大小。若 \(s_i = \{(id_1, (a_1, b_1)), \cdots, (id_{\ell}, (a_{\ell}, b_{\ell}))\}\)，则 \(D(i) = |\{b_1, \cdots, b_{\ell}\}|\)，且 \(D(1) \geq 1\)。 当 \(s_i \in L_{n,k}\) 时，由于 \(s_i \subset s_{i + 1}\)，且在 \(s_i\) 中决定的值不超过 \(k\) 个且每个值都是有效的，所以在 \(s_{i + 1}\) 中会决定一个在 \(s_i\) 中未被决定的值，即 \(D(i) < D(i + 1)\)。 设 \(s_{x'}\) 是该序列中最大的合法实例，\(x' = x\) 或 \(x' = x - 1\)。一方面，\(D(x') \leq k\)；另一方面，因为在序列 \(s_1, \cdots, s_{x'}\) 中从合法实例到非法实例的交替次数至少为 \(\lfloor\frac{x' - 1}{2}\rfloor\) 且 \(D(1) \geq 1\)，所以 \(1 + \lfloor\frac{x' - 1}{2}\rfloor \leq D(x')\)。由此可得 \(x' \leq 2k\)，又因为 \(x \leq x' + 1\)，所以 \(x \leq 2k + 1\)。因此，任何递增且交替的实例序列的长度最多为 \(2k + 1\)，即 \(\#altern(L_{n,k}) \leq min\{2k + 1, n\}\)。 ## 2. 监测 \(k\) - 集合一致性 ### 2.1 意见数量与监测关系 研究表明，当 \(\#altern(L_{n,k}) < n\) 时，\(\#opinion(L_{n,k}) = \#altern(L_{n,k})\)；否则，\(\#opinion(L_{n,k}) = n + 1\)，即 \(\#opinion(L_{n,k}) = min\{2k, n\} + 1\)。 ### 2.2 监测方法 对于 \(k > \lceil\frac{n}{2}\rceil\) 的情况，\(min\{2k, n\} + 1 = n + 1\)，此时由 \((n, k)\) - 集合一致性诱导的语言 \(L_{n,k}\) 可以用一个通用监测器进行检查，该监测器最多使用 \(n + 1\) 个意见。 对于 \(k \leq \lceil\frac{n}{2}\rceil\) 的情况，我们提出一个监测器 \((M, \mu)\) 用于 \((n, k)\) - 集合一致性，它使用 \(2k + 1\) 个意见。意见集合为： \(U = \{red\} \cup \{(green, \ell) : 1 \leq \ell \leq k\} \cup \{(orange, \ell) : 1 \leq \ell \leq k\}\) 其大小 \(|U| = 2k + 1\)。划分 \((Y, N)\) 定义如下：对于任何值在 \(U\) 中的多重集 \(S\)，令 \(maxlevel(S) = max\{\ell : (green, \ell) \in S \vee (orange, \ell) \in S\}\)，则 \(S \in Y \Leftrightarrow (green, maxlevel(S)) \in S \wedge red \notin S\) 等价地，任何包含值 \(red\) 或对 \((orange, \ell)\) 且没有对 \((green, \ell')\)（\(\ell \leq \ell'\)）的多重集 \(S\) 属于“否”集合 \(N\)。 ### 2.3 意见生成器伪代码 每个进程 \(p_i\) 从输入 - 输出对 \((s_i, t_i)\) 开始，运行意见生成器协议并根据执行过程中看到的情况产生一个意见。意见生成器 \(M\) 在进程 \(i\) 输入为 \((i, (s_i, t_i))\) 时的伪代码如下： ```plaintext Opinion-maker M at process i with input (i, (si, ti)): R.update( i, (si, ti) ); r ← R.snapshot(); (s′, t′) ← ({(j, sj) : r[j] ̸= ⊥}, {(j, tj) : r[j] ̸= ⊥}); let val(s′) and val(t′) denote the set of values in s′ and t′ respectively; if |val(t′)| > k then decide red else if val(t′) ⊆ val(s′) then decide (green, |val(t′)|) else decide (orange, |val(t′)|) ``` ### 2.4 监测器正确性证明 设 \(V\) 表示 \((n, k)\) - 集合一致性任务的可能输入值集合。考虑意见生成器的一次执行 \(e\)，输入集为 \(\{(id_1, (s_1, t_1)), \cdots, (id_{\ell}, (s_{\ell}, t_{\ell}))\}\)，其中 \((s_i, t_i) \in V \times V\)。假设每个参与进程都做出决定，令 \(S\) 表示在这次执行中决定的意见的多重集，同时令 \(s = \{(id_1, s_1), \cdots, (id_{\ell}, s_{\ell})\}\) 和 \(t = \{(id_1, t_1), \cdots, (id_{\ell}, t_{\ell})\}\)。 - **情况一：进程决定 \(red\)** 若进程 \(p_i\) 看到的输出集 \(t'\) 中决定的值超过 \(k\) 个，则决定 \(red\)。即使 \(i\) 只有部分输入视图（即 \((s', t') \subset (s, t)\)），由于 \(t'\) 中决定的每个值也在 \(t\) 中决定，所以在 \((s, t)\) 中缺乏一致性的问题无法解决，即 \(t \notin \Delta(s)\)，因此 \(S \in N\) 是正确的。 - **情况二：没有进程决定 \(red\)** 设 \(p_i\) 是最后一个将其输入 \((s_i, t_i)\) 写入共享内存的进程。那么 \(p_i\) 观察到完整的输入 \((s, t)\)，设 \(d\) 是 \(t\) 中决定的值的数量，因为没有进程决定 \(red\)，所以 \(d \leq k\)。 - **若 \(t \in \Delta(s)\)**：由于 \(p_i\) 看到完整的输出，它决定 \((green, d)\)。在每个部分输入 \((s', t') \subseteq (s, t)\) 中，决定的值的数量最多为 \(d\)，所以每个看到部分输入的进程决定 \((green, d')\) 或 \((orange, d')\)（\(d' \leq d\)）。因此，\(maxlevel(S) = d\)，从而 \(S \in Y\)。 - **若 \(t \notin \Delta(s)\)**：因为没有进程决定 \(red\)，\(t\) 中决定的值的数量最多为 \(k\)。由于 \(t \notin \Delta(s)\)，至少有一个决定的值是无效的，即存在一个值 \(u \in val(t)\) 不包含在 \(val(s)\) 中，所以 \(p_i\) 决定 \((orange, d)\)。假设存在一个进程 \(p_j\) 决定 \((green, \ell)\) 且 \(\ell \geq d\)，但这会导致矛盾，因为这意味着 \(p_i\) 应该决定 \((green, d)\)。所以，对于每个 \((green, \ell) \in S\)，\(\ell < d\)，从而 \(S \in N\)。 综上所述，\((n, k)\) - 集合一致性有一个使用 \(min\{2k, n\} + 1\) 个意见的监测器，即 \(\#opinion(L_{n,k}) \leq min\{2k, n\} + 1\)。 ## 3. 拓扑学基础概念 ### 3.1 复形相关定义 - **复形**：复形 \(K\) 是顶点集 \(V(K)\) 和 \(V(K)\) 的有限非空子集族（称为单纯形）的集合，满足：若 \(v \in V(K)\)，则 \(\{v\}\) 是单纯形；若 \(s\) 是单纯形，则 \(s\) 的每个非空子集也是单纯形。单纯形 \(s\) 的维度是 \(|s| - 1\)，复形 \