Class on
Distributed Algorithms
Class number
202-2-5811
Schedule
Sun. 12:00-14:00, 34/205, Thurs. 10:00-12:00, 34/103.
Office hours
Mine: Tue. 14:00-16:00 (Bldng
37, room 217),
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 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 4-8 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. 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, 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.
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
Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.
SIAM
web-page 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 Nash-Williams Decomposition,
Distributed Computing, special issue of PODC'08, vol. 22, pp. 363-379, 2010 ,
Distributed
(Delta+1)-Coloring in Linear (in Delta) Time,
In Proc. Symp. on
Theory of Computing, STOC'09, pp.111-120, Bethesda, MD, 2009.
Deterministic
Distributed Coloring in Polylogarithmic Time. In
Proc. of International Symp. on
Principles of Distributed Computing, PODC'10, pp. 410-419 Zurich, Switzerland,
July 2010.
Lecture Notes of
Ariel Sapir
Lectures
1-2
Lectures
3-4
Lectures
5-7
Lectures
8-9
Lectures
14-17
Lectures
18-21
Lectures
22-24
Assignments, Home
Exam
Assignment 1, Due to 20/11/17
Assignment 2, Due to 7/12/17
Assignment 3, Due to 4/1/18
Assignment 4, Due to 28/1/18
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 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. 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
web-sites 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
web-site of the class of Autumn 2012
The
web-site of the class of Autumn 2011
The
web-site of the class of Autumn 2010
The
web-site of the class of Autumn 2009
The
web-site of the class of Autumn 2008
The
web-site of the class of Autumn 2006
The
web-site of the class of Autumn 2005
The
web-site of the class of Autumn 2004
|