English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 numberof rounds required to obtain a random walk sample. Das Sarma et al. [PODC'10]show that a random walk of length $\ell$ on a network of diameter $D$ can beperformed in $\tilde O(\sqrt{\ell D}+D)$ time. A major question left open iswhether there exists a faster algorithm, especially whether the multiplicationof $\sqrt{\ell}$ and $\sqrt{D}$ is necessary.  In this paper, we show a tight unconditional lower bound on the timecomplexity of distributed random walk computation. Specifically, we show thatfor any $n$, $D$, and $D\leq \ell \leq (n/(D^3\log n))^{1/4}$, performing arandom walk of length $\Theta(\ell)$ on an $n$-node network of diameter $D$requires $\Omega(\sqrt{\ell D}+D)$ time. This bound is {\em unconditional},i.e., it holds for any (possibly randomized) algorithm. To the best of ourknowledge, this is the first lower bound that the diameter plays a role ofmultiplicative factor. Our bound shows that the algorithm of Das Sarma et al.is time optimal.  Our proof technique introduces a new connection between {\em bounded-round}communication complexity and distributed algorithm lower bounds with $D$ as atrade-off parameter, strengthening the previous study by Das Sarma et al.[STOC'11]. In particular, we make use of the bounded-round communicationcomplexity of the pointer chasing problem. Our technique can be of independentinterest and may be useful in showing non-trivial lower bounds on thecomplexity of other fundamental distributed computing problems.

A Tight Lower Bound on Distributed Random Walk Computation