It was tea time on Saturday evening, when one is in that pleasurable zone wherein Sunday is right around the corner, when the phone rang. It was my best friend A. ‘Oh, have you heard, M? H is going out with J!’ ‘What are you saying? H is going out with J? Isn’t that the same girl who had that huge fight with Boss..’ And so it went on, till every of our curio-neurons was fully satisfied with the history, geography, psychology and chemistry of the news.

‘I simply have to tell this to C!’ I trilled on the phone, bursting to tell someone about the news. ‘Ahh!’ said A, with relish, doing a Phoebe Buffay on me, ‘C already knows. D told me that she told her herself. So they know we know. But C doesn't know that we know they know we know! So, it might be fun to call her!’

Now that’s really interesting. I started wondering what time and effort it would take for our entire gang of friends to be informed of the completely useless fact that H was now going out with J. Welcome to the gossip problem! Which simply put is: If there are ‘n’ friends, each privy to the knowledge of one scandal, and they gossip only over phone, what is the minimum number of phone calls that will be required to get the news across to all n friends?

Mathematicians have made gossip immensely intellectual! The mathematical solution tells us that the minimum number of phone calls needed would be (2n-4), for n greater than or equal to 4. But let me attempt a more gossipy solution using induction. Suppose there are 4 friends, A, B, C and D, each privy to a unique scandal. A calls B, and they exchange gossip. So, at the end of that 1 call, A and B are both endowed with errr, the knowledge of 2 scandals. The same individuals are now AB and BA respectively. Similarly, C calls D. That’s Call no.2 and C and D transform into CD and DC respectively. Now AB calls CD whereas BA calls DC. At the end of these calls, all individuals are ABCD! Thus, the minimum number of calls required to get this network fully informed is 4. Well, that is also what the brilliant mathematicians told us, remember? 2n-4 i.e (2x4) – 4 = 4 calls!

Gossip doesn’t only fuel mathematicians. It has fuelled entire data networks! Many distribution networks actually use ‘gossip protocols’ to help spread information out quickly.

Ever wondered how Instagram stores and retrieves billions of those images? Traditionally, one would have to create a data storehouse where all those images were centrally stored. When a user searches for an image, the node accesses the store and retrieves the image. Now, with billions of queries hitting that poor storehouse every minute, it would only be a matter of time that it crashed. So, this storage problem had to be handled differently. It was a couple of engineers at Facebook, who created a decentralised system of storage — Cassandra — wherein each node would have its own storage.

Now, if a user connected to another node puts in a query, the query would propagate through the system through a simple gossip mechanism. You can actually hear one node asking the other, ‘And have you seen those wedding photographs of Raja and Rani? No? Ask the other nodes, bro!’ Eventually, the data propagates throughout the system where every node is ABCD! Though FB later moved on to other systems, Cassandra, that gossip monger, went on to serve as a critical web-architecture plug-in for Twitter, Instagram and even Netflix. The problem with gossip is that a single bad agent can spam up the entire system through the protocol. Imagine that a Bitcoin user spends some Bitcoin value on a transaction, and the entire world knows the exact IP through which the transaction originated.

Bye-bye, privacy! Bitcoin is now experimenting with the Dandelion protocol, wherein the query is initially literally whispered across to only one peer. So you create a long stalk of whispers and then Cassandra takes over and diffuses the gossip! Meanwhile my friend A says, ‘And here’s another piece of news. For your ears only, my best friend!’. Not best friend. Oh, no. It’s dandelion.

The author is a brave economist trying to laugh against the odds

Related Topics
comment COMMENT NOW