一类随机扩散过程的收敛速度问题

2020-07-27 本文已影响0人 LostAbaddon

我们假定网络上总共有 N 个节点，每个节点有 n 个邻点，且每个节点可以在 G 个策略中做出选择。

下面，考虑这样一个过程：

每个节点询问自己的邻点中最多 k 个，得到它们的决策选择（1~G的自然数），加上自己的决策，构成每个节点自己的决策集，所以这个决策集总共最多有 k+1 个元素。接着，每个节点在自己的决策集中选择出现次数最多的决策，作为自己的新决策；如果有多个决策出现的次数一样多，那如果其中包含节点自身原来的决策，则继续保持该决策，否则在这多个决策中随机选择。

这样的一次决策过程，称为一次决策调整，而将每个节点选择的决策称为决策构型。

如果决策构型是全同的，即所有节点选择的决策都是相同的，则称此决策构型是决策一致的；而如果连续 p 次决策调整所得到的构型都是相同的，则称此构型是决策均衡的——为什么要连续 p 次？因为按照定义，每个节点可能不是询问自己所有的邻点，所以有可能出现连续多次决策调整每个节点的决策都不变，但下一次决策调整后出现节点的决策发生改变的情况。

一致和均衡的决策被称为决策收敛。

于是，就存在这样一组问题：

什么样的初始构型可以得到决策一致的结果？
是否所有初始构型都能达到决策收敛？
如果一个构型最终收敛，则需要经过多少次决策调整？

上面还只是一个简单模型，我们可以将模型做得更加复杂一点，引入拜占庭节点：拜占庭节点在每次决策调整的时候，永远返回一个特殊的决策，该决策被称为污染决策。此时，这个模型中的所谓决策构型，指的是所有非拜占庭节点的决策构成的有序集合。我们可以将初始构型中最高票的决策称为目标决策，且污染决策和目标决策是不相同的。最后，我们将收敛的决策中最高票的决策称为最终决策。那么，如果一个初始构型最终是收敛的，那就存在三种可能：

决策收敛于目标决策，此时称为正常收敛；
决策收敛于污染决策，此时称为污染收敛；
决策收敛于目标决策与污染决策之外的第三个决策，此时称为异常收敛。

我们下面就可以问这样的问题：

初始构型满足什么条件、拜占庭节点占多少时，决策最终会收敛且是正常收敛？

我们下面就来讨论一些这些问题。

我们先考虑一个近似模型，即所谓的平均场模型。

在这个模型中，每个节点的地位是相同的，且可以认为每个节点和全网都是相连的。

我们用 $\{ g_i \}$ 来表示决策构型，它有一个对偶表示： $\{ n_g \}$ ，表示决策代号为 g 的节点的数量。下面，我们用 $Q \left( \{ n_g \}; k; g \right)$ 表示对偶构型为 $\{ n_g \}$ 时，从中选择 k 个节点，其中最多票决策为 g 的概率。

因此，我们可以得到决策构型的近似动力学方程：

$n(t + 1)_g = N Q \left( \{ n(t)_g \}; k; g \right)\\$

因此，要得到平均场模型下的决策构型演化，我们就需要能计算出 $Q \left( \{ n_g \}; k; g \right)$ 。我们用 $P(\{ n_g \}; N, g)$ 表示所有对偶构型的总和为 N、每个决策的票数不高于初始构型 $n_g$ 且最高票决策为 g 的所有对偶构型构成的集合，则上述概率可以计算出：

$Q \left( \{ n_g \}; k; g \right) = \sum_{p \in P(\{ n_g \}; k, g)} q \left( \{ n_g \}, p \right)\\$

其中 $q \left( \{ n_g \}, p \right)$ 是从构型 $\{n_g\}$ 中选择 k 个节点得到构型 $\{p_g\}$ 的概率，其表达为：

$q \left( \{ n_g \}, p \right) = \frac{1}{\Lambda \left( N, k \right) \Omega (p)} \prod_{i = 1}^G \Lambda (n_i, p_i)\\$

其中 $\Lambda (n, k) = \frac{\Gamma (n + 1)}{\Gamma (k + 1) \Gamma (n - k + 1)}$ 为组合数函数，而 $\Omega (p)$ 是构型 p 中最大值相同的决策的数量，为对称因子函数。

即便如此，这个计算依然非常复杂，所以我们先来看只有两种决策时的情况：

