Course Overview

Description

Traditional computer science emphasizes the design and analysis of sequential algorithms, which are meant to be executed on a single computing device. With the rise of network technology, however, came a new algorithmic scenario: multiple computing devices, connected by some sort of communication channels or shared objects, that must work together to solve problems. These distributed systems require distributed algorithms.

The world of distributed algorithms is quite different than the world of sequential algorithms. It is a world where the time complexity is often obvious but proving that an algorithm works is difficult. There is less algebra in the distributed setting, but more mind-bending logic arguments. Distributed algorithm theorists almost never utter the phrases "master theorem" or "dynamic programming," but instead talk about "byzantine adversaries" and "indistinguishability." Perhaps most interesting, in distributed computing, many problems that seem easy turn out to be impossible to solve, while some difficult sounding puzzles yield simple solutions.

This is a quirky but important corner of computer science that turns out to be a lot of fun to explore. (It is also, one must add, a good world to know about when entering the job market.)

Course Structure

The first two thirds of this course will teach you the fundamentals of designing and analyzing distributed algorithms. The last third of the course focuses on real distributed systems, leveraging your knowledge from the preceding lectures to help you dissect and understand the strategies that keep systems like Google's data centers or popular peer-to-peer networks operational.

There will be three non-cumulative exams for the course, one for each third. There will also be four problem sets covering the first two parts of the course. You will have two weeks for each problem set.

There will by no programming in this course. As with the standard algorithms course, it is primarily theoretical in nature.

Textbook

The required textbook for this course is Distributed Algorithms, Nancy Lynch, 1996. Most of the topics covered in the first two thirds of this course, as well as some problem set problems, will be drawn from this textbook.

Grading

Grades in the course will be based on the problem sets, exams, and participation. The participation grade will be based on your attendance and involvement in class. If you show up to class, pay attention, and ask questions when stuck (either in class, or after class), you will get full participation points.

Your final grade will be based on the percentage of total available points you earned throughout the semester. The mapping of final percentage to letter grades is not fixed in advance, but instead something I will define as I get a better feel for the relative difficulty of the assigned material. When in doubt about how well you are doing: ask me.

I will assign the point value of different assignments such that the exams combined represent roughly 60% of available points, the problem sets 35%, and participation the final 5%.

Course Logistics

Office Hours

I hold regular office hours from 1:00 to 2:30 pm on Thursdays, in my office at 342 A Saint Mary's Hall. If this time conflicts with your class schedule, let me know, and we can arrange alternate meetings as needed. Beware that my office number might change at some point during this semester.

Contact

To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, I prefer that you bring them to office hours. Use e-mail only when the above two options are not applicable.

Problem Sets

The following rules will help keep the problem set submission and grading process running smoothly:

You must work alone on problem sets. You may only discuss problems with me. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources, solutions from other classes, or talk to other students when working on problem set problems.
Problem sets should be handed in at the beginning of class on the day they are due. That is, bring a physical copy of the problem set to class to give to me before the lecture begins.
Problem sets not handed in by the beginning of lecture will be considered late, and 10% of the points deducted. Problem sets not handed until the day after the deadline will have an additional 10% deducted (slide late problem sets under my door if I am not in my office). Beyond this point, problem sets will not be accepted.

Exams

There will be three exams in the course: two midterms and a final. The exams are non-cumulative (that is, each covers only the new material since the last exam).

Academic Integrity

I take academic integrity seriously. To repeat the problem set instructions from above: You must work alone on problem sets. You may only discuss problems with me. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources or talk to other students.

You may not bring any outside material into exams.

You may not reference any problem sets or solutions from similar courses offered at other schools.

When in doubt, ask me what is allowed.

Schedule

Below is the tentative schedule for the course. I will modify the schedule as needed as the course progresses. Problem sets will be posted below on this schedule as they become available. The readings column lists the chapters from the Lynch textbook that cover the corresponding lecture's material.

Note: The syllabus for the third part of the semester will be set during the semester.

Class Number	Date	Description	Readings
		Part 1: Synchronous Networks
1	8/29	Introduction to distributed algorithms; course overview
2	9/3	Leader election in rings: basic algorithms and impossibilities.	3.1 - 3.3
3	9/5	Leader election in rings: better algorithms.	3.4 - 3.5
4	9/10	Solving problems in general network graphs: leader election, breadth-first search, and shortest path.	4.1 - 4.3
5	9/12	Minimum spanning trees. Homework #1 handed out.	4.4
6	9/17	Impossibility of consensus with link failures, algorithms for consensus with process failures.	5.1, 6.1 - 6.2
7	9/19	A lower bound on consensus with process failures.	Keidar and Rajsbaum, 2003.
8	9/24	Set-consensus and distributed commit.	7.1, 7.3
9	9/26	Byzantine consensus: algorithms and impossibilities. Homework #1 due.	6.3
10	10/1	Exam review.
11	10/3	Exam #1. Homework #2 handed out.
		Part 2: Asynchronous Shared Memory and Network Systems
12	10/8	Shared memory model and mutual exclusion with registers.	10.1 - 10.3
13	10/10	Improved mutual exclusion with registers.	10.5, 10.7
14	10/15	The dining philosophers problem.	11.1 - 11.3
15	10/17	The impossibility of consensus with process failures. Homework #2 due. Homework #3 handed out.	12.3
16	10/22	Asynchronous network model: solving leader election in rings and building spanning trees.	15.1, 15.3
17	10/24	Connecting the asynchronous shared memory and network models.	17.1 - 17.2
18	10/29	The PAXOS consensus algorithm and reliable replicated state.	Lamport, 2001
19	10/31	Partially synchronous systems: basic results for mututal exclusion and consensus. Homework #3 due.	24.1 - 24.2, 25.1 - 25.3
20	11/5	Exam review. (Withdraw Deadline)
21	11/7	Exam #2. Homework #4 handed out.
		Part 3: Real Systems and Recent Results
22	11/12	Google's File System
	11/14	No Class
23	11/19	Practical Byzantine Fault-Tolerance
24	11/21	Akami's Network Caches. Homework #4 due.
25	11/26	Distributed Algorithms for Peer-to-Peer Networks
	11/28	No Class: Thanksgiving Break
26	12/3	Distributed Algorithms for Social Networks
27	12/5	Distributed Algorithms for Wireless Networks
	12/14	Final examination (the exam is from 12:30 to 2:30 pm in ICC 207a)

COSC 242 - Algorithms for Distributed Systems

Fall 2013

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 3:30 - 4:45

Reiss 281