1. React
  2. Papers We Love Conf
  3. 2019
  4. Distributed Consensus Revised

Distributed Consensus Revised

Heidi Howard at Papers We Love Conf 2019

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 (https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-935.pdf) The part-time parliament by Leslie Lamport (https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf) Paxos Made Moderately Complex by Robbert Van Renesse and Deniz Altinbuken (http://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf) Flexible Paxos: Quorum intersection revisited by Heidi Howard, Dahlia Malkhi, Alexander Spiegelman (https://arxiv.org/abs/1608.06696) A Generalised Solution to Distributed Consensus by Heidi Howard, Richard Mortier (https://arxiv.org/abs/1902.06776) the morning paper: Distributed consensus revised - Part I (https://blog.acolyer.org/2019/05/07/distributed-consensus-revised-part-i/) the morning paper: Distributed consensus revised - Part II (https://blog.acolyer.org/2019/05/08/distributed-consensus-revised-part-ii/) the morning paper: Distributed consensus revised - Part III (https://blog.acolyer.org/2019/05/10/distributed-consensus-revised-part-iii/)