$q \left( \{ n_1, n_2 \}, p \right) = \frac{\Lambda \left( n_1, p \right) \Lambda \left( n_2, k - p \right)}{\Lambda \left( n_1 + n_2, k \right) \Omega (p, k - p)}\\$

其中：

$\Omega (x, k-x) = \frac{2 - \delta(k - 2 x)}{2}\\$

为 2 决策情况下的对称因子函数。

我们下面可以只计算 g=1 的情况，因为显然将两个构型数互换就是 g=2 的情况了。

容易知道，g=1 的决策数的上下限分别是：

$k_{min} = \max \left( \frac{k}{2}, k - n_2 \right);\ \ \ \ k_{max} = \min \left( k, n_1 \right)\\$

由此可得：

$Q (k) = Q \left( \{ n_1, n_2 \}; k; 1 \right) = \int_{k_{min}}^{k_{max}} \frac{\Lambda \left( n_1, x \right) \Lambda \left( n2, k - x \right)}{\Lambda \left( n_1 + n_2, k \right) \Omega (x, k - x)} d x\phantom{wwwwwwwwwwwwwwwwwwww}\\ \approx \frac{e^2 (n_1 + 1)^{n_1 + \frac{1}{2}} (n_2 + 1)^{n_2 + \frac{1}{2}}}{2 \pi \Lambda \left( n_1, n_2 \right) \Omega (x, k - x)} \phantom{wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwa}\\ \times \int_{k_{min}}^{k_{max}} \frac{1}{(x + 1)^{x + \frac{1}{2}} (n_2 - k + x + 1)^{n_2 - k + x + \frac{1}{2}} (n_1 - x + 1)^{n_1 - x + \frac{1}{2}} (k - x + 1)^{k - x + \frac{1}{2}}} d x$

被积函数有一个极点，该极点的位置在 $\frac{(n_1 + 1) k - (n_2 + 1)}{n_1 + n_2 + 2}$ 到 $\frac{(n_1 + 1) k + (n_1 + 1)}{n_1 + n_2 + 2}$ 之间，我们可以取极点为 $x_0 \approx \frac{(n_1 + 1) k}{n_1 + n_2 + 2}$ ，由此可以用 $\beta$ 分布构造一个（第一行的）被积函数的拟合：

$\beta(a, b; x) = x^a (1 - x)^b\phantom{wwwwwwwwwwwwwwww}\\ q({n_i}, k, x) \approx K \beta \left( \frac{(n_1 + 1) k}{n_1 + n_2 - k}, \frac{(n_2 + 1) k}{n_1 + n_2 - k}; \frac{x}{k} \right)\\ K = \frac{\Lambda \left( n_1, \frac{(n_1 + 1)k}{n_1 + n_2 + 2} \right) \Lambda \left( n_2, \frac{(n_2 + 1)k}{n_1 + n_2 + 2} \right)}{\Lambda (n_1 + n_2, k) \beta \left( \frac{(n_1 + 1) k}{n_1 + n_2 - k}, \frac{(n_2 + 1) k}{n_1 + n_2 - k}; \frac{n_1 + 1}{n_1 + n_2 + 2} \right)}$

当然，这个拟合函数和实际的概率函数之间肯定存在一定的误差，所以我们最终构造出来的概率函数应该是这样的：

$Q(n_1, n_2; k) \approx \frac{\beta \left( \frac{n_1 k}{n_1 + n_2}, \frac{n_2 k}{n_1 + n_2}; \frac{k_{min}}{k}, \frac{k_{max}}{k} \right)}{\beta \left( \frac{n_1 k}{n_1 + n_2}, \frac{n_2 k}{n_1 + n_2}; 0, 1 \right)}\\$

也即，它基本上就是一个 Beta 分布的累积分布函数。事实上，我们甚至可以很直观底将其推广到多决策得情况：

$Q(\{ n_i \}; k, g) \approx C \int ... \int \prod_i \left( \frac{x_i}{k} \right)^{\frac{n_i k}{N}} dx_1 ... dx_G\\$

积分范围是满足 $\sum_i x_i = k$ 且 $\min (x_g, n_i) \ge x_i \ge 0$ 的曲面，比例系数满足：

$\sum_g Q(\{ n_i \}; k, g) = 1\\$

但，这个结果虽然看上去很简洁，但实际上要计算依然很麻烦。所以我们依然需要进一步做简化近似：

