max planck institut
informatik

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

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: PhD Thesis Defense Ali Pourmiri Max-Planck-Institut für Informatik - D1 Promotionskolloquium D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Friday, 3 July 2015 09:30 60 Minutes Saarbrücken MMCI 001
 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.
Name(s): Ali Pourmiri