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.

THE VIDEO LECTURES WILL BE DISCONTINUED - THE LAST VIDEOS WILL BE FOR LECTURE 2 (TIME and Clock Synchronization).

Exam Dates, written test: 01/08/2020 (14:00-16:00) Room B2 Via Ariosto 25, 00185 DIAG, 02/17/2020 (14:00-16:00) Room B2 (Via Ariosto 25, 00185). (See Exams page)

LECTURE OF December, 13 has been cancelled for the weather warning.

https://www.uniroma1.it/it/notizia/lezioni-sospese-il-13-dicembre

English version (autom. translation): https://translate.google.com/translate?hl=en&sl=auto&tl=en&u=https%3A%2F%2Fwww.uniroma1.it%2Fen%2Fnotizia%2Flezioni-sospese-il-13-dicembre

Lecture 1: Oct, 2, 2019 14:00-17:00 Aula XI - Tumminelli

  1. Introduction (slides, video)

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

  3. Model 2: Failures (slides, video)

  4. Links and Abstractions: Safety and Liveness. Fair-Lossy, Stubborn, Perfect P2P (slides, video).

(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.4), H. Attiya, J.L. Welch. 2004 (2.1).

Key concepts: Local View, Delivery event vs Message creation, Safety and Liveness, Links, Asynchronous System and scheduler, Crash-Stop failure, Byzantine failure.

Lecture 2: Oct, 7, 2019 12:00-14:00 - Usual Room

Lecture syllabus (slides have been updated to include homeworks).

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

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

  3. Time 1.3: Synchronization in complete graphs: Christian and Berkley, NTP (slides, video);

  4. Time 1.4: Synchronization in arbitrary graphs: Tree based vs Fully-Distributed Algorithms, Local Skew vs Global Skew, Max algorithm and its analysis, The limits of ordering with timestamps. (slides, video).

(All topics are in the same deck of slides)

Material to read: Time 1 is in the Main book (2.5); Topics of Time 1.2-1.3 and a short description of Truetime can be found on Maarten van Steen et al. 2008 (Chapter 6.1 - the book is free); The Max algorithm is described at this link pp. 1-4 (slightly different formalism and proof).

Optional reads: A detailed description of Berkley is here; The original paper of Truetime 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, Max algorithm (with the analysis), the limits of ordering with timestamps.

Lecture 3: Oct, 9, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

  1. Time 2.1: Happened-before, Logical (also Scalar) and Vector Clocks. An application of scalar clocks Lamport's ME. Optimizing Lamport's ME - Ricart-Agrawala (slides, video 1,2, and 3). [being these topics hard, I will upload the corresponding videos].

  2. Time 2.2: Failure Detection: Only the definition and the code of the Perfect Failure Detector (slides).

  3. Exercises on Time 1, Time 2 and 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 and Chaper 6.3 a description of Ricart-Agrawala. Failure Detectors are in Main Book (Chapter 2.6). 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, Lamport ME, Ricart-Agrawala. Perfect Failure Detector

Lecture 4: Oct, 14, 2019 12:00-14:00 - Usual Room

Lecture syllabus

  1. Time 3.2: Failure Detection (FD): Perfect analysis. Round-based computation, Eventual Failure Detector (slides).

  2. Time 3.2: Leader Election (LE): Perfect Leader Election, Eventual Leader Election , Fail-stop, Fail-noisy and Fail-silent (slides).

  3. Discussing uses of Leader election and FD: Fault-tolerant MUTEX.

Material to read: Failure Detectors and Leader Election are in Main Book (Chapter 2.6), Fail-stop, Fail-noisy and Fail-silent are in Main Book (Chapter 2.7.1.)

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: Eventual Failure Detector, Round-Based model, Perfect LE and Eventual LE, Fail-stop, Fail-noisy, Fail-Silent. The abstraction of FD and its difference from synchrony assumption.

Lecture 5: Oct, 16, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

  1. Broadcast 1: Reliable broadcast and Regular Reliable Broadcast (slide).

  2. Broadcast 2: Uniform Reliable Broadcast, Quorums, Gossiping (slide).

  3. Exercises

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

Key concepts: Reliable Broadcast, Regular Reliable Broadcast, URB, Quorums, Gossiping and its use, the partition argument of Exercise 3.7 . Complexity measures: messages and communication steps.

Lecture 6: Oct, 21, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

  1. Broadcast 3: FIFO broadcast and Causal Broadcast (slide).

  2. Exercises. (Additional exercises are in main book chapter 3, all exercises on Reliable, Uniform, Fifo and Causal broadcast).

Material to read: Broadcast is in Main Book (Chapter 3.9).

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

Lecture 7: Oct, 23, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

  1. Registers 1: Shared Memories, Definition of registers, Regular Registers (1,N) - Fail-stop and Fail-Silent implementations. (slides)

  2. Register 2: Sequential Consistency and Linearizability/(also known as Atomicity) (slides)

  3. Exercises.

Material to read: Registers are in Main Book (Chapter 4.1,4.2). Sequential consistency is not present in the main book, but it is in Martin Van Steen et Al. (Chapter 7.2 pages 364-368 -the book is free).

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: Shared Memories, Register definitions, Consistency properties (Regular, Sequential and Atomic), Regular register (1,N), Fail-stop and Fail-Silent implementations.

Lecture 8: Oct, 28, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

  1. Registers 3: Atomic Registers (1,1),(1,N), (N,N) (slides).

  2. Compositionality of consistency properties. (slides).

