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
Thomas Sauerwald, 03/20/2012 12:08
Thomas Sauerwald, 03/15/2012 17:46
Thomas Sauerwald, 03/15/2012 12:13
Thomas Sauerwald, 03/13/2012 11:07
Thomas Sauerwald, 03/09/2012 10:28 -- Created document.