6 ms·

Distributed Systems Classics (2017)

340 points by grep_it 14d ago

nesarkvechnep 14d ago
As always, lists like these don’t include Joe Armstrong's PhD thesis “Making reliable distributed systems in the presence of software errors” - http://erlang.org/download/armstrong_thesis_2003.pdf http://erlang.org/download/armstrong_thesis_2003.pdf
- Suhinnall27 14d ago
  Are there any other works that should also be included that you know of?
  - FabHK 14d ago
    Not OP, but a good resource for distributed consensus specifically is Tim Roughgarden's YouTube playlist "Foundations of Blockchains" [0] (hear me out, despite the title - see below). It's 85 videos over 12 lectures, rigorous, very well explained (but assumes some CS fundamentals). Not original work, but gives the conceptual framework and background so that one can read these classic papers in context. Per-lecture reading lists are on the course page [1]. He also points at Elaine Shi's Foundations of Distributed Consensus and Blockchains [2] and Andrew Lewis-Pye's Consensus in 50 pages [2] as background, though these are more textbooks, not papers. Remarkably, the first 7 lectures deal with permissioned systems, recapitulating the classic results of consensus in distributed systems (Dolev Strong, FLP impossibility, CAP) - no blockchain in sight. This takes us to the state of the art at the end of the 1990's (with algorithms that can achieve consensus in the presence of byzantine failures, namely Byzantine Paxos and PBFT, though he discusses a modern variant, permissioned Tendermint from 2014). Lecture 8 stays permissioned and proves consistency and chain quality for the longest-chain rule. Only at Lecture 9, with proof of work, does anything specifically blockchain appear; then L10 block rewards and selfish mining, L11 transaction fee mechanism design; L12 proof-of-stake sybil resistance with the whole litany of attacks possible there. Very good series in my view, and shows how little technical merit this whole blockchain circus has - nearly all the great properties people tout (reliability, consistency, audibility, availability) can be achieved with good old permissioned tech more efficiently, with pretty instant and deterministic finality. Anyway, I found the series worth watching for the classical consensus material alone. [0] https://www.youtube.com/playlist?list=PLEGCF-WLh2RLOHv_xUGLqRts_9JxrckiA https://www.youtube.com/playlist?list=PLEGCF-WLh2RLOHv_xUGLq... [1] https://timroughgarden.github.io/fob21/ https://timroughgarden.github.io/fob21/ [2] https://elaineshi.com/docs/blockchain-book.pdf https://elaineshi.com/docs/blockchain-book.pdf [3] https://lewis-pye.com/2022/08/15/consensus-in-50-pages/ https://lewis-pye.com/2022/08/15/consensus-in-50-pages/
- jermberj 14d ago
  No disrespect meant to Mr. Armstrong, but it's possible it's never listed because it's basically a textbook. It's 295 pages. The rough average of all papers in OP is like 15 pages.
  - vulcan01 14d ago
    His thesis is only slightly longer than typical PhD theses, I think.
    - derefr 14d ago
      Yes, but the other things in the OP list aren't theses, they're journal papers.
    - throwaway219450 14d ago
      I would say 300 is more than slightly longer. Varies by institution and style, but 100k words, 4-5 collated papers, 100-150 pages maximum are quite common. I would be concerned as an examiner if this came across my desk, more so if I read the colophon where the author comments that they intended to write their own typesetting system, before reading Knuth and wisely concluding that they were unlikely to do anything better than TeX. Top tier yak shaving there.
  - moritz 14d ago
    One can skip the Erlang-specific things/the description of the programming language. Just the first 2 chapters (~30p) + the Conclusion (~10p) contain a lot of useful food for thought.
