Technical Report PHD-2017-16

Title: Distributed Distance Computation and Related Topics
Authors: Ami Paz
Supervisors: Keren Censor-Hillel
PDFCurrently accessibly only within the Technion network
Abstract: The wide spread of distributed systems in recent years poses new challenges to computer scientists. This thesis studies several problems in distributed systems, focusing on distance computation problems and other, related topics.

One of the central distance computation problems is the computation of all-pair-shortest-paths, where each unit of a distributed system should learn its distances to all other units. For this problem, we present fast algorithms in networks with all-to-all communication, using fast matrix multiplication algorithms. In general networks, this problem seems much harder, and for this setting we prove that improving the state-of-the-art lower bounds will require new tools. Another distance-related problem is the construction of sparse subgraphs that approximately preserve distances, called spanners. Spanners have a wide range of applications in distributed systems, but the study of their distributed construction still lags behind the study of sequential spanner-construction algorithms. We present distributed algorithms for the construction of spanners that preserve the distances up to an additive factor, and prove lower bounds on the time needed for their construction.

We continue the study of lower bounds, and prove almost quadratic time lower bounds for several natural problems in distributed graph algorithms, including the construction of a minimum vertex cover, a maximum independent set and the computation of the chromatic number. In addition, we prove quadratic time lower bounds for problems in P, and show the largest possible gap between the running times of deterministic and randomized algorithms in this setting.

Apart from the construction of subgraphs and computation of graph parameters, we also consider the verification of given properties of the graph. To this end, we study the notion of proof-labeling schemes, which allow fast verification using predefined node labels. In this setting, we use nondeterministic communication complexity in order to prove lower bounds on the label sizes, and then suggest that approximation algorithms can help in circumventing these bounds. To achieve this goal, we define a new notion called approximate proof-labeling schemes, provide several such schemes with labels smaller than those necessary for exact proof-labeling schemes, and present a tradeoff between the approximation ratio and the label sizes. Finally, we turn our attention to a different model of solving graph problems with uncertainty regarding the graph structure. This is the semi-streaming model, where a single processing unit with a limited memory has to process a graph too large to fit in memory. In this model, we consider the maximum weighted matching problem and provide a (2+epsilon)-approximation algorithm for it, matching the state-of-the-art result for unweighted graphs.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2017
To the main CS technical reports page

Computer science department, Technion