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

Motivated by the increasing need for fast processing of large-scale graphs,we study a number of fundamental graph problems in a message-passing model fordistributed computing, called $k$-machine model, where we have $k$ machinesthat jointly perform computations on $n$-node graphs. The graph is assumed tobe partitioned in a balanced fashion among the $k$ machines, a commonimplementation in many real-world systems. Communication is point-to-point viabandwidth-constrained links, and the goal is to minimize the round complexity,i.e., the number of communication rounds required to finish a computation.  We present a generic methodology that allows to obtain efficient algorithmsin the $k$-machine model using distributed algorithms for the classical CONGESTmodel of distributed computing. Using this methodology, we obtain algorithmsfor various fundamental graph problems such as connectivity, minimum spanningtrees, shortest paths, maximal independent sets, and finding subgraphs, showingthat many of these problems can be solved in $\tilde{O}(n/k)$ rounds; thisshows that one can achieve speedup nearly linear in $k$.  To complement our upper bounds, we present lower bounds on the roundcomplexity that quantify the fundamental limitations of solving graph problemsdistributively. We first show a lower bound of $\Omega(n/k)$ rounds forcomputing a spanning tree of the input graph. This result implies the samebound for other fundamental problems such as computing a minimum spanning tree,breadth-first tree, or shortest paths tree. We also show a $\tilde\Omega(n/k^2)$ lower bound for connectivity, spanning tree verification andother related problems. The latter lower bounds follow from the development andapplication of novel results in a random-partition variant of the classicalcommunication complexity model.

Distributed Algorithms for Large-Scale Graphs