Distributed Systems

Course: COL 819
Semester II, 2019-20
Credits: 4 (3-0-2)



Instructor: Prof. Smruti R. Sarangi

Lectures
: Tuesday, Wednesday and Friday: 10 to 11 AM, Bharti Building 201

Piazza link: http://piazza.com/iit_delhi/spring2020/col819 (access code: col819)

Course Description:
This course will give an introduction to some advanced aspects of distributed systems.

Course Load: 1 Mid-term, 1 End-term, Minor 1(Programming Assignment 1), Minor 2(Programming Assignment 2),
                         Programming Assignment 3. A programming assignment may be substituted by a term paper.

Evaluation: Midterm (20%), End term (25%), Assignment 1 (15%), Assignment 2(15%),
                     Assignment 3 (25%)

Teaching Assistant: Sandeep Kumar (CSE)


Reference Books:
[Relevant Reference for Most Concepts] Distributed Systems: An Algorithmic Approach (Sukumar Ghosh, CRC)
[For relevant background] Distributed Systems: Principles and Paradigms (Andrew S. Tanenbaum and Martin V. Steen)
[Reference on distributed algorithms] Distributed Algorithms by Nancy Lynch
    OR
    Introduction to Distributed Algorithms by Gerard Tel
[Reference on advanced OS concepts] Advanced Concepts in Operating Systems (Singhal and Shivaratri)


Lectures and Slides:

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

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
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 link:  Youtube video
[Online] Raft consensus protocol
In Search of an Understandable Consensus Algorithm
Youtube link: Youtube video
[Online] Byzantine General's Problem
The Byzantine Generals Problem
Youtube link: Youtube video
[Online] Virtual Synchrony, 2-Phase and 3-Phase Commits
Nonblocking Commit Protocols (1981 SIGMOD)
Youtube link: 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 link: Youtube video
Practical Applications
[Online]
Coda  1. Coda: A Highly Available File System for a
Distributed Workstation Environment

2. Fallacies of Distributed Systems
Youtube link:Youtube video
[Online]
Amazon Dynamo Dynamo: Amazonís Highly Available Key-value Store
Youtube link: Youtube video
[Online] Google Percolator
Large Scale Incremental Processing Using Distributed Transactions and Notifications
Youtube link:Youtube video
[Online] Corona A High Performance Publish-Subscribe System for
the World Wide Web

Youtube link: Youtube video
         Notes used along with the video (link)
[Online]
Facebook: Cassandra Cassandra: A Decentralized Structured Storage System
Youtube link:  Youtube video
[Online] Facebook: Photo Storage Finding a Needle in a Haystack: Facebook's Photo Storage
Youtube link:  Youtube video
[Online] Voldemort (LinkedIn)
Project Voldemort -- Distributed Key-Value Storage
Youtube link:  Youtube video
[Online] Condor Distributed Computing in Practice:
The Condor Experience

Youtube link: Youtube video
[Online] DryadLINQ DryadLINQ: A System for General-Purpose Distributed
Data-Parallel Computing Using a High-Level Language

Youtube link: