Making the Impossible Possible: Ten Years of Flexible Paxos

Distributed consensus lies at the foundation of reliable distributed systems. For decades, Paxos has been the dominant solution. Its quorum requirements were treated as fundamental, shaping both theory and practice across distributed systems. In 2016, we showed that a core assumption behind Paxos was unnecessarily strict. By relaxing its quorum requirements, we introduced Flexible Paxos: a new way of thinking about consensus that opened up a broader design space for fault-tolerant systems.

This talk revisits the history of consensus, the reasoning that led to Flexible Paxos, and the impact of that result a decade later. Along the way, we will explore how questioning long-standing assumptions can reveal new possibilities in even the most established areas of computing.