This is not a bad list for sure. Here are some deeper cuts for those looking for something a bit less mainstream:
"The Maintenance of Duplicate Databases" https://datatracker.ietf.org/doc/html/rfc677 (AFAIK the genesis of the use of logical clocks in distributed systems).
"Chain Replication for Supporting High Throughput and Availability" https://www.usenix.org/legacy/event/osdi04/tech/full_papers/... (Chain replication is how a huge percentage of real-world cloud-scale data replication is done).
"Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (The formalization of CAP, which caused a ton of very poor trade-off thinking in the decade that followed by defining Availability in a very goofy way. Still a classic.)
"Paxos Made Live" https://research.google/pubs/paxos-made-live-an-engineering-... (Brought a much-needed engineering perspective to a conversation that was largely theoretical up until this time.)
"Practical Byzantine fault tolerance" (Moved the conversation on Byzantine faults forward significantly).
This is just a short selection. There's so much good stuff going back in the 70s and 80s distributed database literature, for example (and in the modern systems and DB literature too).
Lamport lists his collected works on his site[0] along with some commentary for each one, and directly mentions, The Maintenance of Duplicate Databases, as the origin for logical clock paper. Many of the notes have interesting commentary.
> Many computer scientists claim to have read it. But I have rarely encountered anyone who was aware that the paper said anything about state machines. People seem to think that it is about either the causality relation on events in a distributed system, or the distributed mutual exclusion problem. People have insisted that there is nothing about state machines in the paper. I've even had to go back and reread it to convince myself that I really did remember what I had written.[1]
0: https://lamport.azurewebsites.net 1: https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
> Chain replication is how a huge percentage of real-world cloud-scale data replication is done
Is this still true today? I know that Facebook does [1], but I don't have references for any other places which use it.
[1] https://engineering.fb.com/2022/05/04/data-infrastructure/de...
Inside multiple AWS products (including DynamoDB, Kinesis, and Aurora DSQL) is a system called Journal that moves a ton of data. It uses a variant of chain replication.
EBS is also a chain replication variant at heart, and moves even more data.
Question from a recent CS grad here, who just learnt about CAP: what do you mean by “very poor trade-off thinking in the decade that followed”?
A Critique of the CAP theorem by Martin Kleppmann.
https://arxiv.org/abs/1509.05393
Basically naive CAP theorem assumes "no latency (delay) allowed", in which case, yeah, sure, the quorum must agree or you are writing to a split-brain quorum somehow. But what if delay sensitivity is a knob that can be tuned, and writes have conflict resolution?
Martin Kleppmann's book Designing Data-Intensive Applications is considered a useful tome for anyone who needs a insight in the complexity involved in distributed systems (hint: getting data in ram flushed to an SSD also involves multiple moving parts)
Basically, many people convinced themselves that the formalization of CAP means that systems need to choose between highly available and strongly consistent, and hence chose eventual consistency. This is, partially, because Gilbert and Lynch define "availability" to mean "available to all clients, even those on a minority side of a partition". The much more useful "available to a majority of clients" is achievable at the same time as strong consistency in presence of a single partition, and this is the common cloud failure mode.
See https://brooker.co.za/blog/2024/07/25/cap-again.html for a longer take.
Other, much more reasonable trade-offs, lead to eventual consistency too. Mostly latency optimizations, but many of those also lead to non-zero RPO and so are undesirable for multiple reasons. We discuss some of this in section 8 of the DSQL paper: https://arxiv.org/pdf/2607.13276
Thank you both! That was really enlightening & made for interesting reading!
Though the note at the bottom of the article to teachers to not start with CAP has me concerned about the quality of other content I’ve seen thus far …