Course Log

Symbol *  indicates hard homeworks (i.e., you can still expect something similar in an exam). Symbols ** and *** indicate really hard, extremely hard homeworks (I will not put something similar in an exam),  you should try to solve them just for fun. 

 Lectures:

please read carefully all the rules an regulations in place for the COVID-19: https://www.uniroma1.it/en/notizia/covid-19-phase-2-procedures-students-staff-and-guests

For the rules of the faculty attendance has to be recorded to track contacts in case of COVID 19 cases. 

The form to fill is here. It has to be filled for each class attended: https://docs.google.com/forms/d/e/1FAIpQLSetbP7-Nxt79wgAp9qOXiT5H2JMD1gI39aChlRYkeIUqhz-eA/viewform

Streaming and Recording:

This year 2022/2023 the streaming and recording of lectures is not granted. The regulations of Sapienza explicitly say that lectures are physical and must be done in presence. To help students that work I made available at this link the recording of the lectures of the year 2021/2022.  I strongly recommend to follow the lectures of this year in presence as you can miss new content, new exercises and the interaction with me and the other students.  I also will provide a best effort unreliable streaming service, that is if the internet connection in the room works and there are no problems the lecture will be probably streamed on zoom. This is something you cannot rely on, as I could stop to do it for any unexplained reason and at any moment. 

The lectures are held: 

Building: RM062, Aula Alfa Monday 14:00-17:00

Building: RM112, AULA 5 Thursday 10:00-12:00

Lecture 1: September, 29, 2022  10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

The room should be on the first floor and should be also named 1.01
Lecture syllabus.

1. Introduction (slides)

2. Model 1: Systems and Processes (slides)

Best Effort Zoom Link: https://uniroma1.zoom.us/j/7981663898

Material to read: Main Book (1, 2.1 and 2.2. 2.4.1-2.4.2), H. Attiya, J.L. Welch. 2004 (2.1).

Key concepts: System Model, Processes, Uniqueness of the identifies, Local View, Delivery event vs Message creation, Asynchronous System, indistinguishability of the views. 

Lecture 2: October, 3, 2022  14:00-17:00  Aula Alfa - Via Salaria 113.

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

Lecture syllabus.

1. Model 1: Systems and Processes (slides)

2. Model 2:  Failures  (slides)

3. Links and Abstractions: Safety and Liveness. Fair-Lossy(slides)

4. Links: Stubborn, and Perfect  (slides)

Best Effort Zoom Link: https://uniroma1.zoom.us/j/7981663898

Material to read: Main Book (1, 2.1 and 2.2. 2.4.1-2.4.2), H. Attiya, J.L. Welch. 2004 (2.1).

Key concepts:  Fairness of a scheduler, Crash-stop failures and byzantine failures. Abstraction and properties;  Safety and Liveness. The Fair-Lossy Link, The Stubborn and The Perfect link. 

Lecture 3: October, 6, 2022  10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

The room should be on the first floor and should be also named 1.01
Tentative Lecture syllabus.

1. Time 1 :  Asynchronous, Synchronous, Partially (or Eventually) synchronous.  (slides);

2. Time 1.2:  Importance of time, Physical clocks limitation, UTC,  Internal and external synchronization  (slides);

3. Time 1.3:   Synchronization in complete graphs: Christian  (slides);

4. Exercises on Links (slides).

Best Effort Zoom Link: https://uniroma1.zoom.us/j/7981663898

Material to read: H. Attiya, J.L. Welch. 2004 (2.1).  Time 1 is in the Main book (2.5);  Topics of Time 1.2-1.3 can be found on Maarten van Steen et al. 2008 (Chapter 6.1 -  the book is free)

Key concepts:  Synchronous and Eventually-synchronous systems, physical clock drift, Internal and External synchronization, Christian and Berkley, NTP (for us it is just a hierarchy of servers that use christian-like approach), Local Skew vs Global Skew.

Optional reads: A detailed description of Berkley is here;

Lecture 4: October, 10, 2022  14:00-17:00  Aula Alfa - Via Salaria 113.

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

The room should be on the first floor and should be also named 1.01
Lecture syllabus.

1. Time 1.3:   Synchronization in complete graphs: Christian, Berkley, NTP, Tree based vs fully distributed, local vs global skew  (slides);

2. Exercises on Links (slides).

3.  FIFO link (slides)

4. Time 2: Happened-before, Logical (also Scalar) Clocks. (slides)

