"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.)
"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).
bigcat12345678 [3 hidden]5 mins 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.
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.
moritz [3 hidden]5 mins 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.
vulcan01 [3 hidden]5 mins ago
His thesis is only slightly longer than typical PhD theses, I think.
throwaway219450 [3 hidden]5 mins ago
I would say 300 is more than slightly longer. Varies by institution 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 began to write their own typesetting system, before wisely reading Knuth and deciding that they were unlikely to do anything better than TeX.
derefr [3 hidden]5 mins ago
Yes, but the other things in the OP list aren't theses, they're journal papers.
Suhinnall27 [3 hidden]5 mins ago
Are there any other works that should also be included that you know of?
FabHK [3 hidden]5 mins 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.
The "WhatsApp used Erlang" story was a decade ago, doubt it is true now.
toast0 [3 hidden]5 mins 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
nylonstrung [3 hidden]5 mins 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 [3 hidden]5 mins 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 ?
HN.zip
"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).
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.
Just the first 2 chapters (~30p) + the Conclusion (~10p) contain a lot of useful food for thought.
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 began to write their own typesetting system, before wisely reading Knuth and deciding that they were unlikely to do anything better than TeX.
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_xUGLq...
[1] https://timroughgarden.github.io/fob21/
[2] https://elaineshi.com/docs/blockchain-book.pdf
[3] https://lewis-pye.com/2022/08/15/consensus-in-50-pages/
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
In addition to making LaTex which has almost nothing to do with it
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 ?