- brcmthrowaway 14d ago
  Does anyone use Elixir/Erlang anymore?
  - appstorelottery 14d ago
    WhatsApp backend in Erlang + used in telecoms
    - brcmthrowaway 14d ago
      The "WhatsApp used Erlang" story was a decade ago, doubt it is true now.
      - toast0 14d ago
        There's still a lot of WhatsApp Erlang tooling being published, so I'm pretty sure it's mostly still Erlang. I think I still know a couple people who would share with me if it was rewritten, although I left in 2019. Erlang is simply the right language to build a chat server with, and it doesn't make sense to rewrite it in another language, even though Facebook did that with the server for Messenger. :P Certainly parts of the WhatsApp stack have changed considerably. No more FreeBSD / no more only a handful of OS processes per node, much less Mnesia (not sure if there's any Mnesia left... I don't get that level of information). I've seen signs that they may have returned to large nodes, so they might be back to millions of connections per node, but that was very much not the case when I left; connection counts had dropped on our FreeBSD nodes because we were doing a lot more on the chat channel and then again because the Facebook nodes we migrated to were so much smaller than our FreeBSD nodes.
      - Joel_Mckay 14d ago
        I doubt they changed out Erlang/Elixir, as it is mature backbone infrastructure. It has run many telecoms for over 30 years without issue. The problem is finding talent that knows both distributed systems, and Erlang/Elixir. But Erlang/OTP can replace a lot of expensive kludges. =3
        14d ago
- Joel_Mckay 14d ago
  reliable? we all wish... In distributed systems the fist lesson is resilience is more important. Spend enough time in a computer lab, and you will see things halt and catch fire on occasion. Especially if it has a bunch of GPUs pinning the utilization 24/7, or a cheap power supply in the cluster. =3
nylonstrung 14d ago
Lamport is the author of more than half of these, it's crazy how influential he is in this space In addition to making LaTex which has almost nothing to do with it
- phtrivier 14d ago
  It's the thing that baffles me the most with those people, the Knuths and Lamports and Carmarcks, and whatnot. It's not like they have light schedules - they do research, they have classes, they attendconference, and they have jobs, etc... And some benefit from tenure, which give them time to deeply focus on some topics. But I can't imagine how I would write tex in ten years in Pascal on archaic machines if I had all the time to myself. Doing that in the middle of understanding more computer science than my eyes would ever read ? What do they do with their time ? What do they don't do ? Are they able to skip the eating and pooping and sleeping and cleaning their house and picking up parcels at the post office and grocery shopping parts ? Or a proto Unix being written in three weeks. Concretely, what are the days of those three weeks made of ? Especially since it's famously when the spouse was NOT there to handle the housekeeping... I see not amount of "life hacks" and "atomic habits" and whatnot helping with that. But it's probably just as natural to them as biking - and you can't explain biking, I guess ?
  - drfuchs 14d ago
    A favorite Knuth story to illustrate: He was re-writing the 8080 code for the processor that ran our new Alphatype CRS Phototypesetter, since the manufacturer's code wasn't suitable. Real-time, 7 levels of simultaneous interrupt stuff, since it controlled two stepper motors that moved the lens around the photographic paper, plus four custom font outline-tracing S100 cards that flashed vertical segments of characters at just the right moment on the CRT that the lens then focused onto the paper. No debugability other than a 4x4 keyboard and a 15(?) character display. I was responsible for the code on the other end of the RS232 port that connected it to the DEC mainframe, sending down character outlines on the fly to the very limited memory on the 8080, along with the properly-sorted character placement info ultimately from TeX. Anyway, we'd been doing morning, noon, and night debugging sessions together for a number of days. On maybe the 3rd morning, I arrived at his office and was speaking with his secretary of many years, Phyllis Winkler, when Knuth came in. He handed her a stack of maybe a dozen or two pages, saying "Here's a paper I wrote; please type it in." When? When did he write it? It's still a mystery to me.
bestpickle 14d ago
[dead]
Aditya_0315 14d ago
[flagged]
mjb 14d ago
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 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/renesse/renesse.pdf 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-perspective-2006-invited-talk/ 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).
- grep_it 14d ago
  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 https://lamport.azurewebsites.net 1: https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
- ksambhi 14d ago
  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”?
