max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 New for: D1, D2, D3, D4, D5
 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Randomized Rumor Spreading in Poorly Connected Real-World Networks Ali Pourmiri Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Tuesday, 10 June 2014 13:00 30 Minutes Saarbrücken E1 4 023
 The standard {\sf Push-Pull} protocol, introduced by Demers et al. is a well-studied rumor spreading protocol on networks. Initially a single node is aware of a pieces of information 'known as rumor' then the protocol proceeds in rounds, in each round, every informed node calls a random neighbor and pushes the the rumor to the neighbor and every {uninformed} node calls a random neighbor and pulls the rumor from the neighbor if it possibly knows the rumor. We analyze the behavior of this protocol on random $k$-trees, a class of power law graphs which are small-world and have large clustering coefficients and polynomially bad expansion profile. We show that, with high probability {\sf Push-Pull} propagates the rumor in O(log^2 n) rounds to almost all modes. Also we prove that with probability $1-o(1)$ the protocol needs at least n^{\Omega(1)} rounds to inform all nodes. This exponential dichotomy between time required for informing \emph{almost all} and \emph{all} nodes is striking.
Name(s): Ali Pourmiri