Docente
|
Di Luna Giuseppe Antonio
(programma)
Introduzione
-Storia e Motivazioni.
Riferimenti: https://sites.google.com/view/distributed-sytems-2019/lectures
M1: Models, Abstractions, and Basic Concepts
-Processes, communication, traces and execution, I/O Automata;
-Failures: crash-stop, and byzantine;
-Event based programming: abstraction, specification and implementations;
-Links: fair-lossy, stubborn, point-to-point.
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M2: Time in Distributed Systems
-Synchronous, asynchronous, and eventually synchronous systems;
-Clock Synchronization: Christian, Berkley, NTP, MAX-ALGORITHM;
- Clock sync. Tree based vs Fully-Distributed Algorithms, Local Skew vs Global Skew, Max algorithm and its analysis, The limits of ordering with timestamps
-Logical clocks and Vector Clock, Happened-before relationship.
-Encapusaliting time in failure detectors: P, $\Diamond$-P;
-Leader election and Eventual Leader Election
-Distributed system models: fail-stop, fail-noisy, fail-silent."
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M3: Basic Broadcast Primitives
- Best effort broadcast;
- Reliable broadcast;
- Uniform reliable broadcast;
- Causal broadcast.
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M4: Shared Memories
- Consistency: regular, sequential consistency and linearizability;
- Regular (1,N) register: Message Passing and (1,1)-Regular implementation
- Atomic (1,1), (1,N) and (N,N) registers;
- Non composability of sequential consistency;
-Relationship between consistency properties;"
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M5: Consensus
-Consensus specification;
-Hiearchical consensus: uniform and non-uniform;
-FLP: proof not required only the statement
-Paxos.
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M6: Total Ordering and Replicated State Machine
-Total Order broadcast
-Replicated State Machine and Raft.
-Active Replication vs Primary Backup
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M7: BFT
Intro:
- Byzantine failures.
- Authenticated Channel and crypto assumptions.
- Byzantine Broadcast, consistent and reliable.
Registers:
-Registers with Byzantine failures.
- Safe Register (1,N).
-Regular Register (1,N)
[The regular register only the version with signatures is required]
Consensus:
-synchronous systems: an impossibility result: the necessity of 3f+1 (Not Formal see slides).
-synchronous systems: King Algorithm
-eventually-synchronous system: PBFT"
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
M8: Blockchains
-Permissionless: lottery-based blockchains;
-Permissioned: the PBFT re-branding and intel sawtooth;
References: See reading material on https://sites.google.com/view/distributed-sytems-2019/lectures
[1]: Introduction to Reliable and Secure Distributed Programming - C. Chacin, R. Guerraoui, and L. Rodrigues. 2011.
https://sites.google.com/view/distributed-sytems-2019/lectures
|