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:Fast Random Walks on Overlay Networks
Speaker:Paresh Nakhe
coming from:IIT Madras – India
Speakers Bio:Master of Technology
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 10 February 2014
Duration:90 Minutes
Building:E1 4
Random walks are a fundamental concept which finds use in numerous applications both in computer science and elsewhere. They are most commonly used for sampling in distributed networks to introduce randomization. Given the scale and nature of networks in today’s world, it is indispensable to come up with more efficient ways to perform random walks. In this work, we focus on overlay networks in which nodes may communicate with each other either using the communication links on overlay network or it may use the underlying infrastructure network. We refer to this as the direct communication model. This work is an attempt to explore this model and find advantages of it over other existing models.

Our major contribution in this work is a rigorous framework for constructing random walks of length log n in a network of n nodes in small enough number of rounds. We establish this framework on both static and dynamic networks. For static networks, we propose an algorithm that constructs polylog(n) number of random walks per node in O(log log n) rounds. We show that the algorithm can be extended to work with high probability in a dynamic environment subject to high adversarial churn rate, albeit for a smaller number of nodes.
We demonstrate the effectiveness of this framework by designing a more efficient algorithm for information dissemination than the current state of the art. Specifically, we show that the problem can be solved in O(n / log^t n) where t>0 is a constant.

Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Aaron Alsancak, 02/06/2014 10:41 AM -- Created document.