Fast Flexible Paxos: Relaxing Quorum Intersection for Fast Paxos

Paxos, the de facto standard approach to solving distributed consensus, operates in two phases, each of which requires an intersecting quorum of nodes. Multi-Paxos reduces this to one phase by electing a leader but this leader is also a performance bottleneck. Fast Paxos bypasses the leader but has stronger quorum intersection requirements. In this paper we observe that Fast Paxos’ intersection requirements can be safely relaxed, reducing to just one additional intersection requirement between phase-1 quorums and any pair of fast round phase-2 quorums. We thus find that the quorums used with Fast Paxos are larger than necessary, allowing alternative quorum systems to obtain new tradeoffs between performance and fault-tolerance.

Paxos是解决分布式一致性的事实上的标准方法，它分两个阶段运行，每个阶段都需要节点的多数派交集。Multi - Paxos通过选举一个领导者将其简化为一个阶段，但这个领导者也是一个性能瓶颈。Fast Paxos绕过领导者，但对多数派交集有更严格的要求。在本文中，我们观察到Fast Paxos的交集要求可以安全地放宽，减少到第一阶段多数派和任意一对快速轮次第二阶段多数派之间仅一个额外的交集要求。因此我们发现，与Fast Paxos一起使用的多数派比实际需要的更大，这使得其他多数派系统能够在性能和容错性之间获得新的权衡。