DOI

10.17077/etd.nwoh-93qn

Document Type

Dissertation

Date of Degree

Summer 2019

Degree Name

PhD (Doctor of Philosophy)

Degree In

Computer Science

First Advisor

Pemmaraju, Sriram

First Committee Member

Ghosh, Sukumar

Second Committee Member

Ohlmann, Jeffrey

Third Committee Member

Varadarajan, Kasturi

Fourth Committee Member

Stump, Aaron

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 (\Delta+1)-Coloring, 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. This dissertation focuses on finding upper and lower bounds for symmetry breaking problems, such as MIS and t-Ruling Set, in these congested models.

Chapter 2 shows that an MIS can be computed in O(sqrt{log n loglog n}) rounds for graphs with constant arboricity in the CONGEST model. Chapter 3 shows that the t-ruling set problem, for t \geq 3, can be computed in o(log n) rounds in the CONGEST model. Moreover, it is shown 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. Chapter 4 shows that any algorithm in the BEEP model (which assumes 'primitive' single bit messages) with message complexity M and round complexity T can be simulated in O(t(M/k^2 + T) poly(log n)) rounds in the k-machine model. Using this result, it is shown that MIS, Minimum Dominating Set (MDS), and

Minimum Connected Dominating Set (MCDS) can all be solved in O(poly(log n) m/k^2) rounds in the k-machine model, where 'm' is the number of edges in the input graph. It is shown that a 2-ruling set can be computed even faster, in O((n/k^2+ k) poly(log n)) rounds, in the k-machine model. On the other hand, using information theoretic techniques and a reduction to a communication complexity problem, an \Omega(n/(k^2 poly(log n))) rounds 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.

Chapter 5 focuses on the Max Clique problem in the CONGEST model. Max Clique is trivially solvable in one round in the LOCAL model since each node can share its entire neighborhood with all neighbors in a single round. However, in the CONGEST model, nodes have to choose what to communicate and along what communication links. Thus, in a sense, they have to break symmetry and this is forced upon them by the bandwidth constraints. Chapter 5 shows that an O(n^{3/5})-approximation to Max Clique in the CONGEST model can be computed in O(1) rounds. This dissertation ends with open questions in Chapter 6.

Keywords

Distributed Algorithms, Distributed Systems, Graph Theory, Information Theory, Maximal Independent Set, Modes of Computation

Pages

xi, 99 pages

Bibliography

Includes bibliographical references (pages 93-99).

Copyright

Copyright © 2019 Talal Riaz

Share

COinS