bigcat12345678 14d ago
I am a Lamport admirer. I gradually realized that Lamport is more of the godfather of distributed system than Hinton is to deep learning. Lamport is less prominent than Shannon is to information theory. Shannon is the closest to any title of "gold-like" figure to a scientific discipline of universal relevance in modern society. Lamport specifically revealed a philosophical connections between computer systems and physics, in the parallel of distributed consensus to relativity theory. To me, the enlightenment is that, the relations between events happening in a distributed system, is more fundamental than their absolute ordering, thus the central role of an "observer". I haven't really analyzed if this realization is from Lamport's papers, or my general reading and thinking, but I am moderately confident that general readings are heavily influenced by Lamport's papers, or can be traced back to be compatible with Lamport's thinking. I have not seriously study if this connection is valid in depth, which might be another pure amateur speculation of mine. One thing I think Lamport falls short is that his writing is not easy to read and understand. I unconciously feel that Lamport (and Dario from Anthropic) probably share a hidden sense of intellectual supriority grew from their own experience throughout their career. So their writing (and Dario's gospel) all share a unchangable sense of narration from their own delicate and graceful ideas, much less of faciliating the understanding to their audience. In this cateogry, Shannon is abosolutely superior in any measure, in his writing, ideas are so naturally presented, although the implications of the ideas remain elusive due to the inherent depth. Also, among the 3 prominent figures of modern AI: Hinton/Bengio are more like Shannon, Lecun is closer to Lamport. Enough random rambling. Lamport, as indicated by the outweight presence in this list, is no doubt the single most important scientist in distributed systems.
- toast0 14d ago
  > the relations between events happening in a distributed system, is more fundamental than their absolute ordering The important thing in most distributed systems is having an order. Having a single observer serialize events as it receives them is so much more tractable than trying to use absolute order. Using absolute order requires very precise time synchronization which is hard; using absolute order requires knowing when you have received all the reports of events that already happened which is hard. Determining a designated observer isn't typically easy, but having it determine the order it observes events is easy. If two events happen at a similar time it's typically not a big deal which one is considered first as long as all nodes will agree on the result --- let the designated observer just pick the first one it sees works pretty well. If your report takes an unexpectedly long time to make it to the designated observer, then it won't be first and you'll deal. Much better than trying to figure out unknowable questions of relativity. :P
deleted 14d ago
[deleted]
manesioz 14d ago
Some other classics (applied dist systems): - DDB: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf https://www.allthingsdistributed.com/files/amazon-dynamo-sos... - MapReduce: https://www.cs.princeton.edu/courses/archive/fall13/cos518/papers/mapreduce.pdf https://www.cs.princeton.edu/courses/archive/fall13/cos518/p... - Spark/RDDs: https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final138.pdf https://www.usenix.org/system/files/conference/nsdi12/nsdi12... - BigTable: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf https://static.googleusercontent.com/media/research.google.c...
- mjb 13d ago
  Worth mentioning that Dynamo (the classic 2007 paper) and DynamoDB (the modern AWS product) have fairly little in common architecturally. For DynamoDB, check out https://www.usenix.org/conference/atc22/presentation/elhemali https://www.usenix.org/conference/atc22/presentation/elhemal... https://www.usenix.org/conference/atc23/presentation/idziorek https://www.usenix.org/conference/atc23/presentation/idziore... and my analysis of the differences here https://brooker.co.za/blog/2025/08/15/dynamo-dynamodb-dsql.html https://brooker.co.za/blog/2025/08/15/dynamo-dynamodb-dsql.h...
  - manesioz 13d ago
    Nice distinction, thanks!
projectileboy 14d ago
Obligatory shout out to Morris and Kaashoek's class at MIT - they update the reading list every year, and it's always great: https://pdos.csail.mit.edu/6.824/ https://pdos.csail.mit.edu/6.824/
- AbbeFaria 13d ago
  I am going through this right now. I finished Lab 3. I also made my own notes about some of the papers they discuss, specifically Spanner. https://sudk1896.github.io/2026/09/03/Spanner-notes.html https://sudk1896.github.io/2026/09/03/Spanner-notes.html Highly recommend this course.
macintux 14d ago
I haven't updated this in quite a while, so probably more than a few broken links: my list of distributed systems reading lists. https://gist.github.com/macintux/6227368 https://gist.github.com/macintux/6227368
eliauelkouby 14d ago
[flagged]
prydt 14d ago
Some of these probably aren't exactly classics but I do love: - rendezvous hashing / consistent hashing - Hybrid logical clocks - "Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS" - "Scaling Replicated State Machines with Compartmentalization" (much more recent but really one of my favorite papers)
- jongjong 13d ago
  Rendezvous hashing is so simple and elegant. I implemented a library for rendezvous hashing with skeleton in order to get a similar performance as consistent hashing; it gets much more complicated and IMO loses some of the elegance once you add the skeleton. Most of the challenge is that the skeleton structure relies on a tree and so has to be rebalanced sometimes and this means that sometimes you have to move around more keys than ideal. The startegy you can use to perform the rebalancing can become very complicated. Though the 'virtual nodes' in consistent hashing also add a lot of complexity there.
mad44 13d ago
Here is my list: https://muratbuffalo.blogspot.com/2021/02/foundational-distributed-systems-papers.html https://muratbuffalo.blogspot.com/2021/02/foundational-distr...
codedump 13d ago
[dead]
jdw64 13d ago
I want to work on coding for a service large enough to involve distributed systems someday. I keep studying the theory, but still...
- AbbeFaria 13d ago
  Try doing the assignments from MIT 6.5840 Distributed Systems course by Morris and Kaashoek.
  - jdw64 13d ago
    Thank you. Since most of my work involves small to medium-scale projects, I really appreciate the advice. I will definitely look into it.
hbroom 13d ago
Reading this brings back memories of wrestling with eventual consistency. So much has evolved, yet fundamentals remain.
kwhitlock 13d ago
[dead]
samayashar 13d ago
> Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. The greatest anonymous dude alive.
- whizzter 13d ago
  18 years later the odds of him being dead has risen significantly.
mr_big_bowls 13d ago
[flagged]
halilBB 13d ago
[flagged]
markus_zhang 13d ago
I found myself fascinated by two topics -- Synchronization and Virtual File System in kernel land. Do they have similar websites? I know SunOS was the first one who implemented VFS and they wrote a white paper about it back in the 90s.

340 points by grep_it 14d ago

As always, lists like these don’t include Joe Armstrong's PhD thesis “Making reliable distributed systems in the presence of software errors” - http://erlang.org/download/armstrong_thesis_2003.pdf http://erlang.org/download/armstrong_thesis_2003.pdf

Suhinnall27 14d ago
Are there any other works that should also be included that you know of?
- FabHK 14d ago
  Not OP, but a good resource for distributed consensus specifically is Tim Roughgarden's YouTube playlist "Foundations of Blockchains" [0] (hear me out, despite the title - see below). It's 85 videos over 12 lectures, rigorous, very well explained (but assumes some CS fundamentals). Not original work, but gives the conceptual framework and background so that one can read these classic papers in context. Per-lecture reading lists are on the course page [1]. He also points at Elaine Shi's Foundations of Distributed Consensus and Blockchains [2] and Andrew Lewis-Pye's Consensus in 50 pages [2] as background, though these are more textbooks, not papers. Remarkably, the first 7 lectures deal with permissioned systems, recapitulating the classic results of consensus in distributed systems (Dolev Strong, FLP impossibility, CAP) - no blockchain in sight. This takes us to the state of the art at the end of the 1990's (with algorithms that can achieve consensus in the presence of byzantine failures, namely Byzantine Paxos and PBFT, though he discusses a modern variant, permissioned Tendermint from 2014). Lecture 8 stays permissioned and proves consistency and chain quality for the longest-chain rule. Only at Lecture 9, with proof of work, does anything specifically blockchain appear; then L10 block rewards and selfish mining, L11 transaction fee mechanism design; L12 proof-of-stake sybil resistance with the whole litany of attacks possible there. Very good series in my view, and shows how little technical merit this whole blockchain circus has - nearly all the great properties people tout (reliability, consistency, audibility, availability) can be achieved with good old permissioned tech more efficiently, with pretty instant and deterministic finality. Anyway, I found the series worth watching for the classical consensus material alone. [0] https://www.youtube.com/playlist?list=PLEGCF-WLh2RLOHv_xUGLqRts_9JxrckiA https://www.youtube.com/playlist?list=PLEGCF-WLh2RLOHv_xUGLq... [1] https://timroughgarden.github.io/fob21/ https://timroughgarden.github.io/fob21/ [2] https://elaineshi.com/docs/blockchain-book.pdf https://elaineshi.com/docs/blockchain-book.pdf [3] https://lewis-pye.com/2022/08/15/consensus-in-50-pages/ https://lewis-pye.com/2022/08/15/consensus-in-50-pages/
jermberj 14d ago
No disrespect meant to Mr. Armstrong, but it's possible it's never listed because it's basically a textbook. It's 295 pages. The rough average of all papers in OP is like 15 pages.
- vulcan01 14d ago
  His thesis is only slightly longer than typical PhD theses, I think.
  - derefr 14d ago
    Yes, but the other things in the OP list aren't theses, they're journal papers.
  - throwaway219450 14d ago
    I would say 300 is more than slightly longer. Varies by institution and style, but 100k words, 4-5 collated papers, 100-150 pages maximum are quite common. I would be concerned as an examiner if this came across my desk, more so if I read the colophon where the author comments that they intended to write their own typesetting system, before reading Knuth and wisely concluding that they were unlikely to do anything better than TeX. Top tier yak shaving there.
- moritz 14d ago
  One can skip the Erlang-specific things/the description of the programming language. Just the first 2 chapters (~30p) + the Conclusion (~10p) contain a lot of useful food for thought.
brcmthrowaway 14d ago
Does anyone use Elixir/Erlang anymore?
- appstorelottery 14d ago
  WhatsApp backend in Erlang + used in telecoms
  - brcmthrowaway 14d ago
    The "WhatsApp used Erlang" story was a decade ago, doubt it is true now.
    - toast0 14d ago
      There's still a lot of WhatsApp Erlang tooling being published, so I'm pretty sure it's mostly still Erlang. I think I still know a couple people who would share with me if it was rewritten, although I left in 2019. Erlang is simply the right language to build a chat server with, and it doesn't make sense to rewrite it in another language, even though Facebook did that with the server for Messenger. :P Certainly parts of the WhatsApp stack have changed considerably. No more FreeBSD / no more only a handful of OS processes per node, much less Mnesia (not sure if there's any Mnesia left... I don't get that level of information). I've seen signs that they may have returned to large nodes, so they might be back to millions of connections per node, but that was very much not the case when I left; connection counts had dropped on our FreeBSD nodes because we were doing a lot more on the chat channel and then again because the Facebook nodes we migrated to were so much smaller than our FreeBSD nodes.
    - Joel_Mckay 14d ago
      I doubt they changed out Erlang/Elixir, as it is mature backbone infrastructure. It has run many telecoms for over 30 years without issue. The problem is finding talent that knows both distributed systems, and Erlang/Elixir. But Erlang/OTP can replace a lot of expensive kludges. =3
      - 14d ago
Joel_Mckay 14d ago
reliable? we all wish... In distributed systems the fist lesson is resilience is more important. Spend enough time in a computer lab, and you will see things halt and catch fire on occasion. Especially if it has a bunch of GPUs pinning the utilization 24/7, or a cheap power supply in the cluster. =3

nylonstrung 14d ago

Lamport is the author of more than half of these, it's crazy how influential he is in this space In addition to making LaTex which has almost nothing to do with it

phtrivier 14d ago
It's the thing that baffles me the most with those people, the Knuths and Lamports and Carmarcks, and whatnot. It's not like they have light schedules - they do research, they have classes, they attendconference, and they have jobs, etc... And some benefit from tenure, which give them time to deeply focus on some topics. But I can't imagine how I would write tex in ten years in Pascal on archaic machines if I had all the time to myself. Doing that in the middle of understanding more computer science than my eyes would ever read ? What do they do with their time ? What do they don't do ? Are they able to skip the eating and pooping and sleeping and cleaning their house and picking up parcels at the post office and grocery shopping parts ? Or a proto Unix being written in three weeks. Concretely, what are the days of those three weeks made of ? Especially since it's famously when the spouse was NOT there to handle the housekeeping... I see not amount of "life hacks" and "atomic habits" and whatnot helping with that. But it's probably just as natural to them as biking - and you can't explain biking, I guess ?
- drfuchs 14d ago
  A favorite Knuth story to illustrate: He was re-writing the 8080 code for the processor that ran our new Alphatype CRS Phototypesetter, since the manufacturer's code wasn't suitable. Real-time, 7 levels of simultaneous interrupt stuff, since it controlled two stepper motors that moved the lens around the photographic paper, plus four custom font outline-tracing S100 cards that flashed vertical segments of characters at just the right moment on the CRT that the lens then focused onto the paper. No debugability other than a 4x4 keyboard and a 15(?) character display. I was responsible for the code on the other end of the RS232 port that connected it to the DEC mainframe, sending down character outlines on the fly to the very limited memory on the 8080, along with the properly-sorted character placement info ultimately from TeX. Anyway, we'd been doing morning, noon, and night debugging sessions together for a number of days. On maybe the 3rd morning, I arrived at his office and was speaking with his secretary of many years, Phyllis Winkler, when Knuth came in. He handed her a stack of maybe a dozen or two pages, saying "Here's a paper I wrote; please type it in." When? When did he write it? It's still a mystery to me.

bestpickle 14d ago

[dead]

Aditya_0315 14d ago

[flagged]

mjb 14d ago

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 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/renesse/renesse.pdf 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-perspective-2006-invited-talk/ 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).

