Department seminar: Distributed Computing on Massive Graphs. Wednesday 03/13 12-1pm
Professor Peter Robinson (McMaster University)
Distributed Computing on Massive Graphs
Date: Wednesday March 13th 12-1pm
Location: LAS 3033
Lunch will be provided.
Motivated by the increasing need for fast distributed processing of large graphs such as the Web graph, biological networks, and various social networks, we study fundamental graph problems in the distributed message-passing model, where k machines jointly perform computation on an n-node input graph. (Typically, n is much larger than k.) The graph is assumed to be randomly partitioned among the k machines, which is a common implementation in many real-world systems. We quantify the fundamental limitations of solving graph problems in a distributed system by giving complexity lower bounds. To complement our lower bounds, we show how problems such as verifying graph connectivity and computing the PageRank can be solved efficiently. We also discuss how our model relates to real-world distributed systems for graph processing such as Google Pregel and Apache Giraph.
Peter Robinson is an Assistant Professor at McMaster University. Previously, he was a Lecturer at Royal Holloway University of London and he obtained his PhD from the Vienna University of Technology. His research interests are in the areas of distributed and parallel algorithms, big data processing, and fault-tolerant computation in communication networks such as peer-to-peer systems. His work has received two Best Paper Awards and he is serving as the General Chair of ACM PODC 2019.