Differences
This shows you the differences between two versions of the page.
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}} |