Technical Report PHD-2020-07

Title: Distributed Network Design
Authors: Michal Dory
Supervisors: Keren Censor-Hillel
PDFCurrently accessibly only within the Technion network
Abstract: Large scale distributed networks, as the internet, play a central role in the modern world. Thus, distributed algorithms become more relevant than ever. This thesis studies distributed algorithms for fundamental graph problems, from the area of network design. We start by studying connectivity related problems, where the goal is to build a low-cost backbone of a distributed network that is resilient to failures, or alternatively augment the connectivity of a given backbone to increase its reliability. While such problems have been widely studied in the standard centralized setting, the focus of this work is on designing distributed algorithms for these tasks. Here the nodes of the communication network themselves should build the backbone, by communicating with adjacent nodes, and without seeing the whole network. We continue by studying distributed algorithms and hardness results for k-spanners. Here the goal is to build a low-cost backbone of the network that preserves the distances up to a multiplicative k factor. Our contribution is twofold, presenting both approximation algorithms and hardness of approximation results for the fundamental k-spanner problem. Finally, we study the closely related problem of distance computation in distributed networks. We design fast approximate shortest paths algorithms in the distributed Congested Clique model, improving significantly upon the state-of-the-art. On the way of obtaining our results, we develop a rich set of tools, that may have potential applications in studying various related problems.
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 2020
To the main CS technical reports page

Computer science department, Technion