|
Tel Aviv University
|
Fall 2002 Lecturer: Prof. Yehuda Afek |
No classes as long as there is a strike.
Class room is Schreiber 006
Course Summary
A graduate course exploring topics from the current literature in distributed computing, focusing on theoretical issues: models, upper and lower bounds, and proof methods. Two major topics:
1. Distributed algorithms for data communication networks
2. synchronization algorithms for {\em asynchronous} shared memory parallel machines.
In addition we will discuss the connections and relations between these two models. Hopefully we will also go over a real distributed algorithm such as BGP.
Administrative Information
Lectures: Sunday 17:00-20:00, Room: Schreiber 006
Course Topics and Schedule (tentative)
|
DATE |
TOPIC |
|
Oct 28 |
Models, Broadcast & Echo |
|
Nov 4 |
Termination Detection, Snapshots, Synchronizers |
|
Nov 11 |
Leader Election, ring networks |
|
Nov 18 |
Leader Election Algorithms and Spanning tree algorithms |
|
Nov 25 |
Computing the maximal independent set, rings and general graphs, upper and lower bounds |
|
Dec 2 |
Data link protocols, the sequence transmition problem and End-to-End protocols |
|
Dec 9 |
The consensus problem. Algorithms and lower bounds |
|
Dec 16 |
The shared memory model |
|
Dec 23 |
The consensus problem, and its impossibility in asynchronous networks with one faulty processor |
|
Dec 30 |
Wait-free synchronization, the shared memory hierarchy and universal constructions |
|
Jan 6 |
Atomic Snapshots of shared memories, Immediate snap-shots |
|
Jan 13 |
Simulating Shared memory in message passing |
|
Jan 20 |
Distributed Shortest Path Algorithms, & the BGP example |
See Course outline with references (pdf)
Grade
The grade weighting for the semester will be:
|
Home Works |
35% |
|
Take home exam: |
65% |
These weights are subject
to change.