Distributed Algorithms, 5p
PhD-level Course

The course starts on the 20st of January

Welcome to the course page for Distributed Algorithms, a point introductory graduate course at the Dept. of Computer Systems, Uppsala University.
Undergraduate students interested in following this course are also wellcome.

Introduction and Course Description

Sequential and parallel algorithms can usually be seen as recipies that transform inputs that are given to them at the beginning into desired outputs that are produced at the end. Distributed Algorithms run in processes of systems where the processing elements are physically apart and are there rather to guarantee desired behavior of the system.

People's concern when thinking of a distributed algorithm is not only what each component should do in order to guarantee the desired behavior of the system but also -like in parallel and sequential algorithms- a big deal of effort goes to issues like:

the way that the processes can organize, remember, change and access collections of data (which data structures to use).
how to predict (analyze) the resources that the algorithm requires; resources such as memory, communication bandwidth, computational time, time for an operation to finish.
how to develop methods (create a design methodology) that another designer can employ in order to find a solution to another problem.
how to prove that nobody ever can find a better algorithm (lower bounds).
how to prove that although you did not find a solution nobody ever will find one (Intractability).

The course will aim at making the students familiar with many of the important problems, protocols and impossibility results in the area of distributed computing; it will also aim at giving a good feeling for the different system models and their capabilities. More specifically, the idea is that those who will have followed and participated in the course will acquire a sound background, a "tool-case", which can be further used to pursue research in Distributed Computing, as well as to recognize the problems when they arise in practice and to employ either techniques for solving them or arguments for proving impossibility.

The problems to be taught and discussed are: broadcasting, election, minimum spanning tree, synchronizers, time-stamping, logical clocks, mutual exclusion, resource allocation, transaction commit, distributed consensus, atomic snapshots, concurrent time-stamping, wait-free and lock-free synchronization, concurrent data objects, self-stabilization. Additionally, the course will include study of the basic distributed system models, including synchronous, asynchronous, timing-based, general message passing, plus simpler paradigms such as shared memory and atomic objects.

Bibliography

1. V. Garg ``Principles of Distributed Systems". (Kluwer Academic Publishers, 1996)
2. N. Lynch ``Distributed Algorithms'' (Morgan-Kaufmann, 1995)
3. G. Tel ``Introduction to Distributed Algorithms''. (Cambridge University Press, 1994)
4. Related conference and journal papers.

Prerequisites

We expect students to have programming skills in C or C++ (the applied project will involve programming). Besides this, knowledge of basic algorithms and operating systems principles will be useful.

Examination

There are going to be weekly homework assignments. See homework guidelines. The homework assignments page will be pointing to all homework assignments released so far.

There is also an applied project assignment that students can select. For this, students will be divided into groups of 2-4 persons. For more details see the paragraph below. Students who select to do the applied project assignment do not have to give the final exams.

Applied project

The applied project is: Distributed Algorithms Visualization and Evaluation. The main goal of the project is that the students uncover the fundamental attributes and characteristics of these distributed algorithms by constructing their animations. Each group will be assigned to develop the animation of two distributed algorithms.

The project runs in parallel with the rest of the course, and most of the last month is reserved for finishing the assignments.

The project work should be documented in a joint final report, presented in a (joint) seminar on 980326. This is also the date when the final exam will take place for the students who have not selected the applied project assignment.

Grading

The grade will be determined by the homework assignemts (40%), the final project (60%) or the final exam (60%).

Schedule

For a tentative schedule of the lectures see here.

For a more detailed descrption of the topics see here.

Instructor, Office hours, etc.

If you are interested in following the course send an e-mail to Philippas Tsigas (tsigas@docs.uu.se) Office hours: Tuesdsdays after the lecture.

Last updated: Mon Dec 8 18:52:15 MET 1997 (by Philippas Tsigas)

Distributed Algorithms, 5p PhD-level Course