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

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:PhD Thesis Defense
Speaker:Ali Pourmiri
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Promotionskolloquium
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:Friday, 3 July 2015
Duration:60 Minutes
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Ali Pourmiri, 06/22/2015 06:47 PM
  • Ali Pourmiri, 06/22/2015 06:47 PM -- Created document.