School of Computer Science
Computer Science 308575
Fundamentals of Distributed Algorithms
Instructor(s):
Prof. C. Tropper
McConnell Hall, room 112N
Office hours: Monday, Wednesday 12:001:30
Teaching assistant:Arash Nourian,arash.nourian@mail.mcgill.ca
Office hours: 107 McConnell Hall, Wednesday, 12:001:00
Course Description and Outline
With the development of highspeed networks and everfaster
microprocessors
our approach to computation is undergoing an evolution towards
a distributed model. In this model, we make use of message passing
between
processors,
This evolution is not without a price however;
we can no longer rely upon a a global view of the computation, as
global variables are not available. Hence we need to revisit
basic questions such as how to detect the termination of a computation
and how to obtain a global snapshot of the computation (so we can
debug our programs, for example). In this course, we attempt to
cover fundamental paradigms in distributed algorithms
along with several of the proof techniques which have
evolved for establishing correctness.
The course will have an implementation flavor, as several projects
are required (see below). These projects are intended to acquaint the
student with the pitfalls (and pleasures) of programming
distributed algorithms. Assignments of a theoretical nature,
intended to help students develop an appreciation for the
techniques of proof appropriate for establishing correctness
will be required as well. We will read a collection of original
papers, collected in the form of a course pack, which is available
in the bookstore. The outline for the topics in the course follows.
1. Time in distributed systems.
2. Leader election algorithms, mutual exclusion algorithms.
3. Termination detection algorithms
4. Deadlock detection algorithms
5. Global snapshots and applications (global virtual time, checkpoints
in distributed databases,..)
6. Garbage collection algorithms
7. Fault tolerance
8. Proof techniques for distributed algorithms
9. How processes learn
Papers for course.
The papers which we will read for this course may be
downloaded from 575 papers
MPI references
Here are a list of tutorials on mpi which should be of some help.
Papers for presentation
Problem sets
Send the pdf with your solutions to: jwang90@cs.mcgill.ca.
problem set 1
problem set 2
problem set 3
Course Project Page:
Assignment
Project Submission Guide:
handin
Email:
Teaching Assistant