Material to read: Registers are in Main Book (Chapter 4.3-4.4). The compositionality of consistency properties is briefly discussed in Martin Van Steen et Al. (Chapter 7.2 pages 364-368 -the book is free).

Key concepts: Atomic registers, message passing and regular registers implementations. The compositionality and non-compositionality of consistencies.

Lecture 9: Oct, 30, 2019 14:00-17:00 - Usual Room

Exercises from simulated exams and similars (solutions have been uploaded).

Only exercises (slides)


Lecture 10: Nov, 4, 2019 12:00-14:00 - Usual Room

Tentative Lecture syllabus.

  1. Synchronous Consensus 1: Regular Consensus: Flooding-Consensus and Hierarchical Consensus (slides).

  2. Synchronous Consensus 2: Uniform Consensus: Uniform Flooding-Consensus and Uniform Hierarchical Consensus (slides).

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. The flooding consensus will not be object of the final exam.

Lecture 11: Nov, 6, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

  1. Consensus 3: Paxos consensus algorithm in eventually-synchronous systems. Algorithm and formal proofs. The difficulties of implementing paxos on real systems: the case of chubby. (slides)

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. This lead to the creation of an alternative algorithm dubbed Raft, that follows a rotating-coordinator approach. We will see Raft in the RSM module. For the above, I strongly suggest to read Lamport's paper ``Paxos made simple".

Lecture 12: Nov, 11, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

  1. Consensus 4: FLP impossibility result (slides) PART 1 - existence of a bi-valent initial conf.

Material to read: FLP is not in the main book. It can be found at this link.

Key concepts: Impossibility of solving consensus in asynchrononus (or fail-silent) when even one process may crash. FLP, similarly to Paxos, is one of the key results in distributed computing (and computer science in general). It is arguably one of the most elegant impossibility proof you will see.

Lecture 13: Nov, 13, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

  1. Consensus 4: FLP impossibility result (slides)

  2. Total Order Broadcast. (slides)

  3. Material to read: FLP is not in the main book. It can be found at this link. Total Order Brodacast is in main book (Chapter 6.1). FLP proof is not necessary for the exam, the statement, and its implications, are.

  4. Key concepts: Total order broadcast

Lecture 14: Nov, 18, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

  1. Replication: Primary-backup vs Active-replication, Replicated State Machine. (slides)

  2. An example of a real Replicated State Machine: Raft (we will use the slides of the authors created for their ``user study") slides. - Up to slide 25.

Material to read: Replication is not in the main book (the content of the slides is enough), if you are interested in additional material send me an email. For Raft there is the original paper (here).

Optional reads: Linearizability (here).

Key concepts: Primary-backup vs Active-replication, Replicated State Machine, Ideas behind Raft

Lecture 15: Nov, 20, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

1. RAFT last part (same slides of previous lecture: here)(modified slides)

2. Exercises (slides)

Key concepts: Raft . The way raft handles configuration changes is optional.

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


Lecture 16: Nov, 25, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

1. Byzantine failures. (slides)

2. Authenticated Channel and crypto assumptions. (slides)

3. Byzantine Broadcast, consistent and reliable. (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 17: Nov, 27, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

1. Registers with Byzantine failures. (slides)

2. Safe Register (1,N). (slides)

3. Regular Register (1,N) (slides)

Material to read and key concepts: Registers are in the Main book. Safe Register (1,N) (Chapter 4.6), Regular (1,N) with and without signatures (Chapter 4.7). The regular (1,N) without signatures is not required for the exam.


Lecture 18: Dec, 2, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

1. Synchronous Byzantine Agreement definition and toy solution for f=1. (slides)

2. Synchronous Byzantine Agreement necessity of 3f+1. (slides)

3. King algorithm. (slides)

Key concepts: Byzantine Agreement definition, and king algorithm.

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-163. The toy algorithm is not required for the exam is only for understanding. King algorithm and Th 17.12-17.13 are required. Th 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 consensus (https://disco.ethz.ch/courses/distsys/lnotes/chapter16.pdf)


Lecture 19: Dec, 4, 2019 14:00-17:00 - Usual Room

Tenative Lecture syllabus. (Slides will be updated tomorrow morning)

1. PBFT (slides)


Material to read: 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 algorithm that have been used to design fast permissioned blockchain environments that are Byzantine tolerant.

Optional materials: 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).

Lecture 20: Dec, 9, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

1. Blockchain: permissionless (Bitcoin mainly) (slides)


Lecture 21: Dec, 11, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

1. Simulated Exam (text)

2. Solutions (slide)


THE LECTURE 22 of Dec, 13 has been cancelled for the weather warning. See link below.

https://www.uniroma1.it/it/notizia/lezioni-sospese-il-13-dicembre

English version (autom. translation): https://translate.google.com/translate?hl=en&sl=auto&tl=en&u=https%3A%2F%2Fwww.uniroma1.it%2Fen%2Fnotizia%2Flezioni-sospese-il-13-dicembre

CANCELLED FOR WEATHER WARNING.


Lecture 23: Dec, 16, 2019 12:00-14:00 - Usual Room

Lecture syllabus.

1. Blockchain: permissioned (PBFT variant and Intel Sawtooth) (slide)

2. Exercises: Students are encouraged to solve this three exercises for which solutions will be shown. (slide) (Solutions)

Lecture 24: Dec, 18, 2019 14:00-17:00 - Usual Room

Lecture syllabus.

1.Exercises with prof. Silvia Bonomi.