10:45 am; Seminar Hall
Distributed Computation of Large-scale Graph Problems
Gopal Pandurangan
University of Houston, USA.
05-08-16

---

Abstract

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.

About the speaker:

Gopal Pandurangan (http://www.cs.uh.edu/~gopal) is an associate professor in the Department of Computer Science at the University of Houston. He received his Ph.D. in Computer Science from Brown University in 2002. He has held faculty and visiting positions at Nanyang Technological University in Singapore, Brown University, Purdue University, and Rutgers University. His research interests are in algorithms, distributed computing, networks, large-scale data, and computational biology.