טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentDory Michal
SubjectDistributed Network Design
DepartmentDepartment of Computer Science
Supervisor Professor Keren Censor-Hillel
Full Thesis textFull thesis text - English Version


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.