The course is an advanced course in parallel and distributed computations, dealing with the following subjects:

• models, fundamental concepts and analytical methods for parallel and distributed systems, fundamental limitations and impossibility results
• algorithms and protocols for commonly occurring computing problems in communication, synchronisation, fault tolerance, coordination, consensus and replication, sharing and security, and distributed storing.

The course assumes interest for programming and theoretical issues.

After passing the course, the student should be able to

• account for models, limitations and fundamental concepts within parallel computations with communication based both on message passing and shared memory
• apply and adapt existing algorithms and develop new algorithms for execution on parallel and distributed machines and analyse these algorithms with regard to correctness, security and performance.

Course Format

Lectures: There are 14 2-hour lectures, two per week. Reading material, in textbook, web, or papers, is assigned for each lecture.

Exercises: Each lecture has assigned exercises, some for training only, most are for hand-in. Training exercises are voluntary. Deadline for each week's hand-in exercises is Friday 15:00 - right before the corresponding exercise session. We apply peer review, with review deadline following Wednesday 18:00. The week's exercises are discussed in the Friday exercise session.

Labs: Labs are done asynchronously. That is, no fixed time is allotted for the labs, it is up to yourself to plan your time and make sure the labs are handed in at the appropriate time. Labs are done pairwise. We are using PDC facilities in order to get access to machines with more interesting architecture and larger number of cores than what the regular laptops offer. An extra PDC intro lecture is scheduled during the first week of the course, and a PDC live support session is scheduled during the third week of the course. Lab presentations will be scheduled separately.

Seminars: Each student is strongly encouraged to present a research paper of own choosing at one of the four scheduled seminar sessions. Presenting a research paper is mandatory for doctoral students enrolled in FDD3008. Scheduled seminars will be announced or cancelled based on the number of students who sign up to present. Check under Examination for details.

Discussions: Use of the Canvas discussion feature is encouraged. Try to make it a habit to submit at least one reasonably well thought out comment per lecture. This can be either by initiating a new discussion thread or by commenting on an existing one.

Examination: Is oral, check under Examination for details.

Attendance

Attendance at lectures and exercise sessions is strongly recommended but not mandatory. The material is not easy and a good grade in the course is strongly correlated with activity. Beyond attending lectures and exercise sessions, we recommend:

• asking questions in real time,
• browsing through slides the day before the scheduled lecture, or even earlier, and
• carefully reading and re-reading indicated sections of the course book and other course material (try spaced repetition).

Attendance at announced seminars is mandatory.

Course Requirements

The course returns TEN2, 4.5 hp and UPP1, 3 hp. TEN2 grade scale is A, B, C, D, E, Fx, F and UPP1 is pass/fail. The TEN2 grade is determined by the oral exam. For UPP1 the requirements are the following:

1. Attendance at all announced seminars.
2. All mandatory exercises handed in and passed (including extra exercises if applicable).
3. All peer reviews handed in and passed.
4. All labs handed in, presented, and passed.

Additional adjustments in either direction may in exceptional situations be done based on exercise and peer review performance, and contributions to the discussions.

PhD Students

Postgraduate students (using course code FDD3008) must pass the course with minimum grade C on the oral exam, and must receive a VG grade for a paper presentation during a seminar. Otherwise, requirements are the same.

Course participants must use an account at PDC to access the supercomputer used for labs. Students who do not already have an account must apply for one. Students who already have PDC accounts should email PDC support and ask to get added to the allocation for DD2443.

The main textbook is

• Maurice Herlihy, Nir Shavit, Victor Luchangco, Michael Spear: The art of multiprocessor programming, 2nd Edition, Morgan Kaufmann 2020.

The textbook is available online here and is downloadable as PDF from KTH computers or when connected via Eduroam at KTH campus.

We also use online course material from Roger Wattenhofer, ETHZ, see the reading lists in Canvas for the relevant lectures.

Other material (papers, lecture notes) will be made available in Canvas as the course pushes on.

Students at KTH with a permanent disability can get support during studies from Funka:

Funka - compensatory support for students with disabilities

• UPP1 - Seminars, assignments and labs, 3.0 credits, grading scale: P, F
• TEN2 - Oral exam, 4.5 credits, grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

If the course is discontinued, students may request to be examined during the following two academic years.

Oral Examination

