Flexible Paxos is the simple observation that it is not necessary to require all quorums in Paxos to intersect. It is sufficient to require that the quorum used by the leader election phase (phase-1) will overlap with the quorums used by previous replication phases (phase-2). Majority quorums are one such way to meet this requirement, but many more exist. Thus, Paxos is just a single point on a broad spectrum of possibilities for safely reaching distributed consensus. To learn more about Flexible Paxos and how it is used to build more resilient distributed systems, take a look at the papers, talks, and open source projects below.
Papers
- Flexible Paxos: Quorum intersection revisited - The original paper describing Flexible Paxos
- Fast Flexible Paxos: Relaxing Quorum Intersection for Fast Paxos - extending Flexible Paxos to Fast Paxos
- Paxos Made EPR: Decidable Reasoning about Distributed Protocols
- DPaxos: Managing Data Closer to Users for Low-Latency and Mobile Applications
- Multileader WAN Paxos: Ruling the Archipelago with Fast Consensus
- A Generalised Solution to Distributed Consensus
- Dissecting the Performance of Strongly-Consistent Replication Protocols
- Near-Optimal Latency Versus Cost Tradeoffs in Geo-Distributed Storage
- On the Parallels between Paxos and Raft, and how to Port Optimizations
- WPaxos: Wide Area Network Flexible Consensus
- Bipartisan Paxos: A Modular State Machine Replication Protocol
- Flexible Paxos: An Industry Perspective
- Unifying Consensus and Atomic Commitment for Effective Cloud Data Management
- Linearizable Quorum Reads in Paxos
- Matchmaker Paxos: A Reconfigurable Consensus Protocol
- FleetDB: Follow-the-workload Data Migration for Globe-Spanning Databases
- On the Significance of Consecutive Ballots in Paxos
- Low-Latency Geo-Replicated State Machines with Guaranteed Writes
- State-Machine Replication for Planet-Scale Systems
- Unbounded Pipelining in Dynamically Reconfigurable Paxos Clusters
- Revisiting the Paxos Foundations: A Look at Summer Internship Work at VMware Research
- Odyssey: The Impact of Modern Hardware on Strongly-Consistent Replication Protocols
Articles & Blog Posts
- A More Flexible Paxos - A brief introduction to Flexible Paxos for the systems community, posted on Tech musings by Sugu Sougoumarane
- Majority agreement is not necessary for consensus - A summary of the key results of the Flexible Paxos paper, posted on Read, Write and Execute by Heidi Howard
- Flexible Paxos: A new breed of scalable, resilient and performant consensus algorithms is made possible - Dahlia Malkhi describes the story of the Flexible Paxos at VMware Research
- Distributed Durability in MySQL - A proposal to modify the MySQL semi-sync replication process in order to improve the overall consistency, posted on Tech musings by Sugu Sougoumarane
- Flexible Paxos: Quorum intersection revisited - The popular research blog, the morning paper, covers the Flexible Paxos preprint, posted on the morning paper by Adrian Colyer
- The load, capacity, and availability of quorum systems - Following up from the citation in Flexible Paxos, the morning paper covers Naor & Wool, posted on the morning paper by Adrian Colyer
- Modeling Paxos and Flexible Paxos in Pluscal and TLA+ - Murat Demirbas details how he model checked Paxos and then Flexible Paxos using Pluscal, posted on Metadata
- Summary of Flexible Paxos: Relaxing the quorum constraint
- Paul Cavallaro on Flexible Paxos
- UPaxos and primary-backup replication
- Improved Majority Quorums for Raft
- Paxosmon: Gotta Consensus Them All - Nice summary of the various Paxos variants
Talks
- Distributed consensus: Making impossible possible - An overview of the key results in the field of distributed consensus. Talk by Heidi Howard at OSCON London in 2016. [Slides]
- Flexible Paxos: Revisiting quorum intersection using TLA+ - Part of the Dr TLA+ series by Microsoft Research
- Constructing Scalable, Resilient and Consistent Systems with Flexible Paxos - Talk by Heidi Howard at Dockercon 2017
Code
- LibFPaxos - A patch to LibPaxos3 which exposes quorum size as a configuration parameter. Licensed under 3-clause BSD.
- LibFPaxos Benchmarks- Scripts for reproducing the LibFPaxos experiments from the Flexible Paxos paper using Mininet. Licensed under MIT.
- Flexible Paxos TLA+ - TLA+ specification of single-valued Flexible Paxos. Licensed under MIT.
- Flexible Raft TLA+ - TLA+ specification of Raft, modified for flexible quorums. Licensed under MIT.
- LogDevice - A distributed log storage systems from Facebook
- Paxi - Simulation framework for distributed consensus algorithms which includes prototypes of various algorithms including Flexible Paxos and Fast Flexible Paxos
- FrankenPaxos - Another distributed consensus simulator which includes prototypes of various consensus algorithm including Flexible Paxos
- FlexibleZoo - Zookeeper fork by Max Meldrum
- FPaxosPython - A (naive) implementation of Flexible Paxos