grep_it 14d ago
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 https://lamport.azurewebsites.net 1: https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks
ksambhi 14d ago
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”?

bigcat12345678 14d ago

I am a Lamport admirer. I gradually realized that Lamport is more of the godfather of distributed system than Hinton is to deep learning. Lamport is less prominent than Shannon is to information theory. Shannon is the closest to any title of "gold-like" figure to a scientific discipline of universal relevance in modern society. Lamport specifically revealed a philosophical connections between computer systems and physics, in the parallel of distributed consensus to relativity theory. To me, the enlightenment is that, the relations between events happening in a distributed system, is more fundamental than their absolute ordering, thus the central role of an "observer". I haven't really analyzed if this realization is from Lamport's papers, or my general reading and thinking, but I am moderately confident that general readings are heavily influenced by Lamport's papers, or can be traced back to be compatible with Lamport's thinking. I have not seriously study if this connection is valid in depth, which might be another pure amateur speculation of mine. One thing I think Lamport falls short is that his writing is not easy to read and understand. I unconciously feel that Lamport (and Dario from Anthropic) probably share a hidden sense of intellectual supriority grew from their own experience throughout their career. So their writing (and Dario's gospel) all share a unchangable sense of narration from their own delicate and graceful ideas, much less of faciliating the understanding to their audience. In this cateogry, Shannon is abosolutely superior in any measure, in his writing, ideas are so naturally presented, although the implications of the ideas remain elusive due to the inherent depth. Also, among the 3 prominent figures of modern AI: Hinton/Bengio are more like Shannon, Lecun is closer to Lamport. Enough random rambling. Lamport, as indicated by the outweight presence in this list, is no doubt the single most important scientist in distributed systems.

toast0 14d ago
> the relations between events happening in a distributed system, is more fundamental than their absolute ordering The important thing in most distributed systems is having an order. Having a single observer serialize events as it receives them is so much more tractable than trying to use absolute order. Using absolute order requires very precise time synchronization which is hard; using absolute order requires knowing when you have received all the reports of events that already happened which is hard. Determining a designated observer isn't typically easy, but having it determine the order it observes events is easy. If two events happen at a similar time it's typically not a big deal which one is considered first as long as all nodes will agree on the result --- let the designated observer just pick the first one it sees works pretty well. If your report takes an unexpectedly long time to make it to the designated observer, then it won't be first and you'll deal. Much better than trying to figure out unknowable questions of relativity. :P

deleted 14d ago

[deleted]

manesioz 14d ago

Some other classics (applied dist systems): - DDB: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf https://www.allthingsdistributed.com/files/amazon-dynamo-sos... - MapReduce: https://www.cs.princeton.edu/courses/archive/fall13/cos518/papers/mapreduce.pdf https://www.cs.princeton.edu/courses/archive/fall13/cos518/p... - Spark/RDDs: https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final138.pdf https://www.usenix.org/system/files/conference/nsdi12/nsdi12... - BigTable: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf https://static.googleusercontent.com/media/research.google.c...

mjb 13d ago
Worth mentioning that Dynamo (the classic 2007 paper) and DynamoDB (the modern AWS product) have fairly little in common architecturally. For DynamoDB, check out https://www.usenix.org/conference/atc22/presentation/elhemali https://www.usenix.org/conference/atc22/presentation/elhemal... https://www.usenix.org/conference/atc23/presentation/idziorek https://www.usenix.org/conference/atc23/presentation/idziore... and my analysis of the differences here https://brooker.co.za/blog/2025/08/15/dynamo-dynamodb-dsql.html https://brooker.co.za/blog/2025/08/15/dynamo-dynamodb-dsql.h...
- manesioz 13d ago
  Nice distinction, thanks!

projectileboy 14d ago

Obligatory shout out to Morris and Kaashoek's class at MIT - they update the reading list every year, and it's always great: https://pdos.csail.mit.edu/6.824/ https://pdos.csail.mit.edu/6.824/

AbbeFaria 13d ago
I am going through this right now. I finished Lab 3. I also made my own notes about some of the papers they discuss, specifically Spanner. https://sudk1896.github.io/2026/09/03/Spanner-notes.html https://sudk1896.github.io/2026/09/03/Spanner-notes.html Highly recommend this course.

macintux 14d ago

I haven't updated this in quite a while, so probably more than a few broken links: my list of distributed systems reading lists. https://gist.github.com/macintux/6227368 https://gist.github.com/macintux/6227368

eliauelkouby 14d ago

[flagged]

prydt 14d ago

Some of these probably aren't exactly classics but I do love: - rendezvous hashing / consistent hashing - Hybrid logical clocks - "Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS" - "Scaling Replicated State Machines with Compartmentalization" (much more recent but really one of my favorite papers)

jongjong 13d ago
Rendezvous hashing is so simple and elegant. I implemented a library for rendezvous hashing with skeleton in order to get a similar performance as consistent hashing; it gets much more complicated and IMO loses some of the elegance once you add the skeleton. Most of the challenge is that the skeleton structure relies on a tree and so has to be rebalanced sometimes and this means that sometimes you have to move around more keys than ideal. The startegy you can use to perform the rebalancing can become very complicated. Though the 'virtual nodes' in consistent hashing also add a lot of complexity there.

mad44 13d ago

Here is my list: https://muratbuffalo.blogspot.com/2021/02/foundational-distributed-systems-papers.html https://muratbuffalo.blogspot.com/2021/02/foundational-distr...

codedump 13d ago

[dead]

jdw64 13d ago

I want to work on coding for a service large enough to involve distributed systems someday. I keep studying the theory, but still...

AbbeFaria 13d ago
Try doing the assignments from MIT 6.5840 Distributed Systems course by Morris and Kaashoek.
- jdw64 13d ago
  Thank you. Since most of my work involves small to medium-scale projects, I really appreciate the advice. I will definitely look into it.

hbroom 13d ago

Reading this brings back memories of wrestling with eventual consistency. So much has evolved, yet fundamentals remain.

kwhitlock 13d ago

[dead]

samayashar 13d ago

> Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. The greatest anonymous dude alive.

whizzter 13d ago
18 years later the odds of him being dead has risen significantly.

mr_big_bowls 13d ago

[flagged]

halilBB 13d ago

[flagged]

markus_zhang 13d ago

I found myself fascinated by two topics -- Synchronization and Virtual File System in kernel land. Do they have similar websites? I know SunOS was the first one who implemented VFS and they wrote a white paper about it back in the 90s.