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 , presented in the industry track of ICDE 2024 , introduces GaussDB-Global (GlobalDB) , Huawei's geographically distributed database system. GlobalDB replaces the centralized transaction management (GTM) of GaussDB with a decentralized system based on synchronized global clocks (GClock) . This approach mirrors Google Spanner's TrueTime approach and its commit-wait technique, which provides externally serializable transactions by waiting out the uncertainty interval. However, GlobalDB claims compatibility with commodity hardware, avoiding the need for specialized networking infrastructure for synchronized clock distribution. The GClock system uses GPS receivers and atomic clocks as the global time source device at each regional cluster. Each node synchronizes its clock with the global time source over TCP every 1 millisecond. Clock deviation is kept low because synchronization is achieved within 60 microseconds as a TCP round trip, and the CPU’s clock drift is bound...

This master's thesis at Lund University Sweden  explores how CockroachDB 's transactional performance can be improved by using tightly synchronized clocks. The paper addresses two questions: how to integrate high-precision clock synchronization into CockroachDB and the resulting impact on performance. Given the publicly available clock synchronization technologies like Amazon Time Sync Service and ClockBound, the researchers (Jacob and Fabian) argue that the traditional skepticism around the reliability of clocks in distributed systems is outdated.  CockroachDB vs Spanner approaches CockroachDB uses loosely-synchronized NTP clocks, and achieves linearizability by using Hybrid Logical Clocks (HLC) and relying on a static maximum offset (max_offset=500milliseconds) to account for clock skew. However, this approach has limitations, particularly in handling transactional conflicts within a predefined uncertainty interval. When a transaction reads a value with a timestamp falling ...

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 paper is from 1991, by Barbara Liskov. To set the context, viewstamped replication paper was published at 1988, and the Paxos tech report (which failed to publish) came in 1989. This paper also comes only 3 years after the NTP RFC was written. Although this is an old paper, it is a timely (!) one. The paper discusses how clocks can be used for improving the performance of distributed systems. This paper is a visionary paper, ahead of its time. It is possible to criticize the paper by saying it was too optimistic in assuming time synchronization has arrived (it took another 2 decades or so for time synchronization to make it make it). But going off with that optimistic premise, the paper made so many remarkable contributions. The next noteworthy update on the practical use of synchronized clocks came 21 years later in 2012 with Spanner . Sanjay Ghemawat on the Spanner paper was Liskov's student that worked on the Harp project. This brings me to the next impressive thing about ...

Let's start with the impossibility results, a good place to start distributed systems discussion. The coordinated attack result says that if the communication channels can drop messages arbitrarily and undetectably you cannot solve distributed consensus using a deterministic protocol in finite rounds. This result is all about *the curse of asymmetry of information*. Reliable channels are needed for two parties to agree on something. Otherwise the two parties are stuck in a Zeno's paradox of "You may not know that I know that you know that I know" kind of information chaining. A classic paper to checkout on the topic is " Knowledge and common knowledge in a distributed environment ". Assuming mostly reliable channels and demanding majority acks, it is possible to solve consensus in a partially synchronous system. Paxos shows us how to do this. Paxos uses quorum of acks to get around the problem of "the agreement having to occur in one shot" as in ...