在基于八卦的协议中如何保证所有节点都被感染？

Question

在基于八卦的协议中，我们如何保证所有节点都被消息感染？

如果我们选择随机数量的节点并向这些节点发送消息，而这些节点也这样做，则有可能某些节点不会收到消息。

虽然算不出来，但好像很小。但是，如果系统运行时间长了，某个时候某个节点会倒霉，就会被遗弃。

Answer 1

这个问题有点难回答，原因有二：

并没有真正的a 基于八卦的协议。最多有家族个基于八卦的算法。
算法实际上只有在特定假设下才能保证感染。例如，如果，如您所说，"the system is running for a long time" 任何给定的 link 在某个指数过程（很可能发生的情况）下永久失败，那么某个节点将以 1 的概率完全隔离，并且没有协议可以克服它。

但是，IIUC，您询问的协议具有以下假设：

对于任何组 V' ⊂ V个节点，有一个activelinku∈ V' 右箭头; v∈ V∖ V'。

每个节点在每一步统一选择 d 个它的邻居，而不考虑它们的状态、其他节点的选择、总更新状态等

在这种情况下，你提出的问题概率为0。

如果 i 个节点被感染，您可以将感染视为 Markov Chain，系统处于 i 状态.假设某些更改起源于某些 s ∈ V，所以系统从状态i开始。

通过属性 1.,有一个link从i个感染节点到n - i 其他人。
通过属性 2.，选择这个link的概率至少是1 / n。这是因为 link 恰好穿过切割的节点最多有 n 个邻居，但至少有一个邻居穿过切割。即使它的选择完全是无状态和不知情的，那也是它会选择这个邻居的机会。

因此，不会发生 j 步的概率是 (1 - d/n)^j。使用 Union Bound，任何状态 i 发生这种情况的概率最多为 n (1 - 1/n)^j。取j = n²，变成n e^{- n};取 j = n³，这就变成了 n e^{- n²}。等等

（当然，八卦算法感染发生得更快；这是最坏情况的上限。）

因此，如果系统运行时间足够长，则某些节点未被感染的概率会降低到 0（非常快）。对于Anti-Entropy Gossip Protocols，这就足够了。对于某些其他协议，正如您所怀疑的那样，有可能某些节点会因某些更新而丢失。

Answer 2

我们无法提供答案，因为您不了解您的问题（因此问题不明确）

网络的拓扑结构未知，但答案取决于它
算法的停止条件是什么？停不停？

假设给定节点连接到所有其他节点（即拓扑）并且每个节点在收到消息时执行相同的操作。

您可以将您的问题简化为更小的子问题（即分而治之的方法）：想象任何节点只执行一次尝试（即 i = 1）。

由于任何节点都完全随机地选择接收者，并且由于此操作进行了无限次，因此最终所有节点都会收到消息。需要多少次迭代才能达到给定的置信度（接收消息的节点的比率/所有节点的数量）由您决定。

一旦你得到这个包括重复尝试 i 就很简单了。

Answer 3

我对你正在尝试做的事情做了一些模拟。 http://jsfiddle.net/ut78sega/

function gossip(nodes, tries, startNode, reached) {
    var stack = [startNode, tries];
    while(stack.length > 0) {
        var ttl = stack.pop();
        var n = stack.pop();
        reached[n] = 1;
        if(ttl <= 0) { continue; }
        for(var i=0; i < ttl; i++) {
            stack.push(Math.floor(Math.random() * nodes), ttl - 1);
        }
    }
    return reached;
}

节点 - 节点总数
tries - 随机选择的起始数量
startNode - 得到第一条消息的节点
reached - 当前模拟到达的节点哈希集

在递归的每个级别，尝试次数都会减少一次。需要 ~9 次尝试才能 100% 覆盖 65536 (2^16) 个节点。

在基于八卦的协议中如何保证所有节点都被感染？

How to guarantee that all nodes get infected in gossip-based protocols?

distributed-computing

gossip