A Tight Lower Bound on Distributed Random Walk Computation

Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan

We consider the problem of performing a random walk in a distributed network. Given bandwidth constraints, the goal of the problem is to minimize the number of rounds required to o…