Class on Distributed Algorithms



Class number

202-1-5371

Schedule

Sun. 15:00-17:00, Wed. 16:00-18:00.

Office hours

Mine: Wed. 1pm-3pm (Bldng 37, room 217),
Yonatan's: Thursday, 11am - 1pm (Bldng 58, Room -106 ("minus 106")).

Outline

The class is devoted to the theory of distributed algorithms in the message-passing model. The network is modeled by a graph, the processors of the network reside in the vertices of the graph, and the edges of the graph serve as an abstraction of communication links. The aim is to design distributed algorithms that solve graph problems on the infrastructure network.

General information

The grade of the course will be set as the weighted average of the final exam (90%), and homework assignments (10%). There will be 4-7 homework assignments during the course. Students are allowed not to submit one of those assignments. Assignments are for individual submission (submissions by groups of 2 and more students will not be accepted).

Syllabus

The design of distributed algorithms is an active area of research. It has multiple applications in the areas of Communication Networks (particularly, for Internet programming) and Distributed Systems. >From theoretical standpoint, the area is a natural extension of the classical algorithmic theory, and its study has provided significant advances in our understanding of such basic concepts as Locality and Randomization. The course will concentrate on the theory of distributed algorithms. Particular focus will be given to the model in which the processors share no common memory. The specific topics that will be covered (with possible variations due to time limitations, and the desires of the audience) are:

1) The definition of the model, and of the complexity measures in this model.

2) Basic algorithms: broadcast, convergecast, downcast, upcast, breadth-first-search tree construction, upcast-based MST (minimum-weight spanning tree) construction.

3) The issue of synchronization, basic synchronizers (alpha and beta).

4) Upper and lower bounds on the complexity of vertex coloring and maximal-independent-set problems.

5) Routing.

If time permits:

6) The theory of graph decomposition, and its application to distributed computing.

7) Spanners, distance-labeling, more advanced routing.

8) Gallager-Humblet-Spira MST construction.

9) More advanced synchronization (gamma, delta, and beyond).

The discussion will be conducted from mathematical perspective, trying to provide rigorous proofs wherever possible along with the intuition. The class will be self-contained, but will assume some basic knowledge of algorithmics and discrete mathematics..

Bibliography

The book of David Peleg, Distributed Computing: a Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.
SIAM web-page of the book

Assignments

To be submitted in the mailbox 108 in Building 37 (Yonatan Shichel), or via email to shichel@cs.bgu.ac.il
  1. First Assignment - Due 26/11/2006
  2. Second Assignment - Due 13/12/2006
  3. Third Assignment - Due 14/01/2007
  4. Fourth Assignment - Due 29/01/2007


Solutions to Assignments

  1. First Assignment
  2. Second Assignment
  3. Third Assignment
  4. Fourth Assignment

Assignment Grades


Assignment Grades

Exercises


Exercises from David Peleg's book

Latex

Latex is a program for scientific writing. Using special symbols one can write an ascii file, compile it with a latex-compiler (type "latex" from unix command-line), and get a nice postscript with all sorts of mathematical formulae. For more information see:
An online manual of latex
An example of a paper written in Latex

Exam (Feb. 06) - Moed Aleph


The exam (Word document)
A solution (pdf format)

Exam (Feb. 06) - Moed Beyt


The exam (Word document)
A solution (pdf format)

Exam (Feb. 05) - Moed Aleph


The exam (pdf format)
A solution (pdf format)
A correction to the solution of question 3b (eml format - outlook message)

Exam (Feb. 05) - Moed Beyt


The exam (pdf format)
A solution (pdf format)

Exam (Feb. 06) - Moed Aleph


The exam (word format)
A solution (pdf format)

Links to web-sites of previous years


The web-site of the class of Autumn 2005
The web-site of the class of Autumn 2004