MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

PhD Thesis Defense

Ali Pourmiri
Max-Planck-Institut für Informatik - D1
Promotionskolloquium
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Friday, 3 July 2015
09:30
60 Minutes
MMCI
001
Saarbrücken

Abstract

In this thesis, we study two basic random walk-based algorithms, which are randomized rumor spreading and balanced allocation algorithms on networks.

The \emph{Push} and \emph{Push-Pull} protocols are basic randomized protocols for information dissemination on networks. We propose a multiple calls version of the Push and Push-Pull protocols, where at the beginning every node $u$ is equipped by a random number $C_u$ and then in every succeeding round, node $u$ contacts $C_u$ neighbors to exchange the rumor. We then provide both lower and upper bounds on the rumor spreading time on a complete network depending on statistical properties of $C_u$'s. We also analyze the behavior of the standard Push-Pull protocol on random $k$-trees and random $k$-Apollonian networks that are suitable to model poorly connected, small-world and scale free networks. Here, we show that the Push-Pull protocol effectively propagates a rumor on these networks with high probability.
Besides the rumor spreading protocols, we propose a new random walk-based algorithm for sequentially allocating $n$ balls into $n$ bins that are organized as a $d$-regular graph with $n$ nodes, say $G$, where $d\ge 3$ can be any integer. Provided $G$ has a sufficiently large girth, we establish an upper bound for the maximum number of balls at any bin after allocating $n$ balls by the algorithm.

Contact

Ali Pourmiri
--email hidden
passcode not visible
logged in users only

Ali Pourmiri, 06/22/2015 18:47
Ali Pourmiri, 06/22/2015 18:47 -- Created document.