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.)

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.

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.

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%**.

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.

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.

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.

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).

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.

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) |