Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Randomized Rumor Spreading in Poorly Connected Real-World Networks
Speaker:Ali Pourmiri
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 10 June 2014
Duration:30 Minutes
Building:E1 4
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Ali Pourmiri, 06/10/2014 09:12 AM
  • Ali Pourmiri, 06/04/2014 10:32 AM
  • Ali Pourmiri, 06/04/2014 10:31 AM -- Created document.