Generalized analysis of distributed random walk algorithm

We previously described a distributed algorithm for constructing random walks of length $l$ in dynamic graphs which runs in time $\tilde{O}(\sqrt{lD})$, where $D$ is the dynamic diameter. The author's Atish Das Sarma, Anisur Rahaman Molla and Gopal Pandurangan prove their algorithm is correct in the $\mathsf{CONGEST}(\log^2{n})$ model. The reason being that w.h.p the per-round congestion through any edge is $O(\log^2{n})$ bits. Therefore, w.h.p there will be no congestion when constructing the random walks meaning that every round all random walks increase their length by one.

Now suppose we generalise the distributed model the algorithm operates in to the $\mathsf{CONGEST}(B)$ model. Can we adapt their algorithm to work correctly at the cost of $\mathsf{polylog}(n)$ overhead?

First we observe that for $B\in \Omega(\log^2{n})$, the algorithm provided will work as is, because if we have $B\in\Omega(\log^2{n})$ bits of bandwidth per edge and we only need $O(\log^2{n})$ bits with high probability, then there will be no congestion.

If we have $B<c\log^2{n}$ for every constant $c$, then w.h.p we have $O(\frac{\log^2{n}}{B})$ additional rounds due to congestion.

proof. Each edge has bandwidth $B$ bits. We have previously established that w.h.p $\log^2{n}$ bits pass through an edge in each round. Thus $\frac{\log^2{n}}{B}$ additional rounds will be needed w.h.p to account for congestion.

Therefore, for their algorithm to work in the $\mathsf{CONGEST}(B)$ model, we just need to run the first phase of the algorithm for $2\lambda\log^2{n}/B$ rounds, where we give each random walk $\log^2{n}/B$ rounds to extend its length by one edge to account for congestion.