Papers We Love Conf 2019

September 12, 2019 / St. Louis, Missouri

Heidi Howard

Cambridge University

photo of Heidi Howard

Distributed consensus revised

Distributed consensus, the ability to reach agreement in the face of failures and asynchrony, is a fundamental and powerful primitive for constructing reliable distributed systems from unreliable components. For over two decades, the Paxos algorithm has been synonymous with distributed consensus. Paxos is widely deployed in production systems, yet it is poorly understood and it proves to be heavyweight, unscalable and unreliable in practice.

In this talk, we re-examine the foundations of how Paxos solves distributed consensus. Our hypothesis is that these limitations are not inherent to the problem of consensus but instead specific to the approach of Paxos. The surprising result of our analysis is a substantial weakening to the requirements of this widely studied algorithm. Building on this insight, we are able to prove an extensive generalisation over the Paxos algorithm.


Dr. Heidi Howard is a research fellow based at Cambridge University’s Department of Computer Science and Technology. Heidi’s research focuses on improving consistency, reliability and performance in distributed systems. Heidi received her BA in Computer Science from Cambridge University in 2014.

In 2019, Heidi received her PhD from Cambridge University for her research on distributed consensus. Heidi is probably most widely known for her generalizations of the widely used Paxos algorithm for solving consensus, including her work on Flexible Paxos.