$\begin{cases} Q \left( n_1 \le \frac{N}{2}; k \right) \approx \frac{1}{2} \exp \left[ k^{\frac{3}{4}} \left( \frac{n_1}{N} - \frac{1}{2} \right) \right]\\ Q \left( n_1 \ge \frac{N}{2}; k \right) \approx 1 - \frac{1}{2} \exp \left[ k^{\frac{3}{4}} \left( \frac{1}{2} - \frac{n_1}{N} \right) \right] \end{cases}\\$

它可以很方便底外推到 G 个决策的形式：

$q \left( n_a, n_b; k \right) \approx \mathrm{step} (n_a - n_b) + \frac{1 - 2 \mathrm{step} (n_a - n_b)}{2} \exp \left[ - k^{\frac{3}{4}} \left| \frac{n_a - n_b}{n_a + n_b} \right| \right]\\ Q \left( \{ n_i \}; k, g \right) \approx \frac{1}{N} \left\{ \sum_{j \neq i} \left[ (n_i + n_j) q \left( n_i, n_j; \frac{n_i + n_j}{N} k \right) \right] - (G - 2) n_i \right\}$

其中 step 是三值阶跃函数：

$\begin{cases} \mathrm{step} (x < 0) = 0\\ \mathrm{step} (0) = \frac{1}{2}\\ \mathrm{step} (x > 0) = 1 \end{cases}\\$

对每一项 q 来说，我们可以认为它反映了在两个决策之间的节点再分配情况，而且显然原本选择节点多的决策会指数级增多，而少的决策的选择节点则会指数级减少，因此最多选择的决策增长的速度最快，最少选择的决策消失的速度也最快。

我们下面着重研究最多和次多决策之间的“竞争”。

不失一般性，我们取 1 号决策为最多选择决策，2 号决策为次多选择决策。这样两者之差满足：

$d(t) = n_1 (t) - n_2(t)\\ d' \approx \sum_{i \neq 1, 2} \left[ (n_1 + n_i) q \left( n_1, n_i; \frac{n_1 + n_i}{N} k \right) - (n_1 + n_i - d) q \left( n_1 - d, n_i; \frac{n_1 + n_i - d}{N} k \right) \right]\phantom{wwwww}\\ \ + (2 n_1 - d) q \left( n_1, n_1 - d; \frac{2 n_1 - d}{N} k \right) - (2 n_1 - d) q \left( n_1 - d, n_1; \frac{2 n_1 - d}{N} k \right)\phantom{wwwwwwa}\\ \ - (G - 2) d\phantom{wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwi}\\ \approx d \left\{ \left( \frac{2 n_1 k}{N} \right)^{\frac{3}{4}} + \frac{1}{8} \sum_{i \neq 1, 2} \left[ \frac{3 n_1 + 5 n_i}{n_1 + n_i} \left( \frac{n_1 + n_i}{N} k \right)^{\frac{3}{4}} - 4 \right] \exp \left[ - \left( \frac{n_1 + n_i}{N} k \right)^{\frac{3}{4}} \frac{n_1 - n_i}{n_1 + n_i} \right] \right\}\\$

当其它决策的选择节点很少甚至没有（即只有两个决策可供选择）的时候，上面的结果还可以简化为：

$d' \approx d \left( \frac{2 n_1 k}{N} \right)^{\frac{3}{4}}\\$

显然，只要 $k \ge \frac{2}{G}$ ，那最大与次大之间的差距就会以比指数更快的速度拉大（别忘了 $n_1$ 也在高速增长）。

对于 G = 2 的情况，可以得到选最高票决策的节点数岁轮次的近似关系：

$C_k = k^{\frac{3}{4}} - 1\phantom{wwwwwwwwwwwwwwwwwwwwwwa}\\ W(k; t) = 2 Q(k; t) - 1\phantom{wwwwwwwwwwwwwwwww}\\ \ln W - C_k^{-1} \sum_{i = 2}^\infty \frac{1}{i! (i - 1)} (- W)^{i - 1} k^{\frac{3}{4}i} \approx C_k (t - t_0)\\ \therefore t \approx \frac{1}{C_k} \ln \frac{2 n - N}{2 n_0 - N} + \frac{2 (n - n_0)}{N^2 C_k^2} \left\{ [N - (n + n_0) (C_k - 1)] \exp \left( k^{\frac{3}{4}} \right) - (n + n_0) (C_k + 3) - N (C_k + 2) \right\}\\$

这个近似与平均场模型的整体趋势符合得较好，而且很显然当 $n_0 = \frac{N}{2}$ 时系统无法达成一致，而当 $n_0 < \frac{N}{2}$ 时系统就算达成一致也不能是目标决策。这些都和我们的分析一致。

