#### 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.

Done