2021 Principles of Distributed Computing Doctoral Dissertation Award

A pleasingly large number of doctoral dissertations were submitted for the 2021
Principles of Distributed Computing Doctoral Dissertation Award, all of outstanding quality. After careful deliberation, the Committee made the choice to share the award between two theses:

● “On the Space Complexity of Colourless Tasks” by Leqi Zhu, and
● “Towards Universal Optimality in Distributed Optimization” by Goran Zuzic.

Zhu’s thesis establishes general memory lower bounds for both deterministic and randomized algorithms for a variety of basic synchronization tasks including consensus, k-set agreement, and epsilon-approximate agreement. These bounds hold under a weak liveness assumption—obstruction-freedom—making them very general. Among the results in the thesis one stands out. It provides a definitive solution to a classic and long-standing open problem in distributed computing: to determine the space complexity of consensus in asynchronous, shared-memory systems. Besides the significance of the result, the Committee also appreciated its beautiful execution—a clean, textbook-quality proof. On the basis of this achievement the Committee made its decision to assign the award to this excellent piece of work.

Zuzic’s thesis tackles another fundamental problem, in the area of distributed graph algorithms. Loosely speaking, the thesis concerns graph theoretic problems that are non-local, in the sense that they require a number of steps at least proportional to the diameter of the network. This is a large class containing fundamental algorithmic problems such as MST, shortest paths, and min cut. The stated goal is to come up with distributed algorithms that are optimal for every graph topology. In doing so, one must first divine the relevant graph-topology parameters embodying the computational obstruction, and then design algorithms whose performance matches those topological bounds. This is an arduous and ambitious research program, and Zuzic’s thesis insightfully covers a lot of ground. For this impressive overall achievement the Committee judged this excellent thesis also worthy of the award.

The 2021 Principles of Distributed Computing Doctoral Dissertation Award Committee:
Marcos K. Aguilera, VMware
Hagit Attiya, Technion
Christian Cachin, University of Bern
Alessandro Panconesi, Sapienza University of Rome (chair)