Speaker: |
Ayalvadi Ganesh (University of Bristol) |

Organiser: |
Rahul Vaze |

Date: |
Friday, 12 Aug 2022, 11:00 to 12:00 |

Venue: |
A201 |

(Scan to add to calendar)

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 simple 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.