Distributed Computation of Large-scale Graph Problems

When: Friday, June 19, 2015
Where: PGH 550
Time: 11:00 AM

Speaker: Peter Robinson, Queen’s University, Belfast

Host: Prof. Gopal Pandurangan

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.

Bio:

Peter Robinson is an Assistant Professor (UK Lecturer) at Queen's University Belfast. Previously, he was a research fellow at the National University of Singapore and the Nanyang Technological University. He received a PhD in computer science from the Vienna University of Technology in 2011. His research focuses on distributed computing. This includes designing new distributed and parallel algorithms, distributed processing of large-scale data, and secure computation in dynamic networks. He received the Best Paper award at the 14th International Conference on Distributed Computing and Networking and at the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems.