Alladi Ramakrishnan Hall

Distributed Computation of Large Scale Graph Problems

Gopal Pandurangan

University of Houston, USA

Motivated by the increasing need for fast distributed processing
of large-scale graphs such as the Web graph, biological networks and
various social networks, we study a number of fundamental graph problems in
the distributed message-passing model, where we have k machines that
jointly perform a computation on an arbitrary n-node input graph
(typically, n >> k). The graph is assumed to be randomly partitioned among
the k machines, which is a common implementation in many real world
systems. We present several complexity lower bounds that quantify the
fundamental limitations of solving graph problems in a distributed system.
To complement our lower bounds, we present algorithms for problems such as
verifying graph connectivity, computing the PageRank, and constructing a
minimum spanning tree. We also discuss how our model relates to other
distributed systems for large-scale graph processing.