AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Ali Pourmiri

--email hidden

passcode not visible

logged in users only