|
Tel Aviv University
|
Fall 2002 Lecturer: Prof. Yehuda Afek = |
Take
home exam (ps).
|
Final |
Exam |
Ex2 |
Ex1 |
I.D. |
|
|
|
|
|
|
|
100 |
115 |
9 |
9 |
307321943 |
|
100 |
113 |
8.5 |
9.5 |
32798258 |
|
100 |
108.5 |
7.5 |
13 |
312832850 |
|
100 |
107.5 |
9 |
11 |
37536810 |
|
100 |
107.5 |
8.5 |
8.5 |
304468051 |
|
99 |
103 |
9 |
9 |
32002032 |
|
99 |
103 |
8 |
9.5 |
31819717 |
|
98 |
100 |
8.5 |
8.5 |
310337159 |
|
97 |
104 |
7.5 |
6.5 |
33749714 |
|
97 |
101.5 |
8 |
7.5 |
34446302 |
|
97 |
100.5 |
8 |
8 |
25754854 |
|
97 |
100 |
8 |
7.5 |
310055959 |
|
97 |
97 |
6.5 |
7.5 |
34793091 |
|
97 |
96 |
7 |
10 |
34179481 |
|
97 |
96 |
8.5 |
8 |
306078957 |
|
97 |
96 |
6.5 |
9 |
38566469 |
|
97 |
94 |
8.5 |
7.5 |
28580090 |
|
96 |
94 |
6 |
9 |
308874155 |
|
95 |
92 |
7.5 |
6.5 |
27460427 |
|
94 |
94 |
7 |
5 |
17118746 |
|
93 |
94 |
7 |
3.5 |
27963032 |
|
93 |
89.5 |
7.5 |
7 |
32867038 |
|
93 |
86 |
8 |
7.5 |
25436718 |
|
92 |
97 |
4 |
2.5 |
303867949 |
|
92 |
94 |
5 |
5.5 |
56432818 |
|
92 |
94 |
5 |
5.5 |
304321375 |
|
92 |
89 |
7 |
7 |
28899375 |
|
92 |
85 |
9 |
6.5 |
35893478 |
|
91 |
80 |
8.5 |
7.5 |
35849298 |
|
91 |
79 |
8.5 |
7.5 |
34102202 |
|
90 |
87 |
5.5 |
6 |
33864992 |
|
90 |
86 |
5.5 |
6.5 |
3840400 |
|
90 |
84 |
7.5 |
6 |
310004791 |
|
90 |
81 |
8.5 |
5 |
28990281 |
|
89 |
86 |
4.5 |
7 |
308799733 |
|
89 |
78 |
7 |
7 |
25599762 |
|
88 |
84 |
7 |
3.5 |
32342669 |
|
88 |
80 |
6.5 |
6 |
27479930 |
|
86 |
77 |
6.5 |
3.5 |
23632193 |
|
86 |
71.5 |
7 |
5 |
304051840 |
|
86 |
71 |
6.5 |
5.5 |
28865889 |
|
85 |
80 |
7 |
0 |
307656017 |
|
84 |
74 |
3.5 |
6 |
13514682 |
|
38 |
0 |
5 |
5.5 |
43119148 |
|
35 |
0 |
4 |
4.5 |
34943050 |
|
26 |
0 |
0 |
4 |
28489946 |
|
25 |
0 |
0 |
3.5 |
17549106 |
Q&A
regarding the take home exam
Ben-Or’s Byzantine agreement
protocol
Proof for the 1st
question of the 1st homework.
Homework DUE January 13th ! (one
week postponement)
Second homeworks (ps).
Questions
& Answers regarding homework 2
Questions
& Answers regarding homework 1
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 |
|
Dec 2 |
Leader Election, ring networks |
|
Dec 9 |
Leader Election Algorithms and Spanning tree algorithms |
|
Dec 16 |
Hanucka |
|
Dec 23 |
Computing the maximal independent set, rings and general graphs, upper and lower bounds |
|
Dec 30 |
Data link protocols, the sequence transmition problem and End-to-End protocols |
|
Jan 6 |
The consensus problem. Algorithms and lower bounds |
|
Jan 13 |
The shared memory model |
|
Jan 20 |
The consensus problem, and its impossibility in asynchronous networks with one faulty processor |
|
Jan 27 |
Wait-free synchronization, the shared memory hierarchy and universal constructions |
|
Feb 3 |
Atomic Snapshots of shared memories, Immediate snap-shots |
|
Feb 3 |
Simulating Shared memory in message passing |
|
? we will see |
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.