Discrete Math Seminar: Abbas Mehrabian

  • Date: 10/06/2015
  • Time: 16:00
Abbas Mehrabian, UBC and SFU

University of British Columbia


Bounds for Randomized Rumour Spreading Protocols


Consider a social network modelled as a graph, with people and friendships represented by vertices and edges, respectively. Suppose that a person knows a piece of information, and as time passes, talks to other people and spreads it. How long it takes until everyone knows the rumour? The answer, which we call the "spread time", certainly depends on the graph's structure and how the rumour spreads. In this talk we discuss two well known randomized rumour spreading protocols (known as push&pull protocols) and survey the known results on their spread times on various graphs.


Based on joint work with H. Acan, A. Collevecchio, and N. Wormald.

Other Information: 

Location: ESB 4127