Technical Report MSC-2021-06

Title: Distributed computations with global edges of limited bandwidth
Authors: Volodymyr Polosukhin
Supervisors: Keren Censor-Hillel
PDFCurrently accessibly only within the Technion network
Abstract: In this thesis, we study the effect of global links with limited bandwidth on distributed communication. We research this question in two distributed models. One model is the well-known \clique model, and another model is the recently introduced \hybrid network model.

The \clique model is a distributed model where $n$ machines execute the protocol in synchronous communication rounds. On each round, each pair of machines can exchange a single $\bigO{\log{n}}$-bit long message in each direction. In other words, each pair of machines is connected by a global communication link with a bandwidth of $\bigO{\log{n}}$ bits. The complexity measure in this model is the number of rounds until the last machine terminates. The natural goal is to speed up algorithms by using as much of the model's $\bigO{n^2}$-message bandwidth as possible.

In this thesis, we address a complementary question of running in parallel as many distributed jobs as possible. Formally, we solve the distributed scheduling problem. In this problem, the system receives jobs, i.e., protocols with the corresponding inputs, which are provided in a distributed manner. The system is required to produce the output for each job in a distributed fashion, i.e., each machine outputs part of the output corresponding to its input.

Our contributions are deterministic and randomized algorithms for the distributed scheduling problem. The runtime of those algorithms under certain assumptions is close to the natural lower bounds for this problem.

In addition to the \clique model, we study the \hybrid network model. It lays down the theoretical foundations for networks that combine two possible modes of communication: high-bandwidth communication with neighbors in the graph via local links and low-bandwidth all-to-all communication via global links. In this model, we address fundamental problems of distance computation. We achieve fast algorithms for distance-related problems due to \emph{density-aware} communication protocols that utilize global links.

Our contributions include \emph{exact} weighted shortest path from $n^{1/3}$ sources, approximations for eccentricities and diameter, and distance approximations from multiple sources.

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 MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion