4 ms·

Foundational Distributed Systems Papers

253 points by mastabadtomm 6y ago

westurner 6y ago
From "Ask HN: Learning about distributed systems?" https://news.ycombinator.com/item?id=23932271 https://news.ycombinator.com/item?id=23932271 : > Papers-we-love > Distributed Systems: https://github.com/papers-we-love/papers-we-love/tree/master/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 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#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-WkMbsvGQk9_UB https://youtube.com/playlist?list=PLrw6a1wE39_tb2fErI4-WkMbs... > awesome-bigdata lists a number of tools: https://github.com/onurakpolat/awesome-bigdata https://github.com/onurakpolat/awesome-bigdata
mjb 6y ago
If this is your introduction to Murat's blog, be sure to browse through some of the rest: http://muratbuffalo.blogspot.com/ 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.
swyx 6y ago
See also Distributed Systems Reading List: https://dancres.github.io/Pages/ https://dancres.github.io/Pages/
- deleted 6y ago
  [deleted]
waynesonfire 6y ago
Thanks for compiling this list. Looks great. But, eight papers about Paxos and no mention of Raft?
- hardwaresofton 6y ago
  Shameless plug, I have a list of even more paxos papers that does include Raft :) https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ 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_consensus.pdf https://mwhittaker.github.io/publications/compartmentalized_...) - Matchmaker Paxos (https://mwhittaker.github.io/publications/matchmaker_paxos.pdf https://mwhittaker.github.io/publications/matchmaker_paxos.p...) - PigPaxos (https://arxiv.org/abs/2003.07760 https://arxiv.org/abs/2003.07760) - Linearizable Quorum reads in Paxos (https://www.usenix.org/system/files/hotstorage19-paper-charapko.pdf https://www.usenix.org/system/files/hotstorage19-paper-chara...)
- reubenbond 6y ago
  The Raft paper is there. It's the first paper under the "Expository papers and blog posts" section
kerneltime 6y ago
I find this paper to be one of the earliest and one from which other consensus algos can be derived: https://en.wikipedia.org/wiki/Shared_register#Implementing_an_atomic_SWSR_register_in_a_message_passing_system https://en.wikipedia.org/wiki/Shared_register#Implementing_a...
twoodfin 6y 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? [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7628 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7...
- gen220 6y ago
  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.
CaliforniaKarl 6y ago
I'd also add https://jepsen.io/consistency https://jepsen.io/consistency & https://jepsen.io/analyses https://jepsen.io/analyses. Of course they're not foundational, but are also good to have on-hand!
colllectorof 6y ago
Not sure if "foundational", but I would add these because they have interesting mental models: Implementing Atomic Actions on Decentralized Data by David Reed https://pages.cs.wisc.edu/~remzi/Classes/739/Spring2003/Papers/p3-reed.pdf 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.pdf http://cobweb.cs.uga.edu/~maria/pads/papers/p404-jefferson.p...
- anonymousDan 6y ago
  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?
gen220 6y ago
Another one for the list: https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pd... 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 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! :)

253 points by mastabadtomm 6y ago

From "Ask HN: Learning about distributed systems?" https://news.ycombinator.com/item?id=23932271 https://news.ycombinator.com/item?id=23932271 : > Papers-we-love > Distributed Systems: https://github.com/papers-we-love/papers-we-love/tree/master/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 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#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-WkMbsvGQk9_UB https://youtube.com/playlist?list=PLrw6a1wE39_tb2fErI4-WkMbs... > awesome-bigdata lists a number of tools: https://github.com/onurakpolat/awesome-bigdata https://github.com/onurakpolat/awesome-bigdata

mjb 6y ago

If this is your introduction to Murat's blog, be sure to browse through some of the rest: http://muratbuffalo.blogspot.com/ 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.

swyx 6y ago

See also Distributed Systems Reading List: https://dancres.github.io/Pages/ https://dancres.github.io/Pages/

deleted 6y ago
[deleted]

waynesonfire 6y ago

Thanks for compiling this list. Looks great. But, eight papers about Paxos and no mention of Raft?

hardwaresofton 6y ago
Shameless plug, I have a list of even more paxos papers that does include Raft :) https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ 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_consensus.pdf https://mwhittaker.github.io/publications/compartmentalized_...) - Matchmaker Paxos (https://mwhittaker.github.io/publications/matchmaker_paxos.pdf https://mwhittaker.github.io/publications/matchmaker_paxos.p...) - PigPaxos (https://arxiv.org/abs/2003.07760 https://arxiv.org/abs/2003.07760) - Linearizable Quorum reads in Paxos (https://www.usenix.org/system/files/hotstorage19-paper-charapko.pdf https://www.usenix.org/system/files/hotstorage19-paper-chara...)
reubenbond 6y ago
The Raft paper is there. It's the first paper under the "Expository papers and blog posts" section

kerneltime 6y ago

I find this paper to be one of the earliest and one from which other consensus algos can be derived: https://en.wikipedia.org/wiki/Shared_register#Implementing_an_atomic_SWSR_register_in_a_message_passing_system https://en.wikipedia.org/wiki/Shared_register#Implementing_a...

twoodfin 6y 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? [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7628 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7...

gen220 6y ago
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.

CaliforniaKarl 6y ago

I'd also add https://jepsen.io/consistency https://jepsen.io/consistency & https://jepsen.io/analyses https://jepsen.io/analyses. Of course they're not foundational, but are also good to have on-hand!

colllectorof 6y ago

Not sure if "foundational", but I would add these because they have interesting mental models: Implementing Atomic Actions on Decentralized Data by David Reed https://pages.cs.wisc.edu/~remzi/Classes/739/Spring2003/Papers/p3-reed.pdf 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.pdf http://cobweb.cs.uga.edu/~maria/pads/papers/p404-jefferson.p...

anonymousDan 6y ago
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?

gen220 6y ago

Another one for the list: https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pd... 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 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! :)