Material to read: An alternative explanation of logical and vector clocks is here. Logical and vector clocks can be found on Maarten van Steen et al. 2008 (Chapter 6.2. -the book is free) Chapter 6.2 contains also a description of Lamport's ME.  The main book describes also logical clock and happened-before in Chapter 2.5.1 and Chapter 3 Causal Broadcast.
Optional Material: Leslie Lamport on logical clock: https://www.youtube.com/watch?v=gY9VwiPTa60 Relativity and causality violation: https://plus.maths.org/content/violating-causality. Original paper in which Lamport proposed the logical clock: here.
Key concepts: Happened-before relationship, Logical Clock, Vector Clocks, FIFO Channels.

Lecture 5: October, 13, 2022   10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

The room should be on the first floor and should be also named 1.01
Tentative Lecture syllabus.

1. Time 2: Vector Clocks. (slides)

2. An application of logical clocks: Lamport's Mutex. (slides)

3. Exercises on Links (slides).

Material to read: An alternative explanation of logical and vector clocks is here. Logical and vector clocks can be found on Maarten van Steen et al. 2008 (Chapter 6.2. -the book is free) Chapter 6.2 contains also a description of Lamport's ME.  The main book describes also logical clock and happened-before in Chapter 2.5.1 and Chapter 3 Causal Broadcast.
Optional Material: Leslie Lamport on logical clock: https://www.youtube.com/watch?v=gY9VwiPTa60 Relativity and causality violation: https://plus.maths.org/content/violating-causality. Original paper in which Lamport proposed the logical clock: here.
Key concepts: Happened-before relationship, Logical Clock, Vector Clocks, FIFO Channels.

Lecture 6: October, 17, 2022  14:00-17:00  Aula Alfa - Via Salaria 113.

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

Lecture syllabus.

1.  An application of logical clocks: Lamport's Mutex. (slides)

2. Time 3 - Encapsulating timing assumption with Failures Detectors: The Perfect Failure Detector P  (slides).

Material to read:  Chapter 6.2 of  Maarten van Steen et al. 2008 (Chapter 6.2. -the book is free) contains a description of Lamport's ME.    Failure Detectors are in Main Book (Chapter 2.6).

Optional Material: The Splendors and Miseries of Rounds, Adam Shimi, https://dl.acm.org/citation.cfm?id=3364635 (access from Sapienza or using the proxy). Original paper of Chandra and Toueg on Failure Detector (here). The round model for synchrony is folklore and can be found in multiple books (e.g., Distributed Computing - H. Attiya, J.L. Welch. 2004 , pp. 12-13)

Key concepts:  Lamport's ME,  Failure Detectors, P (the algorithm exclude on timeout and the round-based one), Round-based computation and its equivalency with synchrony.

Lecture 7: October, 20, 2022   10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Lecture syllabus.

1. Time 3 - Encapsulating timing assumption with Failures Detectors: The eventually perfect Failure Detector Diamond P  (slides).

2. Time 3 - The leader election (LE) primitives: Perfect LE  and Eventual  LE (Omega).   (slides).

3. Time 3 - The models of Fail-stop, Fail-noisy and Fail-silent and their relationship with Synchronous, Eventually Synchronous and Asynchronous.  (slides).

Material to read:   Failure Detectors and Leader Electors are in Main Book (Chapter 2.6).

Key concepts:   Eventually perfect Failure Detector, LE, and Eventual LE.   Fail-stop, Fail-noisy and Fail-silent. Applications of FD and LE.

Lecture 8: October, 24, 2022  14:00-17:00  Aula Alfa - Via Salaria 113.

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

Lecture syllabus.

1. Time 3 - Applications of the FD and LE: making lamport's ME Fault-tolerant and a really simple ME algorithm using LE.   (slides).

2. Broadcast 1-  Best Effort Broadcast and Regular Reliable Broadcast (slides)

Material to read: Broadcast is in Main Book (Chapter 3.1-3.4). Complexity measures: messages and communication steps; are in Main Book (Chapter 2.7.4).

Key concepts: BEB Broadcast, Regular Reliable Broadcast: Lazy and Eager, Uniform Realiable Broadcast: specification. Complexity measures: messages complexity and communication steps (also called message delays).

Lecture 9: October, 27, 2022  10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  

Lecture syllabus.

1. Broadcast: Uniform Reliable Broadcast (all-ack and Majority-ack), efficient broadcast gossiping and spanning trees. Impossibility of uniform broadcast with n/2 or more failures (slides)

2. Broadcast 2: Exercises on Broadcast (slides).

Material to read:   Broadcast is in Main Book (Chapter 3.1-3.4), Quorums in Main Book (Chapter 2.7.3). Ordered Broadcast FIFO and Casual are in Main Book (Chapter 3.9).

Key concepts: The use of Quorums,

The lectures of 31 of October and 3 of November are cancelled.  

Lecture 10:  November, 7, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113.

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  
The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

1. Ordered Broadcasts: FIFO and Causal Broadcast (slides)

2. Broadcast: Causal Broadcast (no-waiting) algorithm (slides)

