Metadata

People want data fast. They also want it consistent. Those two wants pull in opposite directions. This VLDB'25 paper does another take on this conundrum. Rather than assuming a symmetric network environment where all replicas face similar latencies, the paper emphasizes that in practice, some replicas are closer to the leader, where others are stranded halfway across the globe. By embracing this asymmetry, the authors propose two new algorithms: Pairwise-Leader (PL) and Pairwise-All (PA). Both cut read latency compared to the prior approaches. PL could even achieve 50x latency improvements in some cases. Aleksey and I did our usual thing. We recorded our first blind read of the paper . I also annotated a copy while reading which you can access here. We liked the ideas, even though the protocols themselves didn't thrill us particularly. I particularly liked finding another good example of the use of synchronized time in distributed database systems. Another study to add to my s...

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...

Aleksey and I sat down to read this paper on Monday night. This was an experiment which aimed to share how experts read papers in real time. We haven't read this paper before to keep things raw. As it is with research, we ended up arguing with the paper (and between each other) back and forth. It was messy, and it was also awesome. We had a lot of fun. Check our discussion video below (please listen at 1.5x, I sound less horrible at that speed, ah also this thing is 2 hours long). The paper I annotated during our discussion is also available here. This paper appeared in HotOS 2025 , so it is very recent. It's a position paper arguing that the traditional F-threshold fault model in consensus protocols is outdated and even misleading. Yes, the F-threshold fault model does feel like training wheels we never took off. In his essay " the joy of sects" , Pat Helland bring this topic to tease distributed systems folk: " Distributed systems folks. These people vacilla...

Chapter 7 of the Concurrency Control and Recovery in Database Systems book by Bernstein and Hadzilacos (1987) tackles the distributed commit problem: ensuring atomic commit across a set of distributed sites that may fail independently. The chapter covers these concepts: The challenges of transaction processing in distributed database systems (which wasn't around in 1987) Failure models (site and communication) and timeout-based detection The definition and guarantees of Atomic Commitment Protocols (ACPs) The Two-Phase Commit (2PC) protocol (and its cooperative termination variant) The limitations of 2PC (especially blocking) Introduction and advantages of the Three-Phase Commit (3PC) protocol Despite its rigor and methodical development, the chapter feels like a suspense movie today. We, the readers, equipped with modern tools like FLP impossibility result and Paxos protocol watch as the authors try to navigate a minefield, unaware of the lurking impossibility results that were pu...

The chapter 9 of the Designing Data Intensive Applications (DDIA) book has the following 4 sections (which contain a total of 10 subsections).   Consistency guarantees Linearizability Ordering guarantees Distributed transactions and consensus TMI (Too much info) The chapter tries to do too much. Almost an entire semester of distributed systems content is force-jammed into this chapter. I don't think the discord reading group will be able to complete this chapter and make sense of what is going on. For a more manageable load, much of this chapter should be moved to other chapters. The chapter starts with explaining linearizability. It would have been better to explain this in Chapter 5, Replication. Linearizability sounds easy, but it takes time to internalize. I had discussed linearizability here , and later revisited it with this paper . And of course it was mentioned in many other posts. The chapter continues with CAP tradeoff, rightly calling it "the unhelpful CAP theorem...

Ok, continuing on the SRDS day 1 post , I bring you SRDS day 2. Here are my summaries from the keynote, and from the talks for which I took some notes.  Mahesh Balakrishnan's Keynote Mahesh 's keynote was titled "An Hourglass Architecture for Distributed Systems" . His talk focused on the evolution of his perspective on distributed systems research and the importance of abstraction in managing complexity. He began by reflecting on how in his PhD days, he believed the goal was to develop better protocols with nice properties. He said, he later realized that the true challenge in distributed systems research lies in creating new abstractions that simplify these complex systems. Complexity creeps into distributed systems through failures, asynchrony, and change. Mahesh also confessed that he didn't realize the extent to the importance of managing change until his days in industry.  While other fields in computer science have successfully built robust abstractions (su...

This paper recently appeared at ACM SIGOPS Operating Systems Review. It provides an overview of the shared log abstraction in distributed systems, particularly focusing on its application in State Machine Replication (SMR) and consensus protocols. The paper argues that this abstraction can simplify the design and implementation of distributed systems, and can make them more reliable and easier to maintain. What is the shared log abstraction? The shared log abstraction proposes to separate the system into two layers: the database layer (proposers/learners) and the log layer (acceptors). The shared log provides a simple API for appending entries, checking the tail, reading entries, and trimming the log. This separation allows the SMR layer to focus on higher-level concerns without dealing with the complexities of consensus protocols. This is a wisdom packed paper. It approaches the problem more from software engineering and systems/operations perspectives. ( Previous work, the Delos OSD...

Here we do a walkthrough of the TLA+ specs for the MongoDB logless reconfiguration protocol we have reviewed recently. The specs are available at the  https://github.com/will62794/logless-reconfig  repo provided by Will Schultz, Siyuan Zhou, and Ian Dardik.  This is the protocol model for managing logless reconfiguration. Let's call this the "config state machine" (CSM). This is the protocol model for static MongoDB replication protocol based on Raft. Let's call this the "oplog state machine" (OSM).  Finally this model composes the above two protocols so they work in a superimposed manner. I really admire how these specs provided a modular composition of the reconfiguration protocol and Raft-based replication protocol. I figured I would explain how this works here, since walkthroughs of advanced/intermediate TLA+ specifications, especially for composed systems, are rare. I will cover the structure of the two protocols (CSM and OSM) briefly, before diving ...