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

Question

In gossip-based protocols, how do we guarantee that all nodes get infected by the message?

If we selected a random number of nodes and send a message to these nodes, and these nodes did the same, there is a probability that some node will not receive the message.

Although I couldn't calculate it, it seems small. However, if the system is running for a long time, at some point one nodes will be unlucky and will be leftover.

Answer 1

It's a bit hard to answer, due to two reasons:

1. There isn't really a gossip-based protocol. At most, there are families of gossip-based algorithms.

2. The algorithms actually guarantee infection only under specific assumptions. E.g., if, as you put it, as "the system is running for a long time" any given link fails permanently under some exponential process (a very likely scenario), then with probability 1 some node will be completely isolated, and no protocol can overcome that.

However, IIUC, you're asking about a protocol with the following assumptions:

1. For any group V' ⊂ V of nodes, there is an active link u ∈ V' → v ∈ V ∖ V'.

2. Each node chooses uniformly d of its neighbors at each step, irrespective of their state, choices made by other nodes, total update state, etc.

Under these conditions, the problem you raised will have probability 0.

You can think about the infection as a Markov Chain where the system is at state i if i nodes are infected. Suppose some change originated at some s ∈ V, and so the system starts at state i.

• By property 1., there is a link from the i infected nodes to one of the n - i others.

• By property 2., the probability of selecting this link is at least 1 / n. This is because the node whose link happens to cross the cut, has at most n neighbors, but at least one neighbor across the cut. Even if its selection is entirely stateless and uninformed, that is the chance that it will choose this neighbor.

Therefore, the probability that this will not happen for j steps is (1 - d/n)^j. Using the Union Bound, the probability that this will happen for any state i is at most n (1 - 1/n)^j. Take j = n², and this becomes n e^{- n}; take j = n³, and this becomes n e^{- n2}. Etc.

(Of course, gossip algorithm infection happens much sooner; this is an upper bound for the worst-possible conditions.)

So, if the system runs long enough, the probability that some node does not become infected, decreases to 0 (very quickly). For Anti-Entropy Gossip Protocols, this is enough. For some other protocols, as you suspected, there is a chance that some node will be missed for some update.

Answer 2

We can't provide an answer because you don't understand your problem (hence the question is ambiguous)

• The topology of the network is unknown, but the answer depend on it
• What's the stop condition of the algorithm? Does it stop or not?

Suppose that a given node is connected to all the other node (that's the topology) and each node perform the same action if it receive a message.

You could simplify your problem into smaller sub-problems (that's the divide-et-impera approach): imagine that any node perform just one attempt (i.e. i = 1).

Since any node picks the receiver completely at random and since this operation is done infinite times then eventually all the nodes will receive the message. How many iterations are required to reach a given confidence (ratio of node which received the message / no. of all nodes ) is up to you.

Once you get this including the repeated attempt i is straightforward.

Answer 3

I made a little simulation of what you're trying to do. 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;
}

• node - number of total nodes
• tries - the starting amount of random selections
• startNode - the node that gets the first message
• reached - a hash set of nodes that were reached by the current simulation

At each level of the recursive the number of tries is decreased by one. It takes ~9 tries to get 100% coverage of 65536 (2^16) nodes.