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.

References

• Distributed consensus revised by Heidi Howard
• The part-time parliament by Leslie Lamport
• Paxos Made Moderately Complex by Robbert Van Renesse and Deniz Altinbuken
• Flexible Paxos: Quorum intersection revisited by Heidi Howard, Dahlia Malkhi, Alexander Spiegelman
• A Generalised Solution to Distributed Consensus by Heidi Howard, Richard Mortier
• the morning paper: Distributed consensus revised - Part I
• the morning paper: Distributed consensus revised - Part II
• the morning paper: Distributed consensus revised - Part III

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.

• Twitter @heidiann360
• Site: http://heidihoward.co.uk
• DBLP: https://dblp.uni-trier.de/pers/hd/h/Howard:Heidi