Course syllabus

Course Assistants:

• Dimitrios Palyvos-Giannas [Homework Assignment and Lab], palyvos [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 30th. If you do not choose a time slot by then, your group will be assigned to an empty time slot. It is also be 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 from 21st of February 2022
• Wednesdays 13:15-15:00, EL42 from 16th of February 2022
• Thursday 08:00-09:45, EL43 from 17th of February 202

Before February 16th we used  https://chalmers.zoom.us/j/62998948617. For usability reasons we used the same zoom-link. The link is associated with the first timeslot of the course, that is not problem do not mind that.

The course starts on Monday, January 17th. Due to the increasing spread of covid-19 that is taking place now, we start with remote education. We are looking into introducing a hybrid Q&A hour with a controlled subset of students in the classroom. Probably we will have this session at the second half of the Monday's slot, more information on that to come.

Please check frequently the Course Schedule for updates. 

Lab:

The lab  are to be done in groups of 2. The lab is due on the 20th of February 2022.

Homework assignment:

The homework assignment is to be done in groups of 2. There are multiple deadlines for this assignment and the first one (paper selection) is due 30th of  January 2021. 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 and the recordings 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. Ρeliable 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):

MPCSN  ruikundeng@163.com                  Ruikun Deng

MPCSN  priyankakv.9395@gmail.com       Vishnu Priyanka Kunapareddy

MPCSN  mattias.retteli@gmail.com            Mattias Retteli

MPCSN  shucho@student.chalmers.se      Shubhankar Choudhari

MPCSN  zhouzh49@mail2.sysu.edu.cn     Zihao Zhou

 

Corona information: 

We will follow Corona guidelines from the main Chalmers administration.