Cloudflare has been building Meerkat, their new global consensus service, built on a protocol called QuePaxa instead of the usual Raft or Paxos.
To be honest, I did not know about QuePaxa before this. I learned about it from the post itself, and it is genuinely interesting.
Most consensus systems, like Raft, rely on timeouts to detect a dead leader and trigger a new election. That works fine until your network latency fluctuates a lot, which is exactly what Cloudflare deals with every day.
Too short a timeout, and replicas panic and block writes. Too long, and the system just sits there while something is actually broken. So instead of Raft, Meerkat runs on QuePaxa. Here is how QuePaxa avoids the leader problem.
A client does not need to go through a leader at all; it can contact any replica, and that replica can drive consensus for the current slot on its own. A leader still exists in the system, and it has one advantage: if it is the one proposing, it takes just one round trip to reach a decision.
A non-leader replica needs three or more round-trip to do the same thing. So the leader speeds things up, but it is not a requirement for progress. If the leader goes down or slows down, any other replica simply picks up the work, and writing keeps flowing.
Also, concurrent proposals do not conflict destructively. The replicas coordinate and converge on a single agreed value regardless. Interestingly, Cloudflare is planning to build a full key-value store and a leasing system on top of it.
I have started reading up on QuePaxa after this post, and wanted to share what I found first.