Distributed Computing

0368442901

Winter 2004

Lecturer: Prof. Yehuda Afek 

 

 

Take home exams are in the exercise room (Schreiber 1st floor)

Please tell your friends that the course web page have been updated!!

1.      Checked and graded home-works are in Schreiber building floor 1 the zerox room.

2.      Below are the EXAM grade & Final Grade &mhome-works grades so far.

3.      Notice:  Devising a correct wait-free n processors Q (as in Question 6) from Fetch&Add and other objects with consensus number 2 (e.g., swap) is an open question !!!  A correct solution could be a very good basis for thesis (Master and or PhD).

 

שאלה 1א(5)

שאלה 1ב(5)

שאלה 2(15)

שאלה 3א(5)

שאלה 3ב(5)

שאלה 4(6)

שאלה 4(6)

שאלה 4(13)

שאלה 5א(10)

שאלה 5ב(10)

שאלה 6א(10)

שאלה 6ב(10)

ציון

 

 

 

ציון סופי

ת.ז.

 

 

 

 

 

 

 

 

 

 

 

 

בחינה

תרגיל 1

תרגיל 2

תרגיל 3

 

37281219

5

5

15

5

5

6

5

13

10

10

10

10

99

85

93

95

100

32863839

5

5

15

5

5

6

5

13

10

10

10

10

99

78

81

86

100

31413891

5

5

15

5

5

6

6

13

10

10

9

10

99

75

90

80

100

33495243

5

4

14

5

5

6

6

11

10

10

10

9

95

79

84

97

99

25434606

5

4

15

5

5

6

4

13

5

9

10

10

91

85

98

95

99

37217510

5

5

16

5

5

6

5

12

9

10

10

10

98

78

71

82

98

35679125

5

5

15

5

5

6

5

5

10

10

10

10

91

87

87

96

98

40038077

5

5

14

5

4

6

5

13

8

8

10

10

93

74

93

91

98

17560939

5

4

14

5

5

6

7

13

10

10

10

9

98

83

62

85

98

27150556

5

5

14

5

5

6

5

13

10

10

10

10

98

78

63

89

98

32289118

5

5

14

5

5

6

6

13

10

10

10

10

99

70

59

95

97

36047348

5

5

15

5

4

6

5

12

10

10

10

10

97

78

72

74

98

40303349

5

5

13

5

5

3

5

12

10

10

10

10

93

69

80

93

96

38896254

4.5

4.5

15

5

5

6

5

12

10

10

10

10

97

72

58

89

96

46648424

5

5

12

5

5

6

6

13

9

9

10

10

95

71

73

86

96

35762335

5

5

15

5

5

5

5

8

9.5

9.5

9

10

91

73

90

89

96

31399025

5

5

15

5

5

6

5

13

8

10

6

10

93

77

82

80

95

25561630

5

4

15

5

5

6

5

13

7

9

10

2

86

84

96

95

95

32861916

5

5

15

4

5

6

5

12

10

10

10

10

97

72

53

86

95

34774794

5

5

15

5

5

6

5

12

10

10

10

10

98

54

67

77

94

28429595

5

5

13

5

5

6

6

12

5

7

10

10

89

76

72

83

92

32950925

5

5

13

4

5

6

5

13

10

8

9

10

93

56

73

79

92

32961336

5

5

14

4

5

6

6

13

7

7

10

10

92

51

60

91

90

304271828

5

5

15

5

5

6

6

13

5

7

10

8

90

48

78

85

90

53044095

5

5

13

4

5

6

6

13

8

9

8

10

92

56

66

77

90

33803230

5

5

15

4

5

6

5

13

10

0

10

10

88

58

80

78

89

984081056

5

5

15

5

5

6

6

12

10

10

10

10

99

27

35

91

89

33044017

5

5

14

5

5

6

6

12

10

10

10

2

90

53

59

89

89

27348432

5

5

13

4

5

6

3

9

9

7

9

10

85

68

80

75

88

33677212

5

4

13

5

