Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD2451 / pardis11 / Exercises and hand-ins

# DD2451, Parallel and Distributed Computing, Pardis, 2011

## Handin schedule

Handin 1: Out 4 Nov 16.00, return 11 Nov 16.00

Handin 2: Out 18 Nov 16.00, return 25 Nov 16.00

Handin 3: Out 2 Dec 16.00, return 9 Dec, 16.00

## Exercises and Hand-in Problems

### Lecture 1

• H&S ex 4, 5, 11, 13, 18, 19

### Lecture 2

• H&S ex 24, 25, 26, 28, 31

### Lecture 3

• H&S ex 35, 36, 40, 41, 43. Splitter exercises: Check lecture 1

### Lecture 4

• H&S ex 47, 50 (so far)
• Also: H&S ex 53, 54, 68

### Hand in 1

• Get it here (after 16.00)

### Lecture 5

• H&S ex 85, 86, 91, 222 (in appendix B), 224 (also in appendix B)

### Lecture 6

• H&S ex 102, 104 (can such a scenario arise in the lazy algorithm as wel1? In the lock-free algorithm? Why not?), 109, 112, 118

### Lecture 7

• Exercises are in the slides

### Hand in 2

• Get it here (a bit before 16.00 actually)
• In exercise 2 you may assume a) crash failures only and b) broadcasts are always completed. I.e. if A broadcasts m to B and C and neither B nor C fail then both B and C receive m. That is, a crash cannot cause A to send to B only and not to C (or vice versa).

### Lecture 10

• Exercises in slides 49-51

### Hand in 3

• Get it here (after 16.00)
• Hint for question 3: First part of the question may be a little cryptic. View the entwork graph as an ordinary graph with vertices (nodes) and edges (links). When running the algorithm the claim is that the labelling as determined by variable b eventually stabilizes in such a way that the graph with the labelling has a specific property. This could be, for instance: The labelling determines a Hamiltonian circuit, or the labelling determines a connected component (none of these apply, btw). Hope this helps.