MIT-Harvard CINCS / Hamilton Institute Seminar

    Wednesday, April 28, 2021 - 15:00 to 16:00
    Zoom

    https://mit.zoom.us/j/94416668228?pwd=LzJCV1VveUZ6WHdkQnlwektrVVkwQT09
    Passcode: 825980

    MIT-Harvard CINCS (Communications Information Networks Circuits and Signals) / Hamilton Institute Seminar

    Speaker: Professor Ayalvadi Ganesh, University of Bristol

    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.