# Selected Topics in Distributed Computing

**2008, winter semester. Master course.**

**Prerequisites: none.**

**Note: this course is independent from the course Distributed Algorithms.**

## News

**Last updated: January 18 ^{th}, 2009**

- Added pdf version of the slides “Implementing registers”
- Exercise 9 (anonymous implementations) added (with solution)
- Exercise 6 updated (small correction to the solution)
- Final exam from the last year: pdf
**Information:**the consultations before the exam are at the usual time, i.e., Friday from 11.00 to 12.00 (INR 313). Note that the**last**consultations before the exam are on January 16th- Lecture slides and exercises are now complete
- December 15
^{th}lecture slides available - Updated exercises 6 and 7
- Updated exercises 2–5
- Course slides (Introduction and Implementing Registers, Part 1) and exercises 1 and 2 updated
- The preliminary version of the course web page has been set up. Note that lecture slides and/or course details might be updated later.

## Dates and schedule

- The course is given on Mondays, 9.15−11.00, in BC03
- The exercises are given on Mondays, 11.15−12.00, in BC03

## Teaching team

**Professor:**Rachid Guerraoui, office INR 310, web page**Postdoc:**Seth Gilbert, office INR 311, web page

## Slides and exercises

Date | Lecture | Slides | Exercises |
---|---|---|---|

September 15^{th} | Introduction | ppt pdf | — |

September 29^{th} October 6 ^{th} October 13 ^{th} | Implementing Registers | Part 1: ppt pdf Part 2: ppt pdf | Exercise 1 (with solution): pdf Exercise 2 (with solution): pdf Exercise 3: pdf (*) |

October 27^{th} | The Power of Registers | ppt pdf | Exercise 4: pdf, solution: pdf |

November 3^{rd} | The Limitations of Registers | ppt pdf | Exercise 5 (with solution): pdf |

November 10^{th} | Universal Constructions | ppt pdf | Exercise 6 (with solution): pdf |

November 17^{th} | Implementing the Consensus Object with Timing Assumptions | ppt pdf | Exercise 7 (with solution): pdf |

November 24^{th} | Object Implementation out of Faulty Base Objects | ppt pdf | Exercise 8: pdf, solution: pdf |

November 24^{th} | Computing with Anonymous Processes | ppt pdf | Exercise 9 (with solution): pdf |

December 1^{st} | Transactional Memory | — | |

December 15^{th} | Implementing Registers Using Byzantine Objects | ppt pdf | Exam dry-run (with solutions): pdf |

(*) Solution for Exercise 3: if you understand the lecture, you should know the answers.

## References

Preliminary references (more will be added later):

- Herlihy, M. P. Wait-free synchronization.
*ACM Transactions on Programming Languages and Systems*, 13(1):124–149, January 1991. - Herlihy, M. P., and Wing, J. M. Linearizability: a Correctness Condition for Concurrent Objects.
*ACM Transactions on Programming Languages and Systems*, 12, 3 (1990), 463-492. - Jayanti, P., Wait-free computing. In
*Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG'95)*, Vol. 972 of LNCS, Springer Verlag, 1995, pp. 19–50. (on-line version not available) - Lamport, L. On Interprocess Communication−Part I: Basic Formalism, Part II: Algorithms.
*Distributed Computing*, 1, 2 (1986), 77–101.

Auxiliary documents:

—-

## Grades and Exam

The final exam will be written and closed-book. It will take place on 22.01.2009 (Thursday) at 14:15 in room CM1120.

Final exam from the last year: pdf