Class on
Distributed Algorithms
Class number
20225811
Schedule
Sun. 12:0014:00, 34/205, Thurs. 10:0012:00, 34/103.
Office hours
Mine: Tue. 14:0016:00 (Bldng
37, room 217),
Outline
The class is devoted to the theory of distributed
algorithms in the messagepassing 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 grade for the presentation of one of the topics below in
class, notes from somebody's else presentation (80% together), and homework
assignments (20%). There will be 48 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, breadthfirstsearch tree
construction, upcastbased
MST (minimumweight 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
maximalindependentset problems. This topic will be very central in the
course.
5) Routing.
If time permits:
6) The theory of graph decomposition, and its application to distributed
computing.
7) Spanners, distancelabeling, more advanced
routing.
8) GallagerHumbletSpira 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 selfcontained, but will assume some basic
knowledge of algorithmics and discrete mathematics.
Topics for
Presentation
A paper by D. Peleg and V. Rubinovich
Lower
Bounds for the Minimum Spanning Tree problem
My paper on constructing spanners in streaming and distibuted
models
Streaming
and Distributed Algorithm for Constructing Spanners
A paper of Thorup and Zwick about distributed
routing
Compact
Routing Schemes,
A paper by Barenboim, Pettie, Schneider and myself:
The
Locality of Distributed Symmetry Breaking
A part of this paper would be enough for a presentation.
Bibliography
The book of David Peleg, Distributed Computing: a
LocalitySensitive Approach, SIAM, Philadelphia, PA, 2000.
SIAM
webpage of the book
The monograph of Leonid
Barenboim and myself:
Distributed Graph
Coloring: Fundamentals and Recent Developments
Papers by L. Barenboim and myself that will be used in the second part of the
course:
Sublogarithmic
Distributed MIS Algorithm for Sparse Graphs Using NashWilliams Decomposition,
Distributed Computing, special issue of PODC'08, vol. 22, pp. 363379, 2010 ,
Distributed
(Delta+1)Coloring in Linear (in Delta) Time,
In Proc. Symp. on
Theory of Computing, STOC'09, pp.111120, Bethesda, MD, 2009.
Deterministic
Distributed Coloring in Polylogarithmic Time. In
Proc. of International Symp. on
Principles of Distributed Computing, PODC'10, pp. 410419 Zurich, Switzerland,
July 2010.
Lecture Notes of
Ariel Sapir
Lectures
12
Lectures
34
Lectures
57
Lectures
89
Lectures
1417
Lectures
1821
Lectures
2224
Assignments, Home
Exam
Assignment 1, Due to 20/11/17
Solutions to
Assignments
Solution 1
Solution 2
Solution 3
Solution 4
Exercises
Exercises
from David Peleg's book
Exam, Moed Aleph
Moed Aleph
Moed Bet
Moed Bet
Solution to Moed Aleph
Solution to Moed Aleph
Solution to Moed Bet
Solution to Moed Bet
Latex
Latex is a program for scientific writing. Using special
symbols one can write an ascii file, compile it
with a latexcompiler (type "latex" from unix
commandline), 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. 2014)
 Moed Aleph
The
exam (pdf format)
A
solution to moed aleph (pdf)
Exam (Feb. 2014)
 Moed Bet
The
exam (pdf format)
A
soution to moed bet (pdf)
Exam (Feb. 2013)
 Moed Aleph
The
exam (pdf format)
A
solution (pdf format)
Exam (March 2013)
 Moed Bet
The
exam (pdf format)
A
solution (pdf format)
Exam (Jan. 2012)
 Moed Aleph
The
exam (pdf format)
A
solution (pdf format)
Exam (Feb. 2012)
 Moed Bet
The
exam (pdf format)
A
solution (pdf format)
Exam (Jan. 2011)
 Moed Aleph
The
exam (pdf format)
A
solution (pdf format)
Exam (Jan. 2011)
 Moed Bet
The
exam (pdf format)
A
solution (pdf format)
Exam (Feb. 2010)
 Moed Aleph
The
exam (pdf format)
A
solution (pdf format)
Exam (Feb. 2010)
 Moed Bet
The
exam (pdf format)
A
solution (pdf format)
Exam (March 09) 
Moed Aleph
The
exam (pdf format)
A
solution (pdf format)
Exam (May 09)  Moed Bet
The
exam (pdf format)
A
solution (pdf format)
Exam (Feb. 07)  Moed Aleph
The
exam (Word document)
A
solution (pdf format)
Exam (Feb. 07)  Moed Bet
The
exam (Word document)
A
solution (pdf format)
Exam (Feb. 06)  Moed Aleph
The
exam (pdf format)
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 Bet
The
exam (pdf format)
A
solution (pdf format)
Links to
websites of previous years
The
webpage of the class of Autumn 2016
The
webpage of the class of Autumn 2014
The
webpage of the class of Autumn 2013
The
website of the class of Autumn 2012
The
website of the class of Autumn 2011
The
website of the class of Autumn 2010
The
website of the class of Autumn 2009
The
website of the class of Autumn 2008
The
website of the class of Autumn 2006
The
website of the class of Autumn 2005
The
website of the class of Autumn 2004
