Lectures

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:

The lectures start from 20 September.

For the students physically attending the classes please read carefully all the rules an regulations in place for the COVID-19: https://www.uniroma1.it/it/node/202429

The lectures of the first weeks will be streamed on zoom : https://uniroma1.zoom.us/j/7981663898

For all the enrolled students it is mandatory to use the uniroma1.it account. For the pre-enrolled student, please register a Zoom account using another email, it will be allowed for the first lectures.

Please, join on time the zoom meeting. Otherwise, you risk to stay in the waiting room (if you do not have a sapienza address) until the break.

Lecture 1: September, 20, 2021 12:00-15:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

  1. Introduction (slides,)

  2. Model 1: Systems and Processes (slides, )

  3. Model 2: Failures (slides )

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: Local View, Delivery event vs Message creation, Asynchronous System and scheduler, Crash-Stop failure, Byzantine failure.

Recording (available only with university credentials): https://drive.google.com/file/d/19yMfDvGfO-fSJEBLgaIhcPrGBWqzDOxZ/view?usp=sharing

Lecture 2: September, 22, 2021 14:00-16:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

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

  2. Links: Stubborn, and Perfect (slides)

Material to read: Main Book (2.4.3-2.4.4), H. Attiya, J.L. Welch. 2004 (2.1).

Key concepts: Fair-Lossy Link, stubborn and perfect link. Synchronous and Eventually-synchronous systems, Safety and Liveness,

Recording: https://drive.google.com/file/d/1dNLBajpyMlVlm_se5n-6dbUx3REzRhQW/view?usp=sharing

Lecture 3: September, 27, 2021 12:00-15:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

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 and Berkley, NTP, Sychronization in complete graphs: Local Skew vs Global Skew, The limits of timestamps (slides);

  4. Exercises on Links (slides)

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: Fair-Lossy Link, stubborn and perfect link. Synchronous and Eventually-synchronous systems, Safety and Liveness, 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;

Recording: https://drive.google.com/file/d/1OkpakI0AQPW7QGcuYP5qLOofMM1PaDcB/view?usp=sharing

Lecture 4: September, 29, 2021 14:00-16:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

  1. FIFO link (slides)

  2. Time 2: Happened-before, Logical (also Scalar) and Vector Clocks. (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.

Recording: https://drive.google.com/file/d/1l53o9pYjvcHUNRHf8E7WHBTCbaEPUsoS/view?usp=sharing

Lecture 5: October, 4, 2021 12:00-15:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

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)

Simulator: JBOT sim (answer to a student question) https://jbotsim.io/

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 6: October, 6, 2021 14:00-16:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

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 7: October, 11, 2021 12:00-15:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

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)

  3. Broadcast 2: Uniform Reliable Broadcast (only specification) (slides)

  4. Exercises: 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 8: October, 13, 2021 14:00-16:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

Lecture syllabus.

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

  2. Broadcast 2: Uniform Reliable 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,

Lecture 9: October, 18, 2021 12:00-15:00 Aula Alfa - Via Salaria 113/117

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 (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: The impossibility proof of URB, FIFO Broadcast, Causal Broadcast, Orthogonality of the ordering concept and reliability properties.

Lecture 10: October, 20, 2021 14:00-16:00 Aula Alfa - Via Salaria 113/117

The zoom link for the lecture is: https://uniroma1.zoom.us/j/7981663898

  1. introduction to total order (slides)

  2. Shared Memory: What is Shared Register? Register Semantic, Regular Consistency: (1,N) with fail-stop (read one write all) and fail silent (majority voting) (slide)

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.

October, 25, 2021 12:00-15:00 Aula Alfa - Via Salaria 113/117 - CANCELLED. The lecture is cancelled, there will be directly the one of 27 october.

Lecture 11: October, 27, 2021 14:00-16:00 Remote Only - The lecture will be also recorded.

RECORDING

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

Lecture syllabus.

  1. Regular Consistency: (1,N) and fail silent (majority voting) (slide)

  1. Register Semantic: Sequential and Atomic (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 12: November, 3, 2021 14:00-16:00 Via Salaria 113 Aula Alfa


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 13: November, 8, 2021 12:00-15:00 Via Salaria 113 Aula Alfa

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)

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.


Lecture 14: November, 10, 2021 14:00-16:00 Via Salaria 113 Aula Alfa

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


Only exercises and f+1 lower bound on consensus.

  1. Exercises (slides,solution)


Lecture 15: November, 15, 2021 12:00-15:00 Via Salaria 113 Aula Alfa

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

  1. The lower bound of f+1 rounds and 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: November, 17, 2021 14:00-16:00 Via Salaria 113 Aula Alfa

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

Lecture syllabus.

  1. Exercises on paxos (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 17: November, 22, 2021 12:00-15:00 Via Salaria 113 Aula Alfa

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 18: November, 24, 2021 14:00-16:00 Via Salaria 113 Aula Alfa

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 19: November, 29, 2021 12:00-15:00 Via Salaria 113 Aula Alfa

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. 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, 1, 2021 14:00-16:00 Via Salaria 113 Aula Alfa

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

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, 6, 2021 12:00-15:00 and Exercises 15:00-18:00 Via Salaria 113 Aula Alfa

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: definition, and toy algorithm (slides)

  4. Byzantine Consensus in synchronous system: Necessity of 3f+1 (Not required for the exam). (slides)

Additional Exercise section 16:00-18:00:

  1. Simulated Exam.

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).

Wattenhofer notes on crash tolerant consensus (https://disco.ethz.ch/courses/distsys/lnotes/chapter16.pdf)


Lecture 22: December, 13, 2021 12:00-15:00 Via Salaria 113 Aula Alfa

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

Lecture syllabus.

  1. Byzantine Consensus in synchronous system: Necessity of 3f+1 (Not required for the exam). (slides)

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

  3. Exercises (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.

Lecture 23: December, 15, 2021 14:00-16:00 Via Salaria 113 Aula Alfa

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

Tentative Lecture syllabus.

  1. Permissioned Blockchains: Definition, Hyperledger fabric architecture and example of a smart contract, other blockchains: Corda and Sawtooth (slides)

  2. Permssionless Blockchains: Definition, A deep study of the bitcoin network, Pitfails and attacks against permissionless blockchain based on Proof of Work (slides)

Key concepts: Permissioned blockchain definition, Hyperledger Fabric architectural overview, Permissionless blockchains definition, Bitcoin Architecture e PoW. Attacks against blockchains.

Reading Material: For Hyperledger fabric refer to the original documentation: https://hyperledger-fabric.readthedocs.io/en/release-2.2/. The part on permissionless blockchain is a summary of several sources. See the links in the slides.

December, 20, 2021 14:00-16:00 Via Salaria 113 Aula Alfa Lecture Cancelled

Lecture 24: December, 22, 2021 14:00-16:00 Via Salaria 113 Aula Alfa

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

Tentative Lecture syllabus.

  1. Permssionless Blockchains: Definition, A deep study of the bitcoin network, Pitfails and attacks against permissionless blockchain based on Proof of Work (slides)

Key concepts: Permissioned blockchain definition, Hyperledger Fabric architectural overview, Permissionless blockchains definition, Bitcoin Architecture e PoW. Attacks against blockchains.

Reading Material: For Hyperledger fabric refer to the original documentation: https://hyperledger-fabric.readthedocs.io/en/release-2.2/. The part on permissionless blockchain is a summary of several sources. See the links in the slides.