Final exam: Efficient Graph Computing on the Congested Clique

Date: 
August 4, 2016 - 1:30pm
Location: 
2520B UCC

PhD Candidate: Vivek Sardeshmukh

Abstract

In this report, we initiate study on understanding a theoretical model for distributed computing called Congested Clique. This report presents constant-time and near-constant-time distributed algorithms for a variety of problems in the Congested Clique model.
     We start by showing how to compute a 3-ruling set in expected O(log log log n) rounds and using this, we obtain a constant-approximation to metric facility location, also in expected O(log log log n) rounds.  Then, we study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). These results significantly improve on the running time of the fastest known algorithms for these problems in the Congested Clique setting.
     Thus far there has been little work on understanding the message complexity of problems in the Congested Clique. In this report, we initiate a study on the message complexity of Congested Clique algorithms. We study two graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, focusing on the design of fast algorithms with low message complexity. Our motivation comes from recently established connections between the Congested Clique model and models of large-scale distributed computing such as MapReduce (Hegeman et al., SIROCCO 2014) and the “big data” model (Klauck et al., SODA 2015). For these connections to be fruitful, Congested Clique algorithms not only need to be fast, they also need to have low message complexity. While the aforementioned algorithms are fast, they have an Omega(n^2) message complexity, which makes them impractical in the context of the MapReduce and “big data” models. This motivates our goal of achieving low message complexity, without sacrificing the speed of the algorithm. We present several new results in this direction. 
     Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity.

Advisor: Sriram Pemmaraju