Final exam - Symmetry Breaking: Upper and Lower Bounds

Date: 
May 3, 2019 - 11:00am
Location: 
2520B UCC

PhD Candidate: Talal Riaz

Abstract:

A fundamental issue in many distributed computing problems is the need for nodes to distinguish themselves from their neighbors in a process referred to as symmetry breaking. Many well-known problems such as Maximal Independent Set (MIS), t-ruling set, Maximal Matching, and Minimum Vertex Cover, belong to the class of problems that require symmetry breaking. These problems have been studied extensively in the LOCAL model, which assumes arbitrarily large message sizes, but not as much in the CONGEST and k-machine models, which assume messages of size O(log n) bits.

My research has focused on improving upper and lower bounds for symmetry breaking problems in the CONGEST and k-machine models. We provide an MIS algorithm that runs in  O(sqrt(log n log log n)) rounds for graphs with constant arboricity in the CONGEST model. We further show that the t-ruling set problem, for t ≥ 3, can be computed in o(log n) rounds in the congest model, and that a 2-ruling set can be computed in o(log n) rounds for a large range of values of the maximum degree in the graph.

In the k-machine model, k machines must work together to solve a problem on an arbitrary n-node graph, where n is typically much larger than k. We prove that MIS, Minimum Dominating Set, and Minimum Connected Dominating Set can all be solved in O(poly(log n) * n/k^2) rounds in the k-machine model, where m is the number of edges in the input graph. It is also shown that a 2-ruling set can be computed even faster, in O(poly(\log n) n/k^2 + k) rounds, in the k-machine model. On the other hand, using information theoretic techniques and a reduction to a communication complexity problem, an O(n/k^2) lower bound for MIS in the k-machine model is also shown. As far as we know, this is the first example of a lower bound in the k-machine model for a symmetry breaking problem.

Advisor: Sriram Pemmaraju