-
Notifications
You must be signed in to change notification settings - Fork 39
/
README.html
114 lines (114 loc) · 7.99 KB
/
README.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>index</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.line-block{white-space: pre-line;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="distributed-systems-engineering-notes-6.824-spring-2015">Distributed Systems Engineering notes (6.824, Spring 2015)</h1>
<h2 id="lectures">Lectures</h2>
<p>Lecture notes from 6.824, taught by <a href="http://pdos.csail.mit.edu/rtm/">Prof. Robert T. Morris</a>. These lecture notes are slightly modified from the ones posted on the 6.824 <a href="http://nil.csail.mit.edu/6.824/2015/schedule.html">course website</a>.</p>
<ul>
<li>Lecture 1: <a href="l01-intro.html">Introduction</a>: distributed system definition, motivations, architecture, implementation, performance, fault-tolerance, consistency, MapReduce</li>
<li>Lecture 2: <a href="l02-rpc.html">Remote Procedure Calls (RPCs)</a>: RPC overview, marshalling, binding, threads, “at-least-once”, “at-most-once”, “exactly once”, Go’s RPC, thread synchronization</li>
<li>Lecture 3: <a href="l03-fault-tolerance.html">Fault tolerance</a>: primary-backup replication, state transfer, “split-brain”, Remus (NSDI 2008),<br />
</li>
<li>Lecture 4: <a href="l04-more-primary-backup.html">Flat datacenter storage</a>: flat datacenter storage, bisection bandwidth, striping</li>
<li>Lecture 5: <a href="l05-paxos.html">Paxos</a>: Paxos, consensus algorithms
<ul>
<li><a href="paxos-algorithm.html">Paxos algorithm description</a></li>
</ul></li>
<li>Lecture 6: <a href="l06-raft.html">Raft</a>: Raft, a more understandable consensus algorithm</li>
<li>Lecture 7: <strong>Google Go</strong> <a href="l07-go.html"><em>guest lecture</em></a> by Russ Cox</li>
<li>Lecture 8: <a href="l08-harp.html">Harp</a>: distributed file system, “the UPS trick”, witnesses</li>
<li>Lecture 9: <a href="l09-dist-comp-seq-consistency.html">IVY</a>: distributed shared memory, sequential consistency</li>
<li>Lecture 10: <a href="l10-treadmarks.html">TreadMarks</a>: userspace distributed shared memory system, vector timestamps, release consistency (lazy/eager), false sharing, write amplification</li>
<li>Lecture 11: <a href="l11-ficus.html">Ficus</a>: optimistic concurrency control, vector timestamps, conflict resolution</li>
<li>Lecture 12: <a href="l12-bayou.html">Bayou</a>: disconnected operation, eventual consistency, Bayou</li>
<li>Lecture 13: <a href="l13-mapreduce.html">MapReduce</a>: MapReduce, scalability, performance</li>
<li>Lecture 14: <strong>Spark</strong> <a href="l14-spark.html"><em>guest lecture</em></a> by Matei Zaharia: Resilient Distributed Datasets, Spark</li>
<li>Lecture 15: <strong>Spanner</strong> <a href="l15-spanner.html"><em>guest lecture</em></a> by Wilson Hsieh, Google: Spanner, distributed database, clock skew</li>
<li>Lecture 16: <a href="l16-memcached.html">Memcache at Facebook</a>: web app scalability, look-aside caches, Memcache</li>
<li>Lecture 17: <a href="l17-pnuts.html">PNUTS Yahoo!</a>: distributed key-value store, atomic writes</li>
<li>Lecture 18: <a href="l18-dynamo.html">Dynamo</a>: distributed key-value store, eventual consistency</li>
<li>Lecture 19: <strong>HubSpot</strong> <a href="l19-hubspot.html"><em>guest lecture</em></a></li>
<li>Lecture 20: <a href="l20-argus.html">Two phase commit (2PC)</a>: two-phase commit, Argus</li>
<li>Lecture 21: <a href="l21-thor.html">Optimistic concurrency control</a></li>
<li>Lecture 22: <a href="l22-peer-to-peer.html">Peer-to-peer, trackerless Bittorrent and DHTs</a>: Chord, routing</li>
<li>Lecture 23: <a href="l23-bitcoin.html">Bitcoin</a>: verifiable public ledgers, proof-of-work, double spending</li>
</ul>
<h2 id="lectures-form-other-years">Lectures form other years</h2>
<ul>
<li><a href="extra/pbft.html">Practical Byzantine Fault Tolerance (PBFT)</a>
<ul>
<li>Other years: <a href="original-notes/pbft-2012.txt">[2012]</a>, <a href="original-notes/pbft-2011.txt">[2011]</a>, <a href="original-notes/pbft-2010.txt">[2010]</a>, <a href="original-notes/pbft-2009.txt">[2009]</a>, <a href="original-notes/pbft-2001.txt">[2001]</a>, <a href="original-notes/pbft.ppt">[PPT]</a></li>
</ul></li>
</ul>
<h2 id="labs">Labs</h2>
<ul>
<li>Lab 1: MapReduce, <a href="lab1/index.html">[assign]</a></li>
<li>Lab 2: A fault-tolerant key/value service, <a href="lab2/index.html">[assign]</a>, <a href="lab2/notes.html">[notes]</a></li>
<li>Lab 3: Paxos-based Key/Value Service, <a href="lab3/index.html">[assign]</a>, <a href="lab3/notes.html">[notes]</a></li>
<li>Lab 4: Sharded Key/Value Service, <a href="lab4/index.html">[assign]</a>, <a href="lab4/notes.html">[notes]</a></li>
<li>Lab 5: Persistent Key/Value Service, <a href="lab5/index.html">[assign]</a></li>
</ul>
<h2 id="papers">Papers</h2>
<p>Papers we read in 6.824 (<a href="papers/">directory here</a>):</p>
<ol type="1">
<li><a href="papers/mapreduce.pdf">MapReduce</a></li>
<li><a href="papers/remus.pdf">Remus</a></li>
<li><a href="papers/fds.pdf">Flat datacenter storage</a></li>
<li><a href="papers/paxos-simple.pdf">Paxos</a></li>
<li><a href="papers/raft-atc14.pdf">Raft</a></li>
<li><a href="papers/bliskov-harp.pdf">Harp</a></li>
<li><a href="papers/li-dsm.pdf">Shared virtual memory</a></li>
<li><a href="papers/keleher-treadmarks.pdf">TreadMarks</a></li>
<li><a href="papers/ficus.pdf">Ficus</a></li>
<li><a href="papers/bayou-conflicts.pdf">Bayou</a></li>
<li><a href="papers/zaharia-spark.pdf">Spark</a></li>
<li><a href="papers/spanner.pdf">Spanner</a></li>
<li><a href="papers/memcache-fb.pdf">Memcached at Facebook</a></li>
<li><a href="papers/cooper-pnuts.pdf">PNUTS</a></li>
<li><a href="papers/dynamo.pdf">Dynamo</a></li>
<li><a href="papers/akamai.pdf">Akamai</a></li>
<li><a href="papers/argus88.pdf">Argus</a>, <a href="papers/guardians-and-actions-liskov.pdf">Guardians and actions</a></li>
<li><a href="papers/kademlia.pdf">Kademlia</a></li>
<li><a href="papers/bitcoin.pdf">Bitcoin</a></li>
<li><a href="papers/katabi-analogicfs.pdf">AnalogicFS</a></li>
</ol>
<p>Other papers:</p>
<ol type="1">
<li><a href="papers/flp.pdf">Impossibility of Distributed Consensus with One Faulty Process</a>
<ul>
<li>See page 5, slide 10 <a href="stumbled/flp-consensus.pdf">here</a> to understand Lemma 1 (commutativity) faster</li>
<li>See <a href="http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/">this article here</a> for an alternative explanation.</li>
</ul></li>
<li><a href="papers/pbft.pdf">Practical Byzantine Fault Tolerance (PBFT)</a>
<ul>
<li>See <a href="http://the-paper-trail.org/blog/barbara-liskovs-turing-award-and-byzantine-fault-tolerance/#more-211">discussion here on PBFT</a>.</li>
</ul></li>
</ol>
<h2 id="stumbled-upon">Stumbled upon</h2>
<ol type="1">
<li><a href="http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html">A brief history of consensus, 2PC and transaction commit</a></li>
<li><a href="http://the-paper-trail.org/blog/distributed-systems-theory-for-the-distributed-systems-engineer/">Distributed systems theory for the distributed systems engineer</a></li>
<li><a href="http://book.mixu.net/distsys/">Distributed Systems: For fun and Profit</a></li>
<li><a href="https://codahale.com/you-cant-sacrifice-partition-tolerance/">You can’t choose CA out of CAP</a>, or “You can’t sacrifice partition tolerance”</li>
<li><a href="https://www.somethingsimilar.com/2013/01/14/notes-on-distributed-systems-for-young-bloods/">Notes on distributed systems for young bloods</a></li>
<li><a href="stumbled/paxos-explained-from-scratch.pdf">Paxos Explained From Scratch</a></li>
</ol>
<h2 id="quizzes">Quizzes</h2>
<p>Prep for quiz 1 <a href="exams/quiz1/quiz1.html">here</a></p>
</body>
</html>