事实上，这里得到的近似在 $n \approx \frac{N}{2}$ 时增长速度比实际平均场的情况要快，但在 $n \approx N$ 时增长速度却比实际平均场的情况要慢，所以最终求得的达到决策一致的轮次比实际情况要略多一点。

因此我们可以认为这是一个可以用于定性甚至半定量分析的足够可靠的近似。

由于次高决策的选择节点数如果少于 $\frac{k}{G}$ 则必然全网在下一轮决策调整时会达成决策一致，所以我们可以估算出系统达到决策收敛所需的轮次数：

$T \approx \frac{1}{C_k} \ln \frac{N}{2 n_0 - N} - \frac{2 (N - n_0)}{N^2 C_k^2} \left\{ [N (C_k - 2) + n_0 (C_k - 1)] \exp \left( k^{\frac{3}{4}} \right) + n_0 (C_k + 3) + N (2 C_k + 5) \right\}\\$

进一步，最高票决策在初始状态必须占全网多数，在两决策情况下最小不能小于 $\frac{N}{2}$ ，而查询节点数量 k 至少为 2，所以我们可以得到对于任意决策网络的最大决策一致所需轮数为：

$T_M \approx 1.467 \ln N - 0.567\\$

也即，在两决策的网络中，只要最高票决策的票数超过半数，那网络必然可以达成决策一致，且所需轮数与网络节点数的对数成正比。

实际情况中（不考虑平均场近似而考虑实际的网络中的真实决策过程），要达成决策一致的时间小于上述理论上的极限值，但当初始最高票决策的票数并不明显占多的情况下，网络可能最终会选出非初始最高票为最终决策。

比如，在 15000 个节点在两个决策中做选择的情况下，k 取 2，初始状态下最高票占 52.38%，理论上的达成决策均衡需要 14 轮，而实际模拟情况中平均只需要 9 轮就能达成决策一致，且最终决策就是初始最高票决策。但如果初始最高票只占 50.03%，则此时就可能出现初始状态下的低票决策反而成为最终决策的可能。

当然，上面的分析是基于平均场近似之上的各种近似手段后得到的结果，可以作为定性分析趋势的工具，但准确性有待商榷。

比如，我们在前面提到过，最后各种构型的概率存在初始状态过大而结束状态过小的可能，且平均场模型本身对多决策之间没有明显差异的情况也无法给出正确的预言，模型中也没有计算各种偏差情况的分布概率产生的影响，只是用最概然概率分布来做近似拟合。

实际情况我们只能通过程序来进行模拟。

另，在有离线节点的情况下，等价于将查询节点数 k 调小，所以依然可以用上面的模型进行定性分析。但对于拜占庭节点，情况则变得复杂，它等于可以视为在原有的决策系统之外增加了若干个固定决策源，从而对整个系统会产生影响。

定性分析加模拟可知，对于拜占庭节点，系统向正确决策方向收敛的速度会更慢，且对初始状态的要求也更高。如果说没有拜占庭节点的时候系统能安全的首要条件时初始最高票决策必须占据大多数（按照前面的分析可知，至少要大于 50%，且实际情况中达到 52% 可能才比较保险，最终决策能保证和初始最高票决策相同），而在有拜占庭节点的时候，初始状态下最高票决策的票数必须大于 $\frac{N + (G - 1) B}{G}$ 才有可能保证达成正确的共识，这也就是说拜占庭节点的数量不能超过总节点数的三分之一。

当然，即便不超过三分之一，这个结论也是定性或者最多是半定量的。

拜占庭节点可以发动日蚀攻击，即将一部分正常节点与全网其它节点孤立开，从而在局部造成拜占庭节点数比该局部内正常节点多的情况，从而在很少的几次（不超过 $1.5 \ln N_L$ 次）后将这个局部全部通化为错误决策，然后不断用这种方式来污染全网所有节点。

在考虑日蚀攻击的情况下，可以说只要给拜占庭节点足够多的时间，它们就有可能污染全网。

日蚀攻击是包括区块链在内的很多分布式系统中都有可能遇到的问题，我们当然可以通过增强全网连通性的方式来预防，但要做到 100% 安全却也是不容易的。

至此，可以说关于开头所说的这一类复杂网络中的随机扩散过程中的决策收敛问题终于有了一些定性或者半定量的结论了。

一类随机扩散过程的收敛速度问题

猜你喜欢

热点阅读