This is a theoretical question about how gossip protocols work; I am not asking about any specific implementation or piece of software.

I've read the wikipedia page https://en.wikipedia.org/wiki/Gossip_protocol on gossip protocols, and the idea seems like an excellent way to avoid having a master node in a cluster (say, because traffic is too heavy to all direct it through any particular node, no matter how quickly that traffic is redirected). I would imagine you could register a new node by pointing it to any particular node in the cluster, having the knowledge of the new node shift through the cluster through gossip, and have it make a few edges with a few neighbors.

I would assume that no particular node has complete knowledge of the entire network, as the cluster could be large enough to make this prohibitive.

However, in this case one would imagine that through random behaviors, nodes adding and dropping, eventually the network could become disconnected (in the graph-theoretic sense), after which point it could never become reconnected without outside intervention.

Is this correct? And if so, what can be done about it? I can think of a few answers but I feel like none of them are satisfactory, and I wonder if one of them is standard, or there is another possibility I haven't thought of:

  1. There is a central registry, and new nodes must contact this registry in order to be connected to the cluster. But this seems to invalidate the masterless idea, even if it's only registration traffic that flows through it.
  2. Every node knows about every other node (modulo the time spent propagating the nodes' information). This prevents disconnectedness and makes a lot of things easy to implement, but puts an upper limit on the size of the cluster (or a lower limit on the power of the connecting machines).

Are either of these "standard?" Is there another possibility I didn't think of? Wikipedia doesn't address it and my googling hasn't gotten me any kind of answer.

Note: Apologies if this fits better on stackoverflow; it seemed like a tossup as to which site it better belonged on, as it's theoretical and certainly within the scope of CS research, but based on the lack of relevant tags below, it may not be part of the typical scope of the site.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.