Postdoc Leqi Zhu wins PODC Dissertation Award

CSE postdoctoral researcher Leqi Zhu has been awarded a 2021 Principles of Distributed Computing Doctoral Dissertation Award for his dissertation, “On the Space Complexity of Colourless Tasks,” which he completed at the University of Toronto.

The PODC Dissertation Award was created in 2012 to acknowledge and promote outstanding research by doctoral (PhD) students on the principles of distributed computing. One or two dissertations are selected for this honor each year.

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.

The paper was especially significant for providing a definitive solution to a classic and long-standing open problem in distributed computing: determining the space complexity of consensus in asynchronous, shared-memory systems. In their announcement, the POCD Committee point out the “clean, textbook-quality proof” Zhu used to achieve this result.

In a previous nomination for this thesis, Zhu’s PhD advisor Prof. Faith Ellen wrote that he “has completely solved a longstanding open problem in the theory of distributed computing, has substantially improved a lower bound for another important problem, and has opened a new research direction within this field.”

Zhu is advised at Michigan by Prof. Seth Pettie.