Accelerating the grapevine effect

The process of information sharing among individuals in a network can be accelerated by designing new gossip algorithms and by borrowing ideas from optimization and machine-learning fields.


By looking at classical gossip algorithms from a novel perspective, KAUST Professor Peter Richtarik has found a way to significantly speed up gossip-based information sharing, and in the process, he discovered new applications for this efficient mathematical approach.

Gossip involves the sharing of information between individuals in a network and can be applied mathematically in both human social networks and data networks, such as distributed sensors.

“A network is a collection of nodes, each connected to other nodes via links,” explains Richtarik. “In social networks, for instance, individuals are connected to others via friendship links. In sensor networks, sensors could be connected if they are close enough to communicate over a wireless connection.”

In many real-world applications, it is often useful to perform calculations based on the data stored by all nodes across a network, such as computing the average of the private data stored by each node, which is known as the average consensus problem. However, because communication is limited to direct links between nodes, in practice, this is very challenging.

“The idea of gossip algorithms is to perform this calculation by pairwise communication among randomly selected friends and to repeat this process until all individuals learn the result,” says Richtarik. “This mimics the way gossip works among humans. It’s surprising that it is possible to show mathematically that this simple communication strategy can solve a global, network-wide problem.”

Read the full article