The power of choice in random walks

摘要

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 because random walks present locality, simplicity, low-overhead and inherent robustness to structural changes. In this work we propose and investigate an enhanced algorithm that we refer to as random walks with choice. In this algorithm, instead of selecting just one neighbor at each step, the walk moves to the next node after examining a small number of neighbors sampled at random. Our empirical results on random geometric graphs, the model best suited for wireless networks, suggest a significant improvement in important metrics such as the cover time and load-balancing properties of random walks. We also systematically investigate random walks with choice on networks with a square grid topology. Forthis case, our simulations indicate that there is an unbounded improvement in cover time even with a choice of only two neighbors. We also observe a large reduction in the variance of the cover time, and a significant improvement in visit load balancing.