Distributed Algorithms

0510.7406

 

 

http://www.eng.tau.ac.il./~boaz/magritte.siecle-lumieres.jpgAdministrative Information.

Lectures: Mondays 6-8, Kitot 206.

Lecturer: Boaz Patt-Shamir,  boaz@eng.tau.ac.il.

Prerequisite: Design & Analysis of Algorithms (510.6401), or equivalent

Final exam: June 27, 2pm.

Course URL (this page): http://www.eng.tau.ac.il/distalgs
Course mailing list (see instructions): http://listserv.tau.ac.il/archives/0510-7406-01.html

 

Objective of the Course.

Distributed algorithms are one natural extension of classical algorithms.  In this course, we will study algorithms that are run on a system of processors connected by communication links. The main questions that will guide us are the influence of locality and communication on the complexity and solvability of various tasks. The material will be explored from the theoretical perspective: the underlying system model is abstracted and simplified to enable us to state and prove rigorous assertions regarding the correctness and complexity of algorithms and tasks.

 

Topics. The course will include topics from the following list.

  • Leader election
  • Independent sets, matchings and  coloring
  • Spanning trees
  • Logical time
  • Clock synchronization
  • Datalink protocols
  • Sparse partitions
  • Self stabilization

 

Requirements.

1.     Homework will assigned every two weeks. The final grade will consist of 10% homework grades and 90% final exam.

2.     Each lecture, one of the students will be assigned as a scribe. This means that the student will be responsible to taking careful notes and publishing them in electronic form. The idea is to help all students to have a “standard” notebook for the course.  The student who takes notes is exempt from the current homework.

3.     In-class prsentations or a research-like paper may qualify instead of the exam. This option is to be coordinated personally with the instructor.

 

 Bibliography.

1.     Distributed Computing: A Locality-Sensitive Approach, D. Peleg (P). SIAM, 2000.  Main textbook.

2.    Distributed Algorithms, N. Lynch (L). Morgan Kaufmann, 1996

3.    Distributed Computing (Second Edition), H. Attiya and J. Welch (AW). Wiley InterScience, 2004.

 

Homework assignments.

Feb. 22 Homework 1: Leader Election on a ring. Due Mar. 8.

March 8 Homework 2: Tree algorithms. Due March 22.

 

Lecture notes.
Warning: these notes were not proofread, and may contain many errors!

Lecture 1: Introduction. Leader election. Scribe: Noa Zilberman.

Lecture 2: Maximal Independent Set (lecturer: Yuval Emek). Scribe: Andrei Grodozovski.

Lecture 3: Broadcast, convergecast and tree construction. Scribe: Yael Grossman.

Lecture 4: MST. Scribe: Ofir Regiano.

Lecture 5: Vertex coloring. Scribe: Andrei Grodozovski.

Lecture 6: MST lower bound. Scribe: Lior Zatlavi.

 

Prsentation schedule.

26/4

Jamming in Ethernets (Illya Rivkin)

Clock synchronization (Noa Zilberman)

3/5

Distributed selection (Misha Zabjenski)

Distributed mode computation (Lior Zatlavi)

10/5

Facility location (Assaf Heimann)

Vertex cover (Eyal Srebro)

17/5

MST with advice (Marat Teplitski)

Distributed matching (Eyal Ronen)

24/5

Quorum systems (Elya Dolev)

Approximate scheduling (Yael Grossman)

31/5

Distributed coloring (Ohn Tsarfati)

Stable marriage (Ofir Reginiano)

7/6

Median computation (Andrey Grodozovski)

Primal-dual scheduling (Guy Basteker)