Network Algorithms

0510.7425

 

 

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

Lectures: Tuesdays 4-7, Wolfson 134.

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

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

Final exam: January 28, 2pm.

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

 

Objective of the Course.

We will study algorithms that are run on a network 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.

  • Trees: construction and use
  • Routing
  • Independent sets, matching, coloring
  • Logical and physical time: synchronizers
  • Spanners and sparsifiers
  • Wireless protocols
  • Datalink protocols
  • Self-stabilization
  • Buffer management

 

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.

 

 Bibliography.

1.     Distributed Computing: A Locality-Sensitive Approach (e-book available, see instructions), 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.

1.       Problem Set 1: due November 6. Solutions.

2.       Problem Set 2: due November 20 27. Solutions.

3.       Problem Set 3: due December 18. Solutions.

4.       Problem Set 4: due January 15. Solutions.

 

Lecture notes (in Hebrew, not proofread).

1.      Lecture 1: Intro, broadcast, convergecast, BFS. Scribe: Mor Baruch.

2.     Lecture 2: Leader election in a network, downcast, upcast, pipelining, unweighted all-pairs shortest paths. Scribe: Amir Levi.

3.     Lecture 3: Minimum Spanning Tree. GHS, the Red-Pipelining algorithm. Scribe: Rachel Stahl.

4.     Lecture 4: Maximal Independent Set and -coloring. Scribe: Yuval Carmel.

5.     Lecture 5: Synchronizers. Clock synchronization. Scribe: Daniel Ephrat.

6.     Lecture 6: Vertex coloring. Deterministic coin tossing, lower bound for 3-coloring a ring. Scribe: Gonen Jerbi.

7.     Lecture 7: Communication complexity. Lower bound on exact diameter computation. Scribe: Nadav Krispin.

8.     Lecture 8: Lower bound on MST and shortest-paths tree computation. Scribe: Yakir Sudri.

9.     Lecture 9: Sparse covers, basic constructions. Scribe: Mor Baruch.

10.   Lecture 10: Hierarchical constructions, distributed controller. Scribe: Daniel Ephrat.

11.    Lecture 11: Routing: Basic framework, trees, bounded distance, hierachical. Scribe: Rachel Stahl (scribe 2: Amir Levi).

12.   Lecture 12: Self Stabilization. Scribe: Harel Cohen.

 

Final exam