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

AG Audience

English

45 Minutes

Saarbrücken

In recent years random-walk-based algorithms have been proposed for a variety of networking tasks. These proposals include searching, routing, self-stabilization, and query processing in wireless networks, peer-to-peer networks and other distributed systems. This approach is gaining popularity since random walks present locality, simplicity, low-overhead and inherent robustness to structural changes. Two properties of random walks on graphs are essential to determine the efficiency of this approach: cover time (the expected time to visit all nodes) and mixing time (in regular graphs, the time to sample a node uniformly). In this talk I will present some of the work on the topic I was involved in, emphasizing results related to applications for wireless networks, dynamic networks and parallel random walks.

Joint work with: Noga Alon, Roy Friedman, Gaby Kilot, Michal Koucky, Gady Kozma, Bhaskar Krishnamachari, Yuval Lando, Zvi Lotker and Mark Tuttle

--email hidden

passcode not visible

logged in users only