Material to read:   Broadcast is in Main Book (Chapter 3.1-3.4), Quorums in Main Book (Chapter 2.7.3). Ordered Broadcast FIFO and Casual are in Main Book (Chapter 3.9). 

Key concepts:  FIFO Broadcast, Causal Broadcast, Orthogonality of the ordering concept and reliability properties.

Lecture 11:  November, 10, 2022. 10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  
The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

1. Broadcast: Causal Broadcast (waiting) algorithm (slides)

2. Introduction to total order (slides)

3. Shared Memory: What is Shared Register? Register Semantic

Material to read: Registers are in Main Book (Chapter 4.1,4.2).

Optional Reads: The book of H. Attiya, J.L. Welch. 2004 has a section on shared memories (Chapters 9.1-3, 10.1-3).  The book of Van Steen et al. (Chapter 7) describes a panoply of additional consistency properties.

Key concepts: Waiting Causal Brodacast, Shared Memories, Register definitions, Consistency properties (Regular), Regular register (1,N), Fail-stop and Fail-Silent implementations.

Lecture 12:  November, 14, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113.

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  
The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

1. Regular Consistency: (1,N) with fail-stop (read one write all) and fail silent (majority voting) (slide)

2. Register Semantic: Sequential and Atomic (slides)

3. Atomic Registers algorithm using regular registers: (1,1)-Atomic Register (slides)

Material to read: Casual Waiting is in Main Book (Chapter 3.9), Registers are in Main Book (Chapter 4.1,4.2). The book of Van Steen et al. (Chapter 7) describes a panoply of additional consistency properties (including sequential consistency)

Optional Reads: The book of H. Attiya, J.L. Welch. 2004 has a section on shared memories (Chapters 9.1-3, 10.1-3).  The book of Van Steen et al. (Chapter 7) describes a panoply of additional consistency properties (including sequential consistency). Original paper of Lamport on sequential consistency (paper)

Key concepts: Consistency properties: Sequential Consistency and Atomic Consistency, Compositionality of consistency properties.

Lecture 13:  November, 17, 2022. 10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

Record your presence here. It is needed for tracking contacts in case of COVID-19 outbreak.  
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

1. Atomic Registers algorithm using regular registers: (1,1)-Atomic Register (slides)

2. Atomic Registers algorithms for (1,N)-Atomic Register using (1,N Regular) (slides)

3. Atomic Registers algorithms for (1,N)-Atomic Register using message passing with and without P (slides)

4. (N,N)-Atomic Register are skipped. They will not be in the exam. The interest students can read them on the slides and the main book.

Material to read: Atomic Registers are in Main Book (Chapter 4.3,4.4).

Optional Reads:  Interesting paper on consistency properties (paper). Website with a map of consistency properties (map)

Lecture 14:  November, 21, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113.

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

1. Synchronous Consensus 1:  Hierarchical Consensus (slide, video)

2. Synchronous Consensus 2:  Uniform Hierarchical Consensus (slide, video)

3. Exercises (slides,solution)

Material to read: Consensus in Main Book (Chapter 5.1-5.2).

Optional Reads: The book of H. Attiya, J.L. Welch. 2004 shows a lower bound on the step complexity of regular consensus in synchronous systems (Chapters 5.1.4).

Key concepts: Regular vs Uniform Consensus definitions.  Hierarchical Consensus algorithms, uniform and regular variants.

CONFIRMED: The 07 December starting from 14:00 Aula Alfa there is  an additional lecture with an exam simulation and the correction. The lecture will be recoded and streamed and it will be published on this website.

 Lecture 15:  November, 24, 2022. 10:00-12:00  Aula 5 - Building RM112 - Via Regina Elena 295 D. 

 CANCELLED - THE LECTURE WILL NOT BE HELD. - CANCELLATA. 

Lecture 15:  November, 28, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113.

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

1. FLP: impossibility of solving consensus in asynchronous systems  (slide)

2. Consensus 3:  Paxos consensus algorithm in eventually-synchronous systems:  Explanation of paxos following paxos made simple.  (slide)

Material to read: Paxos is not in the main book. The lecture will follow the structure of the paper ``Paxos made simple" of Leslie Lamport (link) another good paper is this one (link).  The difficulties of implementing paxos are described in this paper (link).

