Here is the section 3.5 of Nancy Lynch's 1989 paper – A Hundred Impossibility Proofs for Distributed Computing, which is profound: What good are impossibility results, anyway? They don't seem very useful at first, since they don't allow computers to do anything they couldn't previously. Most obviously, impossibility results tell…
Google's Spanner paper was published in 2012 which famously introduced the TrueTime API. PTP is the standard equivalent of TrueTime. Two years later, Kulkarni, et al. published the Hybrid Logical Clock paper – Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases. In the HLC paper, they list the downsides…
Linearizability is one of the strongest single-object consistency models, and implies that every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations (https://jepsen.io/consistency/models/linearizable). Quite often people make the mistake of over-simplifying linearizability as the ability of being…
I previously wrote a post on reasoning DNS as a distributed database. In the same spirit, today, let's take a look at IP as distributed data (the Internet would be a distributed database in this analogy). This is inspired by a very interesting blog post from Cloudflare, https://blog.cloudflare.…
This post is a slightly expanded version of my earlier tweet. In software systems, "betting" is actually a common practice. One of the most common bets people place is retry. When the first attempt doesn't work, we can just "try it again". Retry is a bet – you are betting on…
In this post, we will show that a generic distributed critical section can't satisfy both safety and liveness properties with even a single faulty client process. System Model We assume a non-real-time system with no bound on process time or network delay. In the system, there exists a lock service…
For the entirety of this post, we assume a non-real-time system. First of all, why do we have TIMEOUT as a type of replies? What if we don't? This means, in some cases, either client or server (or both) can be "blocked" for an unbounded amount of time. With async…
DNS was created in 1983. Before then, Stanford was storing the host name to IP address map on HOSTS.TXT, which obviously doesn't scale. DNS is the address book of the internet, which performs a simple function of translating domains to IP addresses. One way of looking at it is…