Distributed Systems
CSCI-B 435/ 534/ ENGR-E 510 (Spring 2020)

Announcements

Course Description

Distributed computing systems are complex, difficult to understand, and everywhere.

This course will cover the necessary principles, techniques, and tools for understanding, analyzing, and building distributed applications and systems. We will be looking at both distributed computing fundamentals, as well as study the design of popular distributed systems. We will also examine blockchains from an academic distributed systems perspective.

We will look at how systems can communicate and coordinate through message passing, and study classical distributed algorithms involving logical and vector clocks, leader election, fault-tolerance, and consensus. Students will also learn about the design of large-scale distributed systems, and be expected to implement many of the ideas studied in class as part of homework assignments and projects.

In addition to the theoretical fundamentals, the final projects will also provide an opportunity to build and deploy distributed systems on the cloud.

Prerequisites

Distributed systems build upon and extend many classical areas in Computer Science. Strong fundamentals in Operating Systems, Computer Networks, and Algorithms are a must.

Text-books

We will use a combination of books and research papers.

  • Required: Distributed Systems: Principles and Paradigms, 3rd Edition (Maarten Van Steen and Andrew Tanenbaum) Online version

Reference

  • Elements of Distributed Computing (Vijay Garg)

Syllabus

Lecture order, slides, and exam dates are subject to change.

Lecture Topic Reading Notes
1 Introduction to Distributed Computing Chapter 1 Lec1
2 Building blocks: OS processes and threads Chapter 3 Lec2-slides
3 Computer Networks Chapter 4 Lec3-slides
4 Remote Procedure Calls Birrel and Nelson Lec4-slides
5 MapReduce MapReduce paper Lec5-slides Assignment 0 due
6 High-level communication and publish-subscribe ZeroMQ Lec6-slides
7 Event ordering and logical clocks Lamport Clocks, Chapter 6 Lec7-slides
8 Vector clocks and applications Garg Chapter 4 Lec8-slides Vector clock proof
9 Vector clock applications and Causal Orders Garg Chapter 4, 6 Lec9-slides Assignment 1 due
10 Mutual exclusion and leader election Chapter 6 Lec10-slides
11 Distributed Snapshots Chapter 10 from Garg Lec11-slides
12 Live snapshots in VMs Chapter 2 Lec12-slides
  Midterm 1    
13 Consistency Models: Sequential Consistency Chapter 7 Lec13-slides
14 More consistency models Chapter 7 Lec14-slides
15 Consistency models implementation Chapter 7 Lec15-slides
16 CAP Theorem, Eventual Consistency, CRDTs   Lec16-slides
17 Failures Chapter 8 Lec17-slides
18–19 Consensus: Paxos Chapter 8 Lec18-slides
  Midterm 2    
20 Raft and Zookeeper   raft Zookeeper
21 Byzantine fault tolerance Chapter 8 Lec21-slides
22 Spark Fault Tolerance   Spark
23 Distributed Filesystems NFS, Ceph Lec22-slides
24 Distributed Machine Learning TensorFlow Lec23-slides
25 Distributed Resource Management Mesos, DRF, Sparrow Lec24-slides

Important Dates

Date Event
Around Lecture #12 Mid-term 1
Around Lecture #10 Project proposal due
Around Lecture #17 Mid-project presentations
Last class Final project presentations

Evaluation Criteria

The rough breakdown is as follows:

   
2 Mid-terms 30%
~3 Assignments 30%
Readings and homework 10%
Final Project 20%
Class participation 10%

The assignments will be a mix of theory and distributed system design. The design oriented assignments will involve a large degree of programming and debugging. In most cases, the programming assignments are language agnostic (you can pick any reasonable programming language).

Late submission policy

A percentage penalty will be applied for all late submissions. The penalty is equal to 10*fibonacci(days-late), so if you submit one day late, you will be docked 10%, 2 days: 10%, 3 days: 20%, 4 days: 30%, 5 days: 50%. Allowing late submissions beyond 5 days is at the discretion of the instructor.

Project

The final project will involve analyzing and building a large distributed system. Being a graduate course, projects should be of a sufficiently high standard in terms of novelty, design, and documentation. Project reports will be in the form of conference-style papers.

A list of possible project ideas will be posted here soon.

Administrative Information

Class Information

Where When
Informatics E130 Tuesdays and Thursdays 8 am to 9.15am

Office Hours

Who Email (iu.edu) Office Location Office Hours
Prateek Sharma prateeks Luddy 4126 Thu 3–4 pm, or by appointment
Alex Fuerst alfuest    
       

Author: Prateek Sharma

Created: 2020-01-13 Mon 14:25

Validate