Computer Science 308-575
Fundamentals of Distributed Algorithms

Instructor(s): Prof. C. Tropper
McConnell Hall, room 112N
Office hours: Tuesday, Thursday 12:00-1:300
Teaching assistant:Jun Wang, jwang90@cs.mcgill.ca
Office hours: 107 McConnell Hall, Wednesday, 10:30-11:30

Course Description and Outline With the development of high-speed networks and ever-faster 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 re-visit 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 de-bug 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 papers

MPI references Here are a list of tutorials on mpi which should be of some help.

• mpi tutorials: tutorial
• web pages: web-pages
• mpich 2: mpich2
• mpi-text: Using MPI
• mpi powerpoint slides If you do not have powerpoint, you can download open office.

Papers for presentation

• quiescencedetection
  
• max flow
• fault tolerance

Course Assignments and Projects Page: Assignment1

Project Submission Guide: handin

E-mail: Teaching Assistant