## Class on Distributed Algorithms## Class number202-2-5811## ScheduleSun. 12:00-14:00, 97/207, Thurs. 10:00-12:00, 34/207.## Office hoursMine: Thur. 14:00-16:00 (Bldng 37, room 217),## OutlineThe 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 informationThe 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 (90% together), and homework assignments (10%). 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).## SyllabusThe 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 PresentationA paper by D. Peleg and V. RubinovichLower 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. ## BibliographyThe 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 SapirLectures 1-2 Lectures 3-4 Lectures 5-7 Lectures 8-9 Lectures 14-17 Lectures 18-21 Lectures 22-24 ## Assignments, Home ExamAssignment 1, due to Dec. 10 Assignment 2, due to Dec. 29 Assignment 3, due to Jan. 22 Home Exam, due to Feb. 19 ## Solutions to AssignmentsSolution 1 Solution 2 Solution 3 Solution 4 ## ExercisesExercises from David Peleg's book ## Exam, Moed AlephMoed Aleph ## Moed BetMoed Bet ## Solution to Moed AlephSolution to Moed Aleph ## Solution to Moed BetSolution to Moed Bet ## LatexLatex 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 AlephThe exam (pdf format) A solution to moed aleph (pdf) ## Exam (Feb. 2014) - Moed BetThe exam (pdf format) A soution to moed bet (pdf) ## Exam (Feb. 2013) - Moed AlephThe exam (pdf format) A solution (pdf format) ## Exam (March 2013) - Moed BetThe exam (pdf format) A solution (pdf format) ## Exam (Jan. 2012) - Moed AlephThe exam (pdf format) A solution (pdf format) ## Exam (Feb. 2012) - Moed BetThe exam (pdf format) A solution (pdf format) ## Exam (Jan. 2011) - Moed AlephThe exam (pdf format) A solution (pdf format) ## Exam (Jan. 2011) - Moed BetThe exam (pdf format) A solution (pdf format) ## Exam (Feb. 2010) - Moed AlephThe exam (pdf format) A solution (pdf format) ## Exam (Feb. 2010) - Moed BetThe exam (pdf format) A solution (pdf format) ## Exam (March 09) - Moed AlephThe exam (pdf format) A solution (pdf format) ## Exam (May 09) - Moed BetThe exam (pdf format) A solution (pdf format) ## Exam (Feb. 07) - Moed AlephThe exam (Word document) A solution (pdf format) ## Exam (Feb. 07) - Moed BetThe exam (Word document) A solution (pdf format) ## Exam (Feb. 06) - Moed AlephThe exam (pdf format) A solution (pdf format) ## Exam (Feb. 05) - Moed AlephThe exam (pdf format) A solution (pdf format) A correction to the solution of question 3b (eml format - outlook message) ## Exam (Feb. 05) - Moed BetThe exam (pdf format) A solution (pdf format) ## Links to web-sites of previous yearsThe 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 |