5

6

5

13

9

9

10

0

84

67

68

92

91

306787904

5

5

16

5

5

6

6

11

7

8

10

10

94

55

59

57

88

35884576

5

5

13

4

5

6

6

13

9

10

2

10

88

76

46

78

88

41855529

4.5

4.5

12

5

5

5

6

13

8

9

10

3

85

63

75

72

87

35730993

5

5

13

5

5

5

6

12

5

7

8

6

82

73

68

87

87

33829524

5

5

12

4

4

6

5

13

10

9

10

10

93

33

45

81

86

 

5

5

14

4

4

6

6

13

8

9

9

2

85

51

54

97

86

36291490

5

5

15

5

5

4

5

13

8

7

10

0

82

73

65

79

86

34051250

5

5

14

5

4

5

3

10

8

0

10

10

79

75

72

80

85

29365947

0

0

11

5

5

6

4

11

10

10

10

10

82

71

52

84

84

37536307

4.5

4.5

15

5

5

6

6

13

9

10

10

2

90

0

יבדק

98

83 not final

40975344

5

5

13

4

4

6

6

13

8

10

10

2

86

46

55

72

83

33821190

5

5

14

4

5

6

6

13

10

10

10

10

98

40

30

חסר

לא סופי79

310329156

5

4

14

5

5

6

6

5

7

8

10

2

77

71

64

78

82

34452052

4.5

4.5

13

4

5

6

3

9

7

8

8

10

82

45

66

72

82

31409568

4.5

4.5

15

5

4

6

3

8

5

3

7

7

72

70

68

77

84

312113095

5

5

12

5

5

2

5

10

9

8

8

2

76

40

41

75

75

319166690

5

5

11

5

4

6

6

13

5

5

3

7

75

35

42

67

73

36019735

5

5

12

4

5

6

6

13

5

0

10

10

81

22

22

43

79

308771617

4

4

10

4

4

0

5

10

9

5

4

7

66

52

48

65

69

33857756

4.5

4.5

11

4.5

4.5

1

3

12

0

0

4

9

58

75

55

74

69

32822686

5

4

11

4

5

4

5

6

5

6

2

0

57

55

71

62

66

34121434

4

4

7

4

5

6

5

3

7

0

10

3

58

57

47

76

66

 

 Q&A Regarding Homework 4

Homework 4 – Take home exam Due June 16th *****

Q&A Regarding Homework 3

Homework 3 pdf      

General Q&A  

HW1-Q2-Solution 

Q&A Regarding Homework 2

Homework 2 pdf      Due:  April 18th.

Q&A Regarding Homework 1.

Homework 1 pdf      Due:  March 21st.

Course Summary

A graduate level 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 asynchronous shared memory parallel machines.

In addition we will discuss the connections and relations between these two models.

Administrative Information

·       Lectures: Sunday 17:10-20:00,

·       ***  NEW Class Room: Orenstein 103 ***

·       Office Hours, by appointment (email) Sunday 14:00-15:00

Course Topics and Schedule (tentative)

DATE

TOPIC

Feb 29

Models, Broadcast & Echo

March 7

** PURIM **

March 14

Termination Detection, Snapshots, Synchronizers

March 21

Leader Election, ring networks

March 28

Leader Election Algorithms and Spanning tree algorithms

April     4

**  Pesach **

April   11

**  Pesach **

April   18

Computing the maximal independent set, rings and general graphs, upper and lower bounds

April   25

**  Yom Ha-Zikaron, Memorial day  **

May  2

Data link protocols, the sequence transmition problem and

End-to-End protocols

May   9

The consensus problem.  Algorithms and lower bounds

May   16

The shared memory model

May   23

The consensus problem, and its impossibility in asynchronous networks with one faulty processor

May   30

Wait-free synchronization, the shared memory hierarchy and universal constructions

June     6

Atomic Snapshots of shared memories, Immediate snap-shots

Time permitting

Simulating Shared memory in message passing

Time permitting

Lower bound techniques

 

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.