אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We study the cost of communication in designing fast distributed graph algorithms.

For many graph problems, the phrase ``fast distributed algorithms'' refers to algorithms whose running time is $\polylog(n)$ (or even faster).
Problems that admit such fast algorithms are usually referred to as local problems and include fundamental symmetry breaking problems such as maximal independent set (MIS), $(\Delta + 1)$-coloring, and maximal matching (MM), which have been studied extensively for several decades.

However, the communication cost of all known fast algorithms for fundamental local symmetry breaking problems is high, in general, as high as $\Omega(n^{2})$;
in fact, for the aforementioned problems, there are impossibility results, showing that communicating $\Omega(n^{2})$ bits is, in general, mandatory, regardless of running time.

This raises the following cardinal question:
Do there exist distributed algorithms for important local symmetry breaking problems that are simultaneously communication-efficient and fast?

We answer this question in the affirmative by developing fast distributed algorithms with near-linear (in $n$) communication complexity for two ruling set problems, which are important generalizations of MIS that have been extensively studied and widely used in distributed computing.
Specifically, the main contributions of this work are randomized distributed algorithms that run for $O(\log n)$ rounds, send $n \polylog(n)$ constant size messages, and construct $(\alpha, \beta)$-ruling sets with high probability for
$(\alpha, \beta) \in \{ (2, 3), (3, 4) \}$.

We emphasize that these algorithms are near-optimal in terms of both their communication complexity and round complexity (using constant size messages).
Our ruling set constructions are based on the design of a communication- and time-efficient distributed algorithm for a new graph theoretic problem, called low volume $k$-dominating set, which may be of independent interest.