Distributed Computing

0368-4429-01

Winter 2006 (2005/2006)

Lecturer: Prof. Yehuda Afek 

 

לתשומת לבכם, בשנה הבאה יתקיים סמינר מתקדם בסינכרון וזכרון משותף 0368-5025-01                                                                                              

*** Grades correction***:  The following student grades had an error in the course final grade calculation, and are now corrected as follows:

Student ID #

Course Final Grade

040427312

94

061211249

87

042345686

74

305913659

73

304201031

68

Final Grades:

 

HW1

HW2

HW3

HW4

exam q1

exam q2

exam q3

exam q4

exam q5

exam final

Final Course Grade

034796037

100

111

100

98

35

9

10

15

30

99

100

040770919

87

112

100

100

35

10

10

15

30

100

100

307019398

64

89

100

97

35

10

10

15

30

100

100

304442254

71

79

88

84

35

10

10

15

30

100

97

039062021

90

94

98

94

35

10

2

15

30

92

99

318032109

44

106

95

86

35

8

10

15

28

96

100

039045679

95

104

90

81

35

9

2

15

27

88

97

307026948

64

59

95

72

35

8

10

15

30

98

95

036383461

86

71

93

83

28

9

10

13

28

88

95

040427312

 

115

100

95

14

10

10

15

29

78

84

038589511

80

113

92

98

15

10

9

15

28

77

93

066452541

78

59

93

90

13

10

10

8

26

67

83

038750428

66

111

95

93

12

10

10

15

26

73

90

061211249

63

108

92

 

14

9

9

12

30

74

80

034213058

52

56

80

82

32

10

4

10

25

81

86

066618752

72

54

60

90

12

10

10

8

26

66

78

031777519

75

76

85

88

22

10

2

10

27

71

84

032321820

93

111

97

95

5

10

10

10

26

61

83

017106725

69

81

90

87

12

9

9

10

26

66

82

040686974

56

83

85

76

10

10

10

10

29

69

82

028697456

45

87

80

79

15

8

10

5

27

65

80

032365215

43

80

94

64

24

8

4

10

24

70

82

032825879

67

70

90

84

14

9

3

15

26

67

81

040685844

40

81

82

77

18

7

3

15

28

71

83

200435287

60

59

94

93

15

8

4

15

26

68

82

043144179

68

87

86

77

4

9

10

15

26

64

80

021639646

58

55

84

84

13

9

4

15

26

67

79

036363984

71

81

88

83

13

8

4

10

25

60

78

039486691

50

78

88

83

14

8

9

15

14

60

77

039649447

71

23

93

87

13

9

10

10

20

62

79

306312281

70

67

84

65

12

9

4

10

26

61

75

042345686

62

 

92

80

14

10

10

5

17

56

67

060716933

61

88

84

97

4

10

10

5

25

54

76

305913659

70

 

86

85

13

7

8

8

17

53

65

011924818

58

79

71

68

13

10

10

8

17

58

73

014754741

35

60

82

71

18

7

2

10

25

62

75

317349728

80

97

93

84

4

7

7

8

20

46

72

304201031

91

 

63

50

12

10

10

15

5

52

63

303967764

54

67

93

58

4

10

5

5

13

37

61

060749298

41

71

82

62

7

9

9

0

10

35

60

The final grade took into account only the 3 best homeworks for each, and in addition there is a factor calculated in.

Exams are in the zerox room.

Graded Ex 4 are in the copy room 1st floor Schreiber (upper left bin)

 

 

 

 

QA take home exam 

** Another Exam extension:  Every body gets an extra 24 hours on his / her deadline to submit the exam.  Standard deadline is June 20th.

Exam extension:  Every body gets an extra 24 hours on his / her deadline to submit the exam.

Take home exam Due June 18 19, 20 to Larisa at Schreiber room 213.

Homework 4 Due June 11 in class.

Some slides from Gadi Taubenfeld lecture on Mutual Exclusion

Some notes from the Mutual Exclusion Presentation

FYI:  Take home exam will be given out on June 11 and you will have to turn it in on June 18.

Homework 3 Due May 14 in class. Q&A on homework 3

Homework 2 Due April 23 in class. Q&A on homework 2

Homework 1 Question 3 Solution

Homework 1 Due March 26 in class.  Q&A on homework 1

Winter 2005 Course page

Solutions must be typewritten !!

Course Summary

A graduate level course exploring current and recent topics from the 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 (Message Passing)

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, Schreiber 006

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

Course Topics and Schedule (tentative, subject to change)

DATE

TOPIC

March 5

Models, Broadcast & Echo

March 12

Termination Detection, Snapshots, Synchronizers      Snapshot paper pdf

March 19

Leader Election, ring networks, unidirectional case

March 26

Leader Election Algorithms and Spanning tree algorithms

April 2

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

April 23

Data link protocols, the sequence transmition problem and

End-to-End protocols  and another pdf

April 30

The consensus problem.  Algorithms and lower bounds

May 7

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

May 14

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

May 21

Atomic Snapshots of shared memories, Immediate snap-shots,

May 28

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson,  Lamport-87

June 4

Simulating Shared memory in message passing, Randomized Consensus.

June 11

Lower bound techniques (log * n for maximal independent set on ring of size n).

Time permitting

Renaming, Eventually connected end-to-end STP, Concurrent Time Stamps,

 

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.