In [1], we prove an optimal time lower bound for solving the mutual exclusion problem in a shared memory system, thereby resolving a longstanding open problem. Our paper introduced a novel and powerful information-theoretic proof technique, which we believe will lead to new lower bounds for a variety of problems in distributed computing.

In a nutshell, our proof is based on the following two ideas. We first show that a set of n processes solving mutual exclusion must interact to obtain at least Ω(n log n) bits of information, enough to specify a permutation over themselves. We then present a method to adversarially schedule any mutual exclusion algorithm so that each step by a process obtains only O(1) bits of information. Hence, the ratio of the required information to the acquired information per step yields a lower bound on the step (time) complexity of mutual exclusion.

Our original extended abstract is available here. This thesis chapter contains a detailed exposition and rigorous proof of our results. The pictures below illustrate different aspects of our proof.

[1] Rui Fan and Nancy Lynch. An Ω(n log n) Lower Bound on the Cost of Mutual Exclusion. In Proceedings of ACM PODC 2006, pages 275 - 284.