If this is your introduction to Murat's blog, be sure to browse through some of the rest: http://muratbuffalo.blogspot.com/ He's been blogging about distributed systems, and papers, at an amazing rate for a long time. His paper summaries are especially interesting an insightful.
twoodfin 1159 days ago [-]
Great list. It might not be foundational so much as part of the sub-basement, but I’d include “A Note on Distributed Computing”[1]. Distributed systems design needs all the cautionary tales it can get.
EDIT: This paper (1994) describes NFS, in the course of criticizing its design, as “arguably the most successful distributed application that has been produced”. I wonder which application earns that superlative in 2021?
Probably one of the network protocols underlying the web. Maybe TLS with X.509 certs and the whole CA structure? Or DNS, or SMTP which are also distributed by design.
If it’s something trendier we’re looking for, might be Kubernetes.
From far enough away, every consumer application is a distributed system, not just the obvious ones like G Docs, but also Twitter, Amazon, Netflix.
So I guess it depends on your scope! The computing world is much more distributed (albeit not decentralized) today than it was in ‘94.
It’s one of those beautiful ideas that isn’t practical for Serious Work™ (i.e. centralized computation), because it’s hard to make SLA-style guarantees about a system that communicates by gossip.
But it does seem to mimic nature in that while it’s not optimal for performance it’s quite robust to things like highly dynamic connectivity between nodes. Maybe one day it’ll have practical value, when the world is a bit more decentralized! :)
Oh, the virtual time paper is cool, never came across that before. Has it been particularly influential? What are the disadvantages? I guess there's no real mention of fault tolerance/message loss for one?
waynesonfire 1159 days ago [-]
Thanks for compiling this list. Looks great. But, eight papers about Paxos and no mention of Raft?
hardwaresofton 1159 days ago [-]
Shameless plug, I have a list of even more paxos papers that does include Raft :)
> Papers-we-love > Distributed Systems: https://github.com/papers-we-love/papers-we-love/tree/master...
> awesome-distributed-systems also has many links to theory: https://github.com/theanalyst/awesome-distributed-systems
And links to more lists of distributed systems papers under "Meta Lists": https://github.com/theanalyst/awesome-distributed-systems#me...
In reviewing this awesome list, today I learned about this playlist: "MIT 6.824 Distributed Systems (Spring 2020)" https://youtube.com/playlist?list=PLrw6a1wE39_tb2fErI4-WkMbs...
> awesome-bigdata lists a number of tools: https://github.com/onurakpolat/awesome-bigdata
EDIT: This paper (1994) describes NFS, in the course of criticizing its design, as “arguably the most successful distributed application that has been produced”. I wonder which application earns that superlative in 2021?
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7...
If it’s something trendier we’re looking for, might be Kubernetes.
From far enough away, every consumer application is a distributed system, not just the obvious ones like G Docs, but also Twitter, Amazon, Netflix.
So I guess it depends on your scope! The computing world is much more distributed (albeit not decentralized) today than it was in ‘94.
I remember thinking it was a really cool result in college.
Further, I’m not sure if there’s a good paper for it, but the Gossip protocols are another fun rabbit hole.
https://en.m.wikipedia.org/wiki/Gossip_protocol
It’s one of those beautiful ideas that isn’t practical for Serious Work™ (i.e. centralized computation), because it’s hard to make SLA-style guarantees about a system that communicates by gossip.
But it does seem to mimic nature in that while it’s not optimal for performance it’s quite robust to things like highly dynamic connectivity between nodes. Maybe one day it’ll have practical value, when the world is a bit more decentralized! :)
Implementing Atomic Actions on Decentralized Data by David Reed
https://pages.cs.wisc.edu/~remzi/Classes/739/Spring2003/Pape...
Virtual Time by David Jefferson
http://cobweb.cs.uga.edu/~maria/pads/papers/p404-jefferson.p...
https://vadosware.io/post/paxosmon-gotta-concensus-them-all/
I'm missing some that were suggested to me by a HN member (judofyr), and I haven't updated the post so will put them down here:
- Compartmentalized Paxos (https://mwhittaker.github.io/publications/compartmentalized_...)
- Matchmaker Paxos (https://mwhittaker.github.io/publications/matchmaker_paxos.p...)
- PigPaxos (https://arxiv.org/abs/2003.07760)
- Linearizable Quorum reads in Paxos (https://www.usenix.org/system/files/hotstorage19-paper-chara...)