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.
The lectures start from 09 October.
The lectures will be streamed using Zoom. Please, register a zoom account in advance to follow the lectures. University email addresses are associated with zoom accounts. Using your uniroma1.it email address you should be able to log at http://uniroma1.zoom.us.
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.
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
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.
The recoded lectures will be also distributed to enrolled students.
Lecture syllabus.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
(Model 1, Model 2, Links and Abstractions are in the same deck of 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, Safety and Liveness, Asynchronous System and scheduler, Crash-Stop failure, Byzantine failure. Fair-Lossy Link.
NB: in the slide of the video there is a typo in the delivery of the fair-lossy <deliver|p,m> means delivery message m sent by process p. this typo is not in the slide.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture Syllabus.
Time 1 : Asynchronous, Synchronous, Partially (or Eventually) synchronous. (slides, video);
Time 1.2: Importance of time, Physical clock s limitation, UTC, Internal and external synchronization (slides, video);
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, video);
Material to read: Main Book (2.4.3-2.4.4), 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)
Optional reads: A detailed description of Berkley is here;
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,
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Time 2: Happened-before, Logical (also Scalar) and Vector Clocks. An application of scalar clocks Lamport's Mutual exclusion (slide, video).
Exercises on FIFO channel (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 and Lamport ME.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Time 3 - Encapsulating timing assumption with Failures Detectors: The Perfect Failure Detector P (slides, video).
Material to read: Failure Detectors are in Main Book (Chapter 2.6).
Optional Reads: 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: Failure Detectors, P (the algorithm exclude on timeout and the round-based one), Round-based computation and its equivalency with synchrony.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Tenative Lecture syllabus.
Time 3 - Encapsulating timing assumption with Failures Detectors: The eventually perfect Failure Detector Diamond P (slides, video).
Time 3 - The leader election (LE) primitives: Perfect LE and Eventual LE (Omega). (slides, video).
Time 3 - The models of Fail-stop, Fail-noisy and Fail-silent and their relationship with Synchronous, Eventually Synchronous and Asynchronous. (slides, video).
Material to read: Failure Detectors 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.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Broadcast 1: Best Effort Broadcast and Regular Reliable Broadcast (slides, video).
Broadcast 2: Uniform Reliable Broadcast (only All-ack) (slides, video).
Exercises
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: All-ack Uniform Broadcast. Complexity measures: messages complexity and communication steps (also called message delays).
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Broadcast: Uniform Reliable Broadcast (Majority-ack), efficient broadcast gossiping and spanning trees. Impossibility of uniform broadcast with n/2 or more failures (slides, video)
Ordered Broadcasts: FIFO and Causal Broadcast (slides, video)
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 Quroums, The impossibility proof of URB, FIFO Broadcast, Causal Broadcast, Orthogonality of the ordering concept and reliability properties.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Broadcast: Causal Broadcast (waiting) algorithm, introduction to total order (slides, video)
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, video)
Material to read: Casual Waiting is in Main Book (Chapter 3.9), 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.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
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, Atomic Register Implementation (1,1)-Atomic using (1,N) Regular.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Atomic Registers algorithms for (1,N)-Atomic Register using (1,N Regular) (slides, video)
Atomic Registers algorithms for (1,N)-Atomic Register using message passing with and without P (slides, video)
(N,N)-Atomic Register using (1,N)-Atomic Register (slides, video)
Exercises (slides)
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)
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Synchronous Consensus 1: Hierarchical Consensus (slide, video)
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.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
The lower bound of f+1 rounds and FLP: impossibility of solving consensus in asynchronous systems (slide,video)
Consensus 3: Paxos consensus algorithm in eventually-synchronous systems: Explanation of paxos following paxos made simple. (slide,video)
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".
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Consensus 3-bis: Paxos consensus algorithm in eventually-synchronous systems: Explanation of paxos using the pseducode (from the paper A Simpler Proof for Paxos and Fast Paxos) , examples on paxos, difficulties of implementing paxos on real systems. (slide,video)
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".
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
As usual recording will be provided.
Lecture syllabus.
NB:TYPO IN ALGORITHM: line 19 of algorithm 17 should be sent[originator]=m' not sent[p_i]=m'; you have to store a bus for each possible source.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
Material to read: Total Order Brodacast is in main book (Chapter 6.1). Replication is not in the main book (the content of the slides is enough). Primary-backup vs Active-replication, Replicated State Machine.
Key concepts: Total order broadcast
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
0. student opinions (slides)
Software Replication - Active and passive (also called primary backup) (slides, video).
Passive Replication in Eventually SYNC: Raft (slides, video)
Material to read: Replication is not in the main book (the content of the slides is enough). For Raft there is the original paper (here).
Key concepts: Primary-backup vs Active-replication, Replicated State Machine.
EXAM KEY: WMHL2H
TEXT: https://drive.google.com/file/d/1AbSchKYHUf1Ja249tvtkdsY-z6mPomq6/view
There will be a simulated exam (note this is not a midterm no vote or bonus will be given). The procedure will mimicry one to one the ones of the real exam.
For the students that will attend in person, try to bring a laptop to use exam.net.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
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/
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.
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, video)
Byzantine broadcast part 1: Motivations behind the ByzCast and Consistent Broadcast (slides, video)
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).
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
1 only exercises (slides, video)
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Tentative Lecture syllabus.
Byzantine broadcast part 2: Reliable Byzantine Bcast (slides,video)
Byzantine Consensus in synchronous system: definition, and toy algorithm (slides,video)
Byzantine Consensus in synchronous system: Necessity of 3f+1 (Not required for the exam). (slides,video)
Key concepts: Byzantine Reliable Bcast, Byzantine Agreement definition, Toy Algorithm, impossibility of solving consensus with n<=3f (only statement)
Material to read: 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)
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Tentative Lecture syllabus.
Byzantine Consensus in synchronous system: King algorithm (slides, video)
Ordering in byzantine eventually synchronous systems: An overview of PBFT (slides) (not all required for the exam - you are expected to know only until slide 10)
Key concepts: King algorithm, Overview of PBFT, PBFT, Permissioned blockchain definition, Hyperledger Fabric architectural overview
Reading Material: The king algorithm is on Roger notes (https://disco.ethz.ch/courses/distsys/lnotes/chapter17.pdf ).
PBFT is not in the main book. We will see the simplified version explained in Roger Wattenhofer notes (https://disco.ethz.ch/courses/distsys/lnotes/chapter25.pdf - Section 25.2) . The original paper of PBFT contains the real version of the algorithm (link). The differences are contained and the simplified version is not using optimization mechanisms that are present in real implementations. PBFT is at the base of all the variants and extended algorithms that have been used to design fast permissioned blockchain environments that are Byzantine tolerant. PBFT has been invented by Miguel Castro and Barbara Liskov. I found a youtube video in which Castro explains PBFT (https://www.youtube.com/watch?v=Q0xYCN-rvUs).
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Tentative Lecture syllabus.
Permissioned Blockchains: Definition, Hyperledger fabric architecture and example of a smart contract, other blockchains: Corda and Sawtooth (slides, video)
Permssionless Blockchains: Definition, A deep study of the bitcoin network, Pitfails and attacks against permissionless blockchain based on Proof of Work (slides, video)
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. The part on permissionless blockchain is a summary of several sources. See the links in the slides.
LINK FOR THE REMOTE STREAMING: https://uniroma1.zoom.us/j/7981663898
Lecture syllabus.