MIT-Harvard CINCS / Hamilton Institute seminar


Date: April 28, 2021

Time: 10AM EST



Password: 825980

Speaker: Ayalvadi Ganesh

Title: Broadcasting in random graphs


Abstract: Consider a set of n agents, each of whom has a single message to convey to all other agents. The messages are all of the same length. Time is divided into rounds, and during each round, each agent may broadcast a single message. Agents are represented as nodes of a directed communication graph, and a broadcast is received error-free by all (out)-neighbours of the broadcasting node. The problem is to minimise the number of rounds until all agents have received all messages.


This is known as the gossiping problem, and various versions of it have been studied. In our version, the communication graph is a dense directed Erdos-Renyi random graph G(n,p), and we seek simply decentralised gossip algorithms. We consider two algorithms, random relaying and random linear network coding. We consider a sequence of graphs with p fixed and n tending to infinity. Our main results are that random relaying requires Theta(log n) rounds, whereas random linear network coding requires only a constant number of rounds.



Bio: Ayalvadi Ganesh is an Associate Professor at the School of Mathematics, University of Bristol. His research interests include large deviations, queueing theory, random graph dynamics, and decentralised algorithms. He won the INFORMS Best Publication Award in 2005 and the ACM Sigmetrics Best Paper Prize in 2010.