Besides a number of mandatory elements detailed below, the main course evaluation is through an individual 1-hour oral examination during the exam weeks following the course. The exam covers the entire body of course material presented in class, in slides or handouts, in exercises, and in the required reading material. The exam grading scale is A-F.

During an oral exam, the student first receives a written description of a high-level open-ended exam problem. The student is then given 30 minutes alone in a study room (under supervision) to think about the problem and optionally write down some notes. No resources other than pen and paper may be used during this time. After 30 minutes alone with the problem text, the student will be asked to present an attempt at solving the given problem. This will be an interactive process, where the examiner may interrupt the student to ask for clarification or lead the discussion towards some aspect of the problem solution in accordance with the intended learning outcomes. The discussion will last around 25 minutes, after which the student will be asked to wait outside the exam room for a few minutes while an exam grade is determined.

Exercises and Exercise Peer Review

Exercise and exercise peer review hand-in by the assigned deadlines is mandatory. The mandatory exercises to be handed in are marked clearly in the exercise sheets. All such assigned exercises must be attempted and reviewed. Those who missed the deadline, or did not hand in a solution at all, or did not hand in a peer review in time, must hand in solutions to extra exercises (found at the end of each exercise sheet) besides the mandatory ones.

There are no requirements on correctness of exercise solutions, but a serious effort must be made and shown. If you did not manage to solve the exercise, at least show your effort and where you got stuck. Insufficient effort may lead to being assigned extra exercises to solve. Solutions to exercises must explain the reasoning in an adequate manner - plain yes/no answers will do only if explicitly instructed. This applies to both the exercises and the peer reviews. Exercises and peer reviews are not graded, but consistent outliers in either direction may be taken into account in the final course grade. 

You are allowed to discuss the exercises with your peers but you must produce the actual written answers by yourself, without support of AI tools such as ChatGPT. Do not plagiarize and be sure to declare any sources you have used.

Labs

Labs are done in groups of two whenever possible, otherwise individually. Written lab solutions must be handed in and presented orally and are graded pass/fail. Lab groups must produce the written solutions themselves, without support of AI tools such as ChatGPT. Do not plagiarize and be sure to declare any sources you have used.

Seminars

Research paper presentations at one of the seminars are voluntary for DD2443 students (but mandatory for FDD3008 students) and graded on the scale [VG,G]. Seminar presentation grades will be taken into account during exam grading. For seminars the following grading criteria apply:

• For G, the presentation must bring out the basic contributions and motivational context of the paper in a manner that is comprehensible to the majority of students.
• For VG, the presentation must bring out the contributions and motivational context of the paper at a technically more advanced level, and communicate the insight in a manner that is well adapted to the audience.

Seminar attendance is mandatory. 

Late Assignments

• What happens if you hand in your exercise solutions late?
  • See above: You will need to hand in solutions to the extra exercises of the corresponding exercise sheet.
• What happens if you hand in your peer review late?
  • See above: You will need to hand in solutions to the extra exercises of the corresponding exercise sheet.
• What happens if you submit a lab solution late?
  • You will be assigned additional lab tasks that must be performed and documented.
• What happens if you're unable to attend an announced seminar?
  • Write a short essay, 300-400 words, pd, 11 pt, single line, summarizing one of the papers, or bodies of work, presented at the seminar: What problem is addressed? Why is it important (or not)? How is the problem approached? What are the key results?

Grading Criteria

For each of the grades listed below, the following criteria apply:

• For E: Able to account for basic concepts, definitions, and results in the area of parallel and distributed computation, and apply these concepts, definitions, and results to simple problems.
• For D: In addition to above, able to apply the concepts, definitions, and results to a more advanced problem within one of the parallel and distributed computation subareas.
• For C: In addition to above, able to apply the concepts, definitions, and results to advanced problems within both the parallel and distributed computation subareas.
• For B: In addition to above, able to correctly formulate and explain the basic ideas of one key proof construction presented in the course.
• For A: In addition to above, able to to correctly formulate and explain the basic ideas of several key proof constructions presented in the course within both the parallel and distributed computation subareas.

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

The official course syllabus is valid from the autumn semester 2023 in accordance with the decision by the Head of School: J-2023-0605.

Date of decision: 03/04/2023

In the distributed systems part of the of the course, this course offering focuses on teaching the Raft fault-tolerant distributed consensus algorithm rather than Paxos as previous years. These two algorithms are equivalent in functionality and fault tolerance, but Raft has been shown to be more straightforward to understand.