Leqi Zhu

On the Space Complexity of Colourless Tasks

Leqi Zhu is supervised by Faith Ellen in the Department of Computer Science at the University of Toronto.

This thesis comprises some of the most significant research results in the last decade in the area of distributed computing. The asynchronous shared memory model that is considered in the thesis is the standard model used to design and analyze algorithms which exploit the parallel power of multiple processors. Today, such systems are ubiquitous; the shared memory model is relevant for almost all of modern computer systems, ranging from multi-core desktop computers to high- performance clusters.

This is perhaps the most important thesis in the field of distributed computing since the thesis of Jim Aspnes about 27 years ago. It contains several lower bounds to long-standing open problems in Distributed Computing, and introduces several new proof techniques that are certain to have a continuing effect on the field.