Distributed Algorithms and Verification
Please check regularly.
See News for last update
This class is about writing correct distributed programs.
A distributed program (aka concurrent, parallel, interactive program)
is a multi-threaded program,
perhaps with component programs spread over different computers.
To write correct a distributed program, say A,
three things are needed.
First, a definition of the intended external behavior of A;
we refer to this as the service of A.
Second, a way to establish A implements the service;
i.e., that every possible evolution of A,
regardless of variations in thread speeds (i.e., race conditions),
satisfies the service.
a way to use the service of A (instead of A itself)
when writing other programs.
We will cover a unified method to do these things,
and apply the method to problems in distributed computing and systems
(e.g., locks, termination detection, global snapshot computation,
TCP sockets, wide-area routing,
sequentially-consistent distributed shared memory,
serializable transaction processing).
In addition to paper-and-pencil homeworks,
we will also do a few programming homeworks.
Time permitting, we will also look at analyzing security (authentication)
properties of distributed programs.
Slides for text chapters
Slides for the text chapters are available
They are overly detailed.
The chapter 1 slides are particularly painful,
and I won't be following it closely.
Grading / MS comp in systems area
Homeworks/projects --- approx 60%
Exam 1 -------- approx 20%
Exam 2 -------- approx 20%
Weightages are approximate and may change by upto 10%.
The two exams together count as
an MS comprehensive exam in the systems area.