3 ms·

One of many timeless works from Butler Lampson. The patterns are still widely in use to this day. The trade offs between lease times and availability are so cle

One of many timeless works from Butler Lampson. The patterns are still widely in use to this day. The trade offs between lease times and availability are so clearly put, reading this could save a lot of hard earned lessons. This paper is such a great top-down explanation of consensus and Paxos. If I could go back in time I’d start off my interest in distributed systems by reading just this paper. That would have been a much better approach than feeling like I’m getting beat in the face over and over again by a water mill. The path I took was like many others: You see some distributed database that gets you really excited. CAP leads to Paxos, that leads to FLP, you rebel for a few months by getting interested in CRDTs, and then you have a bunch of hang overs from papers not using the term consistency consistently. The rest of it can best be drawn by giving a toddler a box of crayons. Just read this instead.

avinassh 6y ago
> If I could go back in time I’d start off my interest in distributed systems by reading just this paper. do you have more recommendations for such papers in distributed systems?
- inopinatus 6y ago
  three favourite bookmarks of mine: Time, Clocks, and the Ordering of Events in a Distributed System, Lamport. (1978) http://lamport.azurewebsites.net/pubs/time-clocks.pdf http://lamport.azurewebsites.net/pubs/time-clocks.pdf Impossibility of Distributed Consensus with One Faulty Process, Fischer, Lynch, Patterson. (1985) http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofConsensus.pdf http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofCons... A History Of The Virtual Synchrony Replication Model, Birman. (2010) http://www.cs.cornell.edu/ken/History.pdf http://www.cs.cornell.edu/ken/History.pdf
- rubiquity 6y ago
  There are a lot of these lists on the internet and they're all personal, but since you asked, here would be mine. This list is just a starting point. If I started over, I would focus solely on building the intuition of time and then start with the strictest consistency models and work my way down. I'd ignore persistence entirely and every time state is mentioned I'd just picture an in-memory number or tuple. Much like the rest of computing, everything we're doing today is based on the original ideas of the 70s/80/90s, just with more sharding. A lot more sharding. - Time, Clocks, and the Ordering of Events in a Distributed System[0] - The many faces of consistency[1] - Understanding Replication in Databases and Distributed Systems[2] - Viewstamped Replication Revisited[3] - Consensus on Transaction Commit[4] A lot of people recommend the FLP, CAP, and popular industry papers such as Chubby and Dynamo but I don't find them very useful in the beginning. CAP is too vague to be useful anymore and it's much better to speak in terms of specific consistency models instead. The FLP paper is certainly worth reading later on, but all you need to know in the beginning is that reaching consensus (termination and agreement) over networks with unbounded delivery times (the Internet) is impossible. Once you understand this, or don't understand it but have convinced yourself to accept it, the reasons for why fault detectors enter the picture is a lot easier to digest. I prefer Viewstamped Replication as a deep dive into learning consensus because I find it to be a lot more concrete in contrast to Paxos. 0 - https://lamport.azurewebsites.net/pubs/time-clocks.pdf https://lamport.azurewebsites.net/pubs/time-clocks.pdf 1 - http://sites.computer.org/debull/A16mar/p3.pdf http://sites.computer.org/debull/A16mar/p3.pdf 2 - http://www-users.cselabs.umn.edu/classes/Spring-2018/csci8980/Papers/ProcessReplication/Understanding-Replication-icdcs2000.pdf http://www-users.cselabs.umn.edu/classes/Spring-2018/csci898... 3 - http://www.pmg.lcs.mit.edu/papers/vr-revisited.pdf http://www.pmg.lcs.mit.edu/papers/vr-revisited.pdf 4 - https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf https://lamport.azurewebsites.net/video/consensus-on-transac...

avinassh 6y ago

> If I could go back in time I’d start off my interest in distributed systems by reading just this paper. do you have more recommendations for such papers in distributed systems?

inopinatus 6y ago
three favourite bookmarks of mine: Time, Clocks, and the Ordering of Events in a Distributed System, Lamport. (1978) http://lamport.azurewebsites.net/pubs/time-clocks.pdf http://lamport.azurewebsites.net/pubs/time-clocks.pdf Impossibility of Distributed Consensus with One Faulty Process, Fischer, Lynch, Patterson. (1985) http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofConsensus.pdf http://macs.citadel.edu/rudolphg/csci604/ImpossibilityofCons... A History Of The Virtual Synchrony Replication Model, Birman. (2010) http://www.cs.cornell.edu/ken/History.pdf http://www.cs.cornell.edu/ken/History.pdf
rubiquity 6y ago
There are a lot of these lists on the internet and they're all personal, but since you asked, here would be mine. This list is just a starting point. If I started over, I would focus solely on building the intuition of time and then start with the strictest consistency models and work my way down. I'd ignore persistence entirely and every time state is mentioned I'd just picture an in-memory number or tuple. Much like the rest of computing, everything we're doing today is based on the original ideas of the 70s/80/90s, just with more sharding. A lot more sharding. - Time, Clocks, and the Ordering of Events in a Distributed System[0] - The many faces of consistency[1] - Understanding Replication in Databases and Distributed Systems[2] - Viewstamped Replication Revisited[3] - Consensus on Transaction Commit[4] A lot of people recommend the FLP, CAP, and popular industry papers such as Chubby and Dynamo but I don't find them very useful in the beginning. CAP is too vague to be useful anymore and it's much better to speak in terms of specific consistency models instead. The FLP paper is certainly worth reading later on, but all you need to know in the beginning is that reaching consensus (termination and agreement) over networks with unbounded delivery times (the Internet) is impossible. Once you understand this, or don't understand it but have convinced yourself to accept it, the reasons for why fault detectors enter the picture is a lot easier to digest. I prefer Viewstamped Replication as a deep dive into learning consensus because I find it to be a lot more concrete in contrast to Paxos. 0 - https://lamport.azurewebsites.net/pubs/time-clocks.pdf https://lamport.azurewebsites.net/pubs/time-clocks.pdf 1 - http://sites.computer.org/debull/A16mar/p3.pdf http://sites.computer.org/debull/A16mar/p3.pdf 2 - http://www-users.cselabs.umn.edu/classes/Spring-2018/csci8980/Papers/ProcessReplication/Understanding-Replication-icdcs2000.pdf http://www-users.cselabs.umn.edu/classes/Spring-2018/csci898... 3 - http://www.pmg.lcs.mit.edu/papers/vr-revisited.pdf http://www.pmg.lcs.mit.edu/papers/vr-revisited.pdf 4 - https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf https://lamport.azurewebsites.net/video/consensus-on-transac...