Optional reads: here there is a video of Leslie Lamport explaining Paxos (https://www.youtube.com/watch?v=tw3gsBms-f8). The video is quite difficult, probably is better to read this paper (link).

Key concepts: Paxos. Nb: People say that paxos is notoriously difficult to be understood. For the above,  I strongly suggest to read Lamport's paper ``Paxos made simple".

Lecture 16:  December, 1, 2022. 10:00-12:00  Aula 5 - Building RM112 

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

1. Total Order Broadcast. (slides)

2. Exercises (slides)

Material to read:  Total Order Brodacast is in main book (Chapter 6.1)

Key concepts: Total order broadcast

Lecture 17: December, 5, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113.

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

1. Software Replication - Motivations (slides)

2. Software Replication - Consistency criteria: linearizability (slides)

3. Software Replication - Passive (also called primary backup)  (slides)

Material to read:  Replication is not in the main book (the content of the slides is enough). 

Key concepts: Primary-backup vs Active-replication, Replicated State Machine.

Additional reads: Rachid Guerraoui and André Schiper: “Fault-Tolerance by Replication in Distributed Systems”. In Proceedings of the 1996 Ada-Europe International Conference on Reliable Software Technologies (Ada-Europe '96).

Lecture 18: December, 7, 2022. 14:00-17:30  Aula Alfa - Via Salaria 113. (Wednesday).

Additional Exercise section - Simulated Exam - If possible bring a laptop, a tablet or a smartphone to access the text of the simulated exam during the class. 

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

LINK FOR THE TEXT  

Lecture 19: December, 12, 2022. 14:00-17:00  - Aula Magna Via Regina Elena 295. 

Lecture syllabus.

1. Software Replication - Active  (slides)

2. Software Replication in Eventually- Synchronous systems: Raft (slides).

3. An analysis of Raft in the real world.

Key concepts: Activate Replication, RAFT

Material to read:  For Raft there is the original paper (here). 

Optional reads: A recent example (11/2021) of a liveness stall in which a lot of money has been lost due to Raft going south:  https://blog.cloudflare.com/a-byzantine-failure-in-the-real-world/

Optional material: Lecture on raft by the authors (youtube)

Lecture 20: December, 15, 2022  10:00-12:00  Aula 5 - Building RM112 

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Students Opinions:  please if you have not done it consider to fill the students opinions for the course: instructions and code 

Lecture syllabus.

1. Introduction to byzantine failures. (slides)

2. Preliminary definitions and observations: model of byzantine faliure, needs of authenticated messages, crypto primitive (auth and sign), authenticated link. Unmeanigful properties in a byzantine system model.   (slides)

3. Byzantine broadcast part 1:  Motivations behind the ByzCast and Consistent Broadcast (slides)

Material to read and key concepts: Main book 3.10 (Cons. Bcast), 3.11 (Reliable Bcast), 2.2.6 (Byzantine failures) , 2.3 (Crypto Abstractions), 2.4.6 (Authenticated Channel).

Lecture 21: December, 19, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113.

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

1. Byzantine broadcast: Consistent Broadcast (slides)

2. Byzantine broadcast: Reliable Byz Broadcast (slides)

3. Byzantine Consensus in synchronous system: Necessity of 3f+1.  (slides)

4. Exercises (slides)

Material to read and key concepts: Main book 3.10 (Cons. Bcast), 3.11 (Reliable Bcast), 2.2.6 (Byzantine failures) , 2.3 (Crypto Abstractions), 2.4.6 (Authenticated Channel).

Synchronous byzantine agreement is not in the main book. Refer to the notes of Roger Wattenhofer https://disco.ethz.ch/courses/distsys/lnotes/chapter17.pdf  Pages 159-164.  The 17.12 in the slides is explained in a more detailed way with figures, but it remains the same argument of Th. 17.12 stated more precisely.

Optional reads: Nancy Lynch book contains a detailed section on Byzantine Agreement, and it explains also the Exponential Information Gathering Algorithm (EIG). Such an algorithm is an extension of the toy algorithm in the general setting. It has been the first byzantine agreement algorithm discovered.  (N. Lynch. 1998. - Chapter 6.3).

Material to read and key concepts: Synchronous byzantine agreement is not in the main book. Refer to the notes of Roger Wattenhofer https://disco.ethz.ch/courses/distsys/lnotes/chapter17.pdf  Pages 159-164.  The 17.12 in the slides is explained in a more detailed way with figures, but it remains the same argument of Th. 17.12 stated more precisely.

Lecture 22: December, 21, 2022. 14:00-17:00  Aula Alfa - Via Salaria 113 - Exercise only Additional session. 

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

Exercises (slides.)

Lecture 23: December, 22, 2022  10:00-12:00  Aula 5 - Building RM112 

LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898

1. Byzantine Consensus in synchronous system: Necessity of 3f+1.  (slides)

2. King's Algorithm: Consensus algorithm for a synch system.  (slides)

Material to read and key concepts: Synchronous byzantine agreement is not in the main book. Refer to the notes of Roger Wattenhofer https://disco.ethz.ch/courses/distsys/lnotes/chapter17.pdf  Pages 159-164.  The 17.12 in the slides is explained in a more detailed way with figures, but it remains the same argument of Th. 17.12 stated more precisely.