Foundational Distributed Systems Papers

From "Ask HN: Learning about distributed systems?" https://news.ycombinator.com/item?id=23932271 :

> 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

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.

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.7...

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.

Another one for the list: 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

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! :)

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

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/Pape...

Virtual Time by David Jefferson

http://cobweb.cs.uga.edu/~maria/pads/papers/p404-jefferson.p...

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?

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

Shameless plug, I have a list of even more paxos papers that does include Raft :)

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...)

The Raft paper is there. It's the first paper under the "Expository papers and blog posts" section

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_a...

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