Goran is a Ph.D. student of Bernhard Haeupler at CMU.

AG 1   Info

AG Audience

English

45 Minutes

Saarbrücken

The modern computation and information processing systems shaping our world have become massively distributed and a fundamental understanding of distributed algorithmics has never been more important. At the same time, despite 40 years of intense study, we do not have a satisfactory understanding of how a network topology influences the runtime of various distributed tasks.

I will present ongoing work that provides structural insights into the answer using the unexpected lens of information theory. Concretely, suppose we are solving a distributed optimization problem (e.g., minimum spanning tree problem, minimum cut, or shortest path) in the classic CONGEST model of distributed computing. The work shows, via an information-theoretic argument, that a fast distributed algorithm for any of the above problems induces a specific combinatorial structure in the graph. In other words, the non-existence of this structure represents the first non-trivial lower bound on the runtime of distributed optimization tasks that can be applied to any network topology. Furthermore, we conjecture that the bound is tight---the existence of this structure in a topology implies the existence of fast distributed algorithms. Proving the conjecture would lead to universally optimal distributed algorithms, resolving a long-standing open problem posed in [Garay, Kutten, Peleg; 1998]. Finally, we present some preliminary evidence to the correctness of the conjecture and propose a roadmap to resolve it.

This talk presents ongoing joint work with Bernhard Haeupler and David Wajc.

Christoph Lenzen

--email hidden

passcode not visible

logged in users only

Goran will present remotely by video.