Controlling Information Diffusion in Gossip Protocols

For a long time, gossip protocols have been used to model the spread of infectious diseases or rumors in social networks. They have also resulted in significant advances in peer-to-peer machine learning and decentralized optimization. Based on the theory of gossip protocols, the current research proposes to design a principled framework to control the spread of fake news or infectious diseases.

In a social network, communication is expected to be efficient in promoting information dissemination quickly among participants. Any agent that tries to slow down this process is considered an adversary to the system. Instead, if information spreads too quickly without checks and balances, it makes the system vulnerable to fake news. The present research aims to turn adversaries into algorithms and control the diffusion of information in gossip protocols.

To achieve that objective, the project proposes two lines of research:

• Devise algorithmic solutions to stop or slow the spread of fake news.
• Provide efficient methods to detect the source of fake news.

To achieve the first research outcome (to stop the dissemination of fake news), the study will focus on transforming an omniscient adversary into an efficient spread control algorithm. Considering the number of communications it is allowed to disrupt, a spread control algorithm will aim to maximize the dissemination time of the fake news it attacks. The research will consider several phases in the development of this computational adversary with increasing complexity.

The second research objective (detecting the source of information in a gossip protocol) is challenging because random and local communications make the identification difficult and ensure privacy. There are only limited detection capabilities in the literature, and it is unclear whether it is possible to exactly locate the source of a gossip. To overcome this challenge and design new algorithms for source detection, the researchers will leverage the findings of an earlier work¹ that studied the anonymity of gossip protocols through the lens of differential privacy.

While pursuing each of the two lines of research, the researchers will initially investigate the setting where agents communicate using a gossip protocol without learning from each other (dissemination of information) and then adapt their findings to the setting where agents aim to collaboratively learn a machine learning model (peer-to-peer machine learning).

Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx. Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols. In International Symposium on Distributed Computing (DISC 2020), Freiburg, Germany,2020.