Metadata

Paxos consensus protocol, despite its many theoretical virtues, is fundamentally rude. One need only look at the way it behaves to see the problem. A leader seizes power. It dictates values. When two leaders happen to propose simultaneously, they do not pause, tip their hats, and work things out over tea. No,  they duel, each furiously incrementing ballot numbers at the other like barbarians engaging in a perpetual pissing contest (please excuse my language). The follower nodes, meanwhile, are reduced to the role of obedient subjects, promising their allegiance to whichever proposer shouts loudest and most recently. Having spent decades studying this rude behavior (with WPaxos , PigPaxos , and through a great many posts on this very blog ) I became convinced that the field had made a fundamental error. We had been asking "how do we reach agreement?" when the real question we should have been asking, all along, was "would it kill you to ask nicely?" It is therefor...

As I mentioned in my previous blog post, I recently got my hands on Claude Code. In the morning, I used it to build a  Hybrid Logical Clocks (HLC) visualizer . That evening, I couldn't pull myself away and decided to model something more ambitious.  I prompted Claude Code to design a Paxos tutorial game, BeatPaxos, where the player tries to "beat" the Paxos algorithm by killing one node at a time and slowing nodes down. Spoiler alert: you cannot violate Paxos safety (agreement). The best you can do is delay the decision by inducing a series of well-timed failures, and that is how you increase your score. Thinking of the game idea and semantics was my contribution, but the screen design and animations were mostly Claude’s. I do claim credit for the " red , green , blue " theme for the nodes and the colored messages; those worked well for visualization. I also specified that double-clicking a node kills it, and that the player cannot kill another node un...

This paper (to appear in VLDB'25) proposes a consensus algorithm called "Cabinet", which dynamically adjusts node weights based on responsiveness. As in the past three weeks, Aleksey and I live-recorded our first blind read and discussion of the paper to capture in real time how experts approach and dissect a paper. Below is the link to the video.  The paper I annotated during our read is available here . Frankly, we regretted reading this paper, as it had big flaws. Motivation The paper began by revisiting the role of consensus protocols in distributed systems: ensuring consistent state across replicas. It claimed that consensus often struggles with scalability because majority quorums scale poorly. But this is misleading because it omits that flexible quorums already address this issue. The paper ignores flexible quorums work, and mentions it only with one sentence. Ironically, as we will see later, flexible quorums resurface and undermine all of the paper's premis...

This paper appeared in CIDR23 and is from Meta (wow, this is the first time I used the new name without needing to mention it is in fact Facebook... wait.. goddammit). The paper talks about how they applied Raft to MySQL replication, and used the flexible quorums in the process. This is not a technically deep paper, but it was interesting to see a practical application of flexible quorums idea to Raft rather than Paxos. The most technically interesting part is the adoption of flexible quorums to Raft rather than Paxos. What is the difference? Flexible quorums idea was developed for Paxos's two phases. But, Raft needs to impose an extra requirement on quorums in order to guarantee Leader Completeness: "the new leader must already have all log entries replicated by a majority of nodes in the previous term." The paper does not call this explicitly. This is what the paper says: "For state machine safety, every data commit quorum needs to intersect with every leader elec...

This paper (PAPOC'24) is a cute paper. It isn't practical or very novel, but I  think it is a good thought-provoking paper. It did bring together the work/ideas around transaction commit for me. It also has TLA+ specs in the appendix, which could be helpful to you in your modeling adventures.  I don't like the paper's introduction and motivation sections, so I will explain these my way. The problem with 2PC 2PC is a commit protocol. A coordinator (transaction manager, TM) consistently decides based on participants (resource managers, RMs) feedback to commit or abort. If one RM sees/applies a commit, all RMs should eventually apply commit. If one RM sees/applies an abort, all RMs should eventually apply abort. Below  figure shows 2PC in action. (If you are looking for a deeper dive to 2PC, read this .) There are three different transactions going on here. All transactions access two RMs X and Y. T1, the blue transaction is coordinated by C1, and this ends up committing....

This paper appeared in SOCC'23. The paper presents a primary-backup secret-shared state machine (PBSSM) architecture and the associated consensus protocol, Oblivious Paxos (OPaxos). OPaxos enables privacy-preserving consensus by allowing acceptors to safely and consistently agree on a secret-shared value without untrusted acceptors knowing the value. OPaxos protocol overview OPaxos uses (t, n) threshold secret-sharing. This means generating n secret-shares from a single secret value such that it is possible to reconstruct the secret with just t shares. In order to make (t, n) threshold secret-sharing play well with Paxos, the protocol requires that the cardinality of the intersection of any phase1 quorum and phase2 quorum is larger than t.  This can be achieved by choosing the quorum size as (n+t)/2. More accurately,  one quorum (say phase1) would have cardinality as the ceiling of (n+t)/2, and the other quorum (phase2) would have cardinality as floor of this (n+t)/2. The ...

Nezha (VLDB'23) is a consensus protocol that leverages synchronized clocks to decrease latency and increase throughput. There is also a GitHub repo for the implementation of Nezha and TLA+ model associated with the protocol. Nezha's approach is to offload the traditional leader or sequencer-based ordering to synchronized clocks, achieving decentralized coordination without the need to rely on network routers or sequencers. Here, time synchronization is leveraged on a best-effort basis, with no impact on correctness. You guessed it right: there is a fast-path where the best-effort message ordering works, and the client waits for a super-majority quorum of replies ordered consistently. And then there is a slow-path that covers for the case where that fails. The evaluation suggests that Nezha outperforms previous protocols significantly, including an order of magnitude improvements in throughput. But the evaluations are performed with ideal conditions, and overloook the metastab...

This is a 2009 paper by Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. This paper was very well written and it was clear, and easy to follow (at least for me after having read so many Paxos papers). I finished reading the paper in one hour -- a record time for a slow reader like me. I knew about this work, but had not read the paper carefully before. I think I was overindexing on the reconfiguration aspect of Vertical Paxos, but by reading this paper (by going to the source) I found that the primary-backup replication application of Vertical Paxos was as much the point of emphasis as the reconfiguration aspect. The paper talks about the connection between Paxos and primary-backup replication applications, and presents vertical Paxos as a way of bridging these two. The paper delves down in to the leader handover and reconfiguration, and shows a practical application of these in the context of primary-backup replication protocols. Although it is possible to let the state machine reconf...