Differences

This shows you the differences between two versions of the page.

Link to this comparison view

education:stidc [2009/01/18 15:39]
education:stidc [2009/01/18 15:39] (current)
Line 1: Line 1:
 +====== 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<​sup>​th</​sup>,​ 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: {{stidc07-exam.pdf|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<​sup>​th</​sup>​ 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, [[http://​lpd.epfl.ch/​rachid|web page]]
 +  * **Postdoc:​** Seth Gilbert, office INR 311, [[http://​lpd.epfl.ch/​sgilbert|web page]]
 +  * **Assistants:​** Michal Kapalka, office INR 313, [[http://​lpd.epfl.ch/​kapalka|web page]], Aleksandar Dragojevic, office INR 313, [[http://​lpd.epfl.ch/​dragojev|web page]]
 +
 +----
 +
 +
 +===== Slides and exercises =====
 +
 +^     ​Date ​        ​^ ​  ​Lecture ​  ​^ ​  ​Slides ​  ​^ ​  ​Exercises ​  ^
 +|   ​September 15<​sup>​th</​sup> ​  | Introduction | {{stidc08-introduction.ppt|ppt}} {{stidc08-introduction.pdf|pdf}} ​ |   ​--- ​  |
 +|   ​September 29<​sup>​th</​sup>​ \\ October 6<​sup>​th</​sup>​ \\ October 13<​sup>​th</​sup> ​  | Implementing Registers | Part 1: {{stidc08-registers-impl.ppt|ppt}} {{stidc08-registers-impl.pdf|pdf}} ​ \\ Part 2: {{stidc08-writing-while-reading.ppt|ppt}} {{stidc08-writing-while-reading.pdf|pdf}} ​ | Exercise 1 (with solution): {{stidc08-ex1.pdf|pdf}} \\ Exercise 2 (with solution): {{stidc08-ex2.pdf|pdf}} \\ Exercise 3: {{stidc08-ex3.pdf|pdf}} (*)  |
 +|  October 27<​sup>​th</​sup> ​  | The Power of Registers | {{stidc06-registers-power.ppt|ppt}} {{stidc06-registers-power.pdf|pdf}} | Exercise 4: {{stidc08-ex4.pdf|pdf}},​ solution: {{stidc08-ex4-pres.pdf|pdf}} ​  |
 +|  November 3<​sup>​rd</​sup> ​  | The Limitations of Registers | {{stidc07-registers-limit.ppt|ppt}} {{stidc07-registers-limit.pdf|pdf}} | Exercise 5 (with solution): {{stidc08-ex5.pdf|pdf}} ​  |
 +|  November 10<​sup>​th</​sup>​ | Universal Constructions | {{stidc07-universal.ppt|ppt}} {{stidc07-universal.pdf|pdf}} | Exercise 6 (with solution): {{stidc08-ex6.pdf|pdf}} ​ |
 +|  November 17<​sup>​th</​sup>​ | Implementing the Consensus Object with Timing Assumptions | {{stidc06-consensus.ppt|ppt}} {{stidc06-consensus.pdf|pdf}} | Exercise 7 (with solution): {{stidc08-ex7.pdf|pdf}} ​ |
 +|  November 24<​sup>​th</​sup>​ | Object Implementation out of Faulty Base Objects | {{stidc06-faulty-objects.ppt|ppt}} {{stidc06-faulty-objects.pdf|pdf}} | Exercise 8: {{stidc08-ex8.pdf|pdf}},​ solution: {{stidc08-ex8-pres.pdf|pdf}} ​ |
 +|  November 24<​sup>​th</​sup>​ | Computing with Anonymous Processes | {{stidc07-anonymous.ppt|ppt}} {{stidc07-anonymous.pdf|pdf}} | Exercise 9 (with solution): {{stidc08-ex9.pdf|pdf}} ​ |
 +|  December 1<​sup>​st</​sup>​ | Transactional Memory | {{stidc08-tm.pdf|pdf}} |  ---  |
 +|  December 15<​sup>​th</​sup>​ | Implementing Registers Using Byzantine Objects | {{stidc08-byzantineobjects.ppt|ppt}} {{stidc08-byzantineobjects.pdf|pdf}} ​  | Exam dry-run (with solutions): {{stidc08-dryrun.pdf|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. [[http://​www.cs.brown.edu/​~mph/​Herlihy91/​p124-herlihy.pdf|Wait-free synchronization.]] //ACM Transactions on Programming Languages and Systems//, 13(1):​124--149,​ January 1991.
 +  * Herlihy, M. P., and Wing, J. M. [[http://​www.cs.brown.edu/​people/​mph/​HerlihyW90/​p463-herlihy.pdf|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. [[http://​research.microsoft.com/​users/​lamport/​pubs/​interprocess.pdf|On Interprocess Communication−Part I: Basic Formalism, Part II: Algorithms.]] //​Distributed Computing//,​ 1, 2 (1986), 77--101.
 +
 +Auxiliary documents:
 +
 +  * A tutorial / lecture notes for the course: {{intro.ps|introduction}} {{chap1.ps|chapter 1}} {{chap2.ps|chapter 2}} {{chap3.ps|chapter 3}}
 + 
 +----
 +
 +===== 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: {{stidc07-exam.pdf|pdf}}