Fast Random Walks on Overlay Networks

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.