Fundamentals of Distributed Algorithms
Brief overview
Distributed systems pose fundamental new challenges which require new algorithmic
paradigms and new ways of thinking about systems. This course will focus on some
fundamental ideas relevant to the theory and practice of distributed systems,
including clocks, deadlock, fault tolerance, knowledge, mutual exclusion,
states, and termination.
General information
Time: Monday and Wednesday, 8:30-10:00
Place: Burnside Hall 1B39
Office hours: Tuesday, 14:00-16:00 or by appointment
Office: McConnell 233
Email: franck@cs.mcgill.ca
Phone: 398-7071, extension 0876
Prerequisite: a basic course on operating systems such as 308-310
Reference material
Class notes and handouts will be crucial. In particular, these
papers will be made available to the students.
Evaluation
The student's performance in the course will be evaluated as a combination of
assignments (40%), a term paper (50%), and a presentation (10%). More details are
given below. There will be no supplemental examination for this course. Neither will
students have the option of doing additional work to upgrade their mark.
Assignments
There will be weekly assignments. Every Wednesday, the assignments for the week can
be found by clicking on the calendar below. The assignments should be handed in at
the beginning of the class on the next Wednesday.
Term paper
Students can choose between
- studying and presenting a research paper on distributed algorithms and
- making and presenting a case study of a distributed (operating) system.
1. Research paper
Students will either choose one of these papers or
suggest a paper themselves. They will study their paper in detail, if necessary
also looking at some related work. In both their oral and written presentation they
will
- present the main ideas of the paper,
- discuss the strong and the weak points of the paper,
- point out the links with the material presented in the course, and
- mention possible improvements, extensions, generalizations etc.
2. Case study
Students will choose a distributed (operating) system. Some pointers can be
found here. They will collect information about their
system. In both their oral and written presentation they will
- discuss the main characteristics of the system,
- discuss the strong and the weak points of the system,
- discuss what kind of distributed algorithms are used in the system, and
- point out the links with the material presented in the course.
Progress report
In the week of March 16-20 each student will give an overview of
- what they have done so far,
- what they still plan do, and
- their term paper (headings of the sections).
The term paper is due on April 17.
Class presentation
Students will give a 20 minute summary of their paper. These presentations will
be given during the last five lectures of the course (i.e. those in April).
Students are encouraged to attend the presentations.