Course syllabus

Course Assistants:

• Huaifeng Zhang, huaifeng [at] chalmers [dot] se
• Kåre von Geijer, karev [at] chalmers [dot] se

TA office hours for assistance on the lab:

Every group has to (MANDATORY) book a slot for the lab from the provided times in the course calendar. You need to choose a time slot no later than January 29th. If you do not choose a time slot by then, your group will be assigned to an empty time slot. It is also possible to drop in to additional lab sessions to ask questions (provided that the day's session is not fully booked).

Email support will not be provided for code-related issues. Please ask your questions during the lab sessions.

Course Hours/Place:

• Mondays 10:00-11:45, EL42 
• Wednesdays 10:00-11:45, EL42 or EL41 or EL43 
• Friday 10:00-11:45, EL41, EL42, EC, SB-L216, SB-L200 or SB-L300

Please check TimeEdit for the exact lecture room location.

The course starts on Monday, January 15th. 

Please check frequently the Course Schedule for updates. 

Lab:

The lab is to be done in groups of 2 and is due on the 18th of February 2024.

Homework assignment:

The homework assignment is to be done in the same groups of 2. There are multiple deadlines for this assignment and the first one (paper selection) is due 29th of January 2024. More information here.

Βonus:

The homework assignment and the lab may give you up to 5 points each for the exam. Check the homework assignment and lab pages for more info. 

Literature:

We will use the Fifth Edition of the book titled "Distributed Systems: Concepts and Design" written by: George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Blair, and published by Addison-Wesley, ISBN-10: 0132143011, ISBN-13: 9780132143011. For special themes we will use additional literature items (scientific papers), which will be specified/distributed during the course and, whenever possible, will be made available via the webpage of the course.

Slides:

The slides of the lectures will be published gradually after each lecture in the Course Schedule and in the respective Documents folder.
For more slides from last year, see the Files.

Reading Material:

For the exam, you have to study:

• Chapters: 15, 17, 18 5th edition of the Coulouris et al. book. If you have not studied "Transactions and Concurrency Control" before study chapter 16th also.
• Chapter 1, 3 and 5 of the Master's Thesis.

• Marc Shapiro, Nuno Preguica, Carlos Baquero, Marek Zawirski. Conflict-free Replicated Data Types. [Research Report] RR-7687, 2011, (https://hal.inria.fr/inria-00609399v1/document).

• Xavier Défago, André Schiper, Péter Urbán: Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36(4): 372-421 (2004) 
  
• Gafni and Bertsekas: Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology, IEEE Trans. Comm. 1981.
• Roger Wattenhofer in collaboration with Christian Decker: Eventual Consistency and Bitcoin.pdf

• A set of fast links to papers referenced by the thesis for fast access: 
• Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115-138. (The historical paper that introduces many concepts on process synchronization that we use every day. You might want to read in the original as first introduced in 1971). 
• Chandy, K.M.; Misra, J. (1984). The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems. (The drinking philosophers problem and a solution for it based on dynamic distributed DAG manipulation.)
• Nancy A. Lynch Upper bounds for static resource allocation in a distributed system Journal for Computer and System Sciences, 23:254-278, 1981. (Bounds and techniques for bounds for resource allocation).
• Manhoi Choy and Ambuj K. Singh. Efficient fault-tolerant algorithms for distributed resource allocation. ACM Transactions on Programming Languages and Systems, 17(3):535-559, May 1995. (The papers that introduce the use of Doorways for resource allocation.)
• Ernest Chang; Rosemary Roberts (1979), An improved algorithm for decentralized extrema-finding in circular configurations of processes, Communications of the ACM (ACM) 22 (5): 281–283 (for leader election on rings, a classical paper for rings).

Reading material for the homework assignment can be found here. Also, you can find some old exams, that include March 2022 exams and answers, here.

Course Description

Distributed systems is a popular and powerful computing paradigm. Their importance increases as networked computers become more common than free-standing ones, especially since many different types of computers can be found in networks.

In this course we will see the points of inherent difference and strength of distributed systems compared with sequential or strongly-coupled systems; consequently, we will also study the issues and problems that have to be addressed and solved efficiently for these differences to be taken advantage of, so that the system retains its strength and high potential. This course discusses the fundamentals of distributed systems.

The objective of the course is for students to understand the theoretical principles and practical considerations of distributed systems. By the end of the course, students should be able to reason about various concepts such as consistency, durability, availability, fault tolerance, and replication. By the end of the course, students should be able to understand and reason about the limits that asynchrony, failures and concurrency bring into the distributed system designs. 

In particular, we will address and study the following issues in distributed systems:

1. Reliable and atomic broadcast
2. Replication and Consistency: The advantages and costs of replicating data: the potential improvement in response times and reliability, and the extra communication costs involved in keeping data consistent.
3. Fault-tolerant Agreement in Distributed Systems (a very special and significant problem, since it is a key issue in most synchronization and coordination problems in distributed systems) Study of the basic impossibility results and discuss their implications; proceed with solutions and protocols for systems with certain strengths and design structures.
4. Resource allocation
5. Analysis and Design of Distributed Algorithms
6. Blockchain

When it comes to the topics, there is an overlap on the topics discussed in this course and in the introductory course on Distributed Systems. The difference is on the objectives and the depth of the reasoning tools discussed.

Course Evaluation

A team of students representing the GU-CS students, the CTH International Master's program students, and the "local" CTH students is formed. The team's task is to:
- Provide feedback from students
- take part in mid- and final-evaluation meetings
- write meeting minutes; and
- together with the teacher compile the final evaluation report.

The team is initially comprised of the following students (If you want to join lets us know. The list will be finalized during the first week of the course):

• tiagonarcisoudr@gmail.com       Tiago Narciso Costa
• ppawel@student.chalmers.se    Pawel Przestrzelski
• pavloss@student.chalmers.se    Pavlos Stampoulis
• dikaixu1999@gmail.com            Dikai Xu
•  johx@student.chalmers.se        Johan Larsson