Course Objectives and Scope |
Course Prerequisites |
The objective of this course is to introduce you to the key ideas that
have shaped distributed computing and are likely to do so in the
future; the ambition of this course is to get you as excited about
them as I am. The thing about distributed computing that really
grabbed me when I first became exposed to it was how its tremendous
practical impact was based on beautiful, elegant,
theoretical foundations. Because of asynchrony, partial failures,
network partitions and concurrency (all issues you'll be an
expert on by the end of this course) it is virtually impossible to
hack a distributed system into submission:
getting it right means being able to prove things about it.
This course strives to mirror the multi-faceted nature of the subject it
covers. Classes focuses on fundamentals: We
will cover problems, models, algorithms, and impossibility
results. But to keep ourselves honest, we will integrate the
theoretical discussions with substantial projects that will allow to
apply some of the concepts discussed in class.
Topics will include the majority (we are going to shoot for all and
see what happens) of the following:
- Global states and event ordering
- Logical clocks
- Vector clocks
- Consistent cuts and global property detection
- Rollback-recovery and message-logging protocols
- State machine approach
- Agreement protocols
- Failure detectors
- Replication and consistency
- Byzantine fault tolerance
- Atomic Commit
- Epidemic Protocols
The ideal student should have a good undergraduate background in
Operating Systems, but, as long as you are willing to learn on demand
the OS concepts we will touch upon,
(and I'll be happy to give you pointers on how to do that), you
should be fine.
So, what are the real hard pre-requisites? The first is to be willing
to participate in class. I like to make the class interactive---and
for that, I need you. Second, you need to be willing to get in touch
with your inner Ninja, both on the theoretical and systems side. You
should either be (or be willing to become) comfortable about
developing proofs, as several of the homework problems will require
you to develop protocols and prove them correct. The course
programming assignments, in turn, will require you to either be familiar,
or learn as you go, the rudiments of network programming.
There is no required textbook for this class. (Thank you, thank
you). Instead, you will be required to complete reading assignments
centered on research papers that will integrate what we will be
discussing in class. I will also make available my class notes---I'll
do this after class (typically at the end of the week),
because I want you to think about the question I'll be asking "live",
rather than reading the answers in my notes!
If you want to purchase a book for you to keep as a reference,
there are several to choose from:
- A.S. Tanenbaum and M. van Steen. Distributed
Systems. Principles and Paradigms. (2nd Ed.) Prentice Hall, 2007.
This book provides a good starting point for several of the topics we
will discuss, with an informal presentation style.
- S. Mullender (editor) Distributed Systems, Second
Edition, ACM Press, Addison-Wesley, MA, 1994.
This book, which
contains the lecture notes from a summer course on Distributed
Computing of a while ago, discusses important aspects of both the theory and the
practice of distributed computing. The authors include many of the
leading researchers in the area (spot the Cornellians!).
H. Attiya and J. Welch. Distributed Computing: Fundamentals,
Simulations, and Advanced Topics (2nd Ed.) . Wiley 2004.
A discussion of distributed computing with a strong theoretical bias.
- N. Lynch Distributed Algorithms Morgan Kauffman, 1996.
A monumental tome on, well, distributed algorithm. Not an easy read,
but a good reference.
- P.A. Bernstein, V. Hadzilakos and N. Goodman. Concurrency
Control and Recovery in Database Systems Addison-Wesley, MA,
A true classic on, well, concurrency control.
MW: 1:25-2:40, Olin 255; F 1:25-2:15 Gates G01
During most weeks, we will meet only on Mondays and Wednesday, but please leave
the Friday open for makeup classes. I have already indicated in the
schedule the makeup classes that I already know will be required;
others may pop up.
Notable dates in the schedule
- Prelim: October 16, in class.
- Final: December 6, 7:00 pm. Location: TBD
A note about email
like to discourage you from contacting me by email with substantive
technical questions; instead, I would like to encourage you to come
see me in person during office hours, asking for an appointment
outside of them if necessary, to discuss questions you may have about
the material. There are two reasons for why I strongly discourage you
from having a technical conversation by email: 1) DOS defense. As you
know, a one-line email may require several pages of explanations back:
a perfect Denial of Service attack! The problem is that the attacker
(you :-) ) can at very low cost for himself cause the server (me) to
perform an unbounded amount of work. A strategy to counter denial of
service is to structure protocols so that a potential attacker must
perform approximately the same amount of work as the server: if the
question is important enough to require 30 minutes of my time, then it
should justify at least 30 minutes of yours. 2) It may sound cheesy,
but I want to get to know you, and you visiting my office is the best
way for me to accomplish this.
It is important for you to realize what grades in this class reflect
and what they don't reflect. All we can grade you on is how well you
demonstrate that you know the material this semester. We can't grade
you on how much of a success you'll be after graduation, how
smart/creative/persistent/self-motivated you are, or even how well
you'll be able to apply the material in the future. And after all, it
is what you do in the future, not what you do this semester, that's
That said grades will be determined as follows:
Projects will be of different complexity, which will be reflected in
the percentage of credit that each will earn.
Extracredit (course eval)
In some courses, the TAs and instructor have to spend a lot of time
dealing with re-grading appeals, time that would be better spent
helping students learn the material. Absolutely come to us if we make
an arithmetic error, but realize that a few points here and there are
extremely unlikely to make any difference in your final grade. If you
believe that we assigned too little credit for your work, you may
submit your work for a re-grade under the following restrictions. (1)
All re-grade requests must be submitted with a clear, written
statement that explains why you believe the original grade was
incorrect. (2) All requests for re-grades must be submitted within 1
calendar week of when the graded work is returned. (3) We will truly
re-grade the entire exam, problem set, or project assignment, not just
the issue you bring to our attention. So, to be clear: if in the
process we find out other issues that had escaped us the first
time, we will deduct points. Thus, you grade can go up or down on a
You are encouraged to work in groups on the programming projects;
you may form a different group for each programming project.
Groups should comprise 1 to 3 students. Groups of size 2 or 3 are
ideal for the kinds of projects you will undertake. Working with other
people not only can lead to a better understanding of the material but
it will enable you to develop collaboration skills that should prove
helpful throughout your career. Each participant in a group should be
able to explain the entire content of any submitted solution.
Students are required to work alone on the written assignments.
Violations of the Cornell University Code of Academic Integrity will
be prosecuted aggressively. Collaborate with other members of
your group on the project; do not collaborate with anyone
(within your group, outside of your group, on the Internet, whether
synchronously or asynchronously) on other homework. Looking
on line for solutions to problem set questions (even those buried in
research papers not assigned as readings) will be very much
considered a violation of the Code of Academic Integrity.
Students are also expected to be familiar with the University's and the CS Department's various policies on appropriate use of computers.
Class attendance (or lack thereof) does not directly reflect into
credit: however, it is my experience that students who don't attend
class tend not to do well. "Duh" you might say---but again, coming to
class is truly critical for your success in this class, especially
considering that this class does not follow a textbook. I will
occasionally have a roll call at the beginning of class-again, absence
or presence has no effect on credit: but I would like to get to know
you by name, and I am terrible with names, so I hope this will help
The midterm will take place in class on October 16. The final will take place on December 6th, at 7:00 pm.
If you have a conflict with the date of the final, please inform the instructor
within two weeks after the date is posted. After this date, conflicts will be considered if
they are caused by either:
Illness, which has to be documented by a doctor and approved by the university.
Death in the immediate family.
Late policy. No extensions will be given for
completing the homework or the programming projects, except that
students will be allowed 6 flexible slip days for the projects and
homework during the semester. A student may divide slip days across
projects in any way he or she wishes to extend deadlines for the
projects (or a homework) except for projects or homework due at end of
the semester. To help your TAs track
your slip-day status, the top of your project README file (or your
homework) should include the line:
Slip days used (this project):
_______ Slip days used (total): ______ Please not that:
Slip days will be tracked at the granularity of a day; if an
assignment is 1 minute late, it is one day late: this is not to be
draconian, but to show some respect for your TA. If two project
partners have different numbers of slip days remaining on their
accounts, the slip days account for the team is the
min of the partners' slip day balances.
Assignments that do not carry this information will not be
- Misrepresenting slip days information will be
considered as a violation of academic integrity
of the above rules will be allowed in two cases:
Illness, which has to be documented by a doctor and approved by the university.
Death in the immediate family.
If you have a disability-related need for reasonable academic
adjustments in this course, please provide an accommodation
notification letter from Student Disability Services. Students are
expected to give two weeks’ notice of the need for
accommodations. If you need immediate accommodations or physical
access, please arrange to meet with me within the first two class
meetings. The website for Student Disability Services is:
This page is maintained by Lorenzo Alvisi. Last updated August 18,