DD2451, Parallel and Distributed Computing, Pardis, 2011
Course Memo
Content and Goals
Advanced course in computer science on the theory, algorithms, and techniques of parallel and distributed computing systems. Focus is on principles and algorithms and somewhat less on practical systems construction. The goals of the course are:
- To understand and account for models, limitations, concepts and algorithms in the area of message passing and shared memory concurrency, and to apply this understanding to example systems and algorithms
- To analyze parallel and distributed algorithms for correctness, performance, reliability, and security.
Prerequisites
The course does not have formal prerequisites. Target audience is D4, F4, and the MD line of SU. Familiarity with algorithms and their theory, basic probability theory, and basic mathematical discourse in cs, and programming will be very useful. We assume a level corresponding to the required courses of the KTH D and/or F programs.
Postgraduate Version of the Course
The course is also given as an postgraduate course at the introductory level. The course code and name for that course is FDD3008 Distributed Algorithms. For FDD3008 some additional course requirements apply, to be detailed.
Professor
Mads Dam is responsible for the course and principla lecturer. Reach him at mfd@kth.se or at his office 4416 at Nada. Safest is to call in advance and check if he is in.
Schedule
| Lecture 1 |
24 Oct |
10-12 |
D35 |
Introduction, mutual exclusion, locks |
| Lecture 2 |
27 Oct |
13-15 |
B23 |
Concurrent objects, linearization, sequential consistency |
| Lecture 3 |
31 Oct |
10-12 |
D42 |
Registers, snapshots |
| Lecture 4 |
2 Nov |
13-15 |
E34 |
Consensus, I |
| Lecture 5 |
8 Nov |
13-15 |
E31 |
Consensus, II |
| Lecture 6 |
10 Nov |
15-17 |
Q17 |
Fault tolerance, I |
| Lecture 7 |
14 Nov |
13-15 |
D35 |
Fault tolerance, II |
| Lecture 8 |
16 Nov |
15-17 |
D42 |
Leader election |
| Presentations |
18 Nov |
10-12 |
V33 |
|
| Lecture 9 |
21 Nov |
10-12 |
D35 |
Spanning trees, aggregation |
| Presentations |
23 Nov |
15-17 |
V23 |
|
| Lecture 10 |
25 Nov |
10-12 |
E36 |
P2P systems, DHT's |
| Lecture 11 |
28 Nov |
10-12 |
D35 |
Vertex colouring, perhaps |
| Presentations |
1 Dec |
10-12 |
D34 |
|
| Lecture 12 |
5 Dec |
10-12 |
D35 |
TBD |
| Presentations |
6 Dec |
10-12 |
Q31 |
|
A plan of the content of the lectures will be made available on the course home page.
Course material
Main textbook is
- Maurice Herlihy, Nir Shavit: The art of multiprocessor programming, Morgan Kaufmann 2008.
Other useful references - among many:
- Hagit Attiya, Jennifer Welch: Distributed Computing: Fundamentals, Simulations and Advanced Topics, McGraw-Hill Publishing, 2004. Focus on theory and lower bounds.
- David Peleg: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics (SIAM), 2000. Also theoretical.
- George Coulouris, Jean Dollimore, Tim Kindberg, Gordon Blair: Distributed Systems, Concepts and Design. Pearson 2012. This is a very systems-oriented text, too superficial for our use, but lots of useful background reading.
- Christian Cachin, Rachid Guerraoui, Luis Rodrigues: Reliable and secure Distributed Programming, 2n ed., Springer 2011. Another very good textbook. Theory focus. Covers some security-oriented material we will not cover in the course.
Other material, course notes and papers, will be made available on the course home page as we move on.
Registration
We use rapp to manage course credits etc. Many categories of students may take this course, and different students might face different administrative problems. We encourage each student to ensure that he/she is properly registrered for the course and that no administrative problems arise in connection with taking the course, or getting it properly credited.
Examination
There is no final exam. Examination will be through homework sets. Three sets of handins are planned at this time. For those interested in a higher grade there may be a possiblity to prepare a student lecture.
The Nada Code of Honor applies to these homework problems but there are also some rules specific to this course. These rules are available electronically from the course home page.
The grade determined by the score on the homework is final and the deadlines for handing in the solutions are normally not negotiable. Late solutions are accepted with some penalties and limitations described in the rules for the homework sets. Some circumstances such as severe illness can be taken as an excuse for late homework, while lack of time due to work outside the university or many parallel courses can not. If you feel you have a good reason to hand in homework late, please contact the lecturer as soon as possible.
Course Web
Information and changes concerning the course will be continuously published at the course home page.
