Date
|
Lecture
|
References
|
Overview
and Background
|
Jan 3rd
|
Course Overview
(slides adapted from Prof. Martin Van Steen's
original
slides with consent)
|
|
Jan 7th
|
Course Overview [Continued]
|
1) RPC in C (link)
2) Java RMI (link)
|
Information Storage and Retrieval
(Gossiping, P2P Networks, DHTs)
|
Jan 8th
|
Epidemic
Based Algorithms |
Epidemic
Algorithms for Replicated Database Maintenance |
Jan 14th
|
Gossip
Based Algorithms
|
A
Gossip-Style Failure Detection Service
 Youtube
video (gossip and epidemic based protocols)
|
Jan 19th
Jan 21st
|
Napster and Gnutella
|
Napster
and Gnutella: A Comparison of Two Popular Peer to Peer
Protocols |
Pastry
DHT
|
Pastry:
Scalable, decentralized object location and
routing for large-scale peer-to-peer systems
Youtube
video |
Jan 22nd
|
Chord
DHT
|
Chord:
A Scalable Peer-to-peer Lookup Service for Internet
Applications |
Jan 24th
|
Chord DHT
|
|
Jan 28th
Jan 29th
|
Freenet
|
Freenet:
A Distributed Anonymous Information Storage and Retrieval
System
|
Jan 31st
|
BitTorrent
|
1.
Wikipedia page
2.
Dissecting BitTorrent: Five Months in a Torrent's Lifetime
3.
Kademlia: A Peer-to-Peer Information System Based on the
XOR Metric
|
Distributed Algorithms
|
Jan 31st
Feb 7th
|
Logical
Clocks, Physical Clocks, GPS
|
1.
Time, Clocks, and the Ordering of Events in a Distributed
System
Berkely
algorithm link
|
Feb 11th
|
Lamport's
Mutual Exclusion Algorithm
|
|
Feb 12th
|
Ricart
Agarwala Algorithm
Maekawa's Algorithm
|
1.
A root(N) Algorithm for Mutual Exclusion in Decentralized
Systems (paper on Maekawa's Algorithm)
|
Feb 18th
|
Token
based Mutual Exclusion
|
|
Feb 19th
|
Leader
Election
|
|
Feb 21st
Feb 25th
|
Minimum
Spanning Tree (GHS Algo.)
|
Notes can be found in
Scopes
|
Feb 26th
|
Chandy Lamport Algorithm
|
|
Feb 28th
|
The FLP Result
|
1.
Impossibility of Distributed Consensus with One Faulty
Process
2. Simple explanation of the proof: link
|
Mar 3rd
|
Proof of the FLP Result
|
|
Mar 4th
|
Consistency
: Sequential and causal consistency
|
Sequential consistency (tutorial),
video
(after 44th minute)
|
Mar 12th
|
Client centric consistency
models
CAP Theorem
|
Brewer's
Conjecture and the Feasibility of Consistent, Available,
Partition-Tolerant Web Services
|
| [Online] |
Paxos
|
1.
The Part-Time Parliament
2.
Paxos Made Simple
Youtube
video
|
| [Online] |
Raft consensus
protocol
|
In
Search of an Understandable Consensus Algorithm
Youtube video
|
| [Online] |
Byzantine General's Problem
|
The
Byzantine Generals Problem
Youtube video |
| [Online] |
Virtual
Synchrony, 2-Phase and 3-Phase Commits
|
Nonblocking
Commit Protocols (1981 SIGMOD)
Youtube video
|
| [Online] |
Bitcoin and
Blockchains
|
1.
Bitcoin and Cryptocurrency Technologies, 2016
2.
Hashcash - A Denial of Service Counter-Measure
3.
Bitcoin: A Peer-to-Peer Electronic Cash System
4.
Architecture of the Hyperledger Blockchain Fabric
5.
Comparison of Ethereum, Hyperledger Fabric, and Corda
6.
Bitcoin's Academic Pedigree
Youtube video
|
Practical Applications
|
[Online]
|
Coda |
1.
Coda: A Highly Available File System for a
Distributed Workstation Environment
2.
Fallacies of Distributed Systems
Youtube video
|
[Online]
|
Amazon Dynamo |
Dynamo:
Amazon’s Highly Available Key-value Store
Youtube video
|
| [Online] |
Google Percolator
|
Large
Scale Incremental Processing Using Distributed
Transactions and Notifications
Youtube video
|
| [Online] |
Corona |
A
High Performance Publish-Subscribe System for
the World Wide Web
Youtube video
Notes used
along with the video (link)
|
[Online]
|
Facebook:
Cassandra |
Cassandra:
A Decentralized Structured Storage System
Youtube video
|
| [Online] |
Facebook: Photo Storage |
Finding
a Needle in a Haystack: Facebook's Photo Storage
Youtube video
|
| [Online] |
Voldemort (LinkedIn)
|
Project
Voldemort -- Distributed Key-Value Storage
Youtube video
|
| [Online] |
Condor |
Distributed
Computing in Practice:
The Condor Experience
Youtube video |
| [Online] |
DryadLINQ |
DryadLINQ:
A System for General-Purpose Distributed
Data-Parallel Computing Using a High-Level Language
Youtube video |