Gossip Protocol

What is it good for?

Imagine we want to broadcast a message in a network (which contains millions of nodes). We can broadcast our message via delivering this message to every node by ourselves. Which will be very secure, but slow, and will be costly (might consume a lot of bandwidth).

Instead, we will do what people do in their daily life. We will gossip about it. The gossip will spread by itself! At the end of the day, we will not be delivering our message by knocking on every person’s door, instead of watching TV in our apartment. Isn’t it wonderful?

No, it isn’t. Watching TV is a waste of time.

Don’t watch TV

How it works

  1. If you have a new message (whether you are the first person who will tell the others, or hear something new from your neighbours), relay this new message only to your neighbours.
  2. If a message comes to you, but you already knew about it, discard that message

That’s all!

And it makes perfect sense for our daily lives, think of it. When you hear a new gossip, you tell that to your friends. But if you hear the same gossip from somebody else, you don’t go to your friends and tell the same gossip again. Imagine telling the same gossip to everyone, whenever you hear it from anyone.

There are complex mathematical proofs on how much will it take for a message to propagate through the network, its cost, order of the messages, etc…

But we don’t need to worry about them. If everybody tells every new gossip to their neighbours, we are sure that eventually all the new messages will be heard by everyone.