Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA
COURSE PROGRAM
Distributed Systems
A.Y. 2020/21 Prof. Guido Proietti
October 6,
2020: Message Passing System (MPS). Synchronicity,
symmetry, uniformity, anonymity. Example: distributed Depth First Search tree
computation.
Slides: Introductory
elements
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
October 8,
2020: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
October 13, 2020: Analysis of the
Hirschberg & Sinclair algorithm. Leader election in synchronous non-uniform
rings with synchronized start.
October 15,
2020: Leader election in synchronous uniform rings: the
Frederickson & Lynch algorithm. Leader election in general topologies
(summary of results).
October 20,
2020: Again on the Frederickson & Lynch algorithm:
counting the number of slow messages when the leader is sleeping. Exercise: execution of
the slow-fast algorithm and pseudo-code generation.
2. Minimum Spanning Tree
October 22, 2020: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous and synchronous distributed version of the Prim’s algorithm.
October 27,
2020: High-level description of the Kruskal
sequential algorithm. Synchronous version of the Gallager,
Humblet e Spira (GHS)
algorithm. Correctness and time and message complexity analysis.
October 29,
2020: Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) of asynchronous GHS. Time and message complexity
analysis of asynchronous GHS.
November 3,
2020: Exercise: execution of the GHS
algorithm in a pseudo-synchronous system.
3. Maximal
Independent Set
November 5, 2020: The Maximal Independent Set (MIS) problem.
A sequential and a generalized greedy algorithm for finding a MIS. A randomized
distributed algorithm for finding a MIS with O(DD log n) rounds w.h.p.
November 10, 2020 (Dott. Stefano Leucci): The Luby’s algorithm for finding a
MIS with O(logD D log n) rounds w.h.p.
November 12, 2020 (Seminar by Dott. Stefano Leucci): Motion planning problems. Definition of goals: Connectivity,
Independent Set, and Clique. Measures: Sum, Max, and Number. Hardness and approximability of Independent Set w.r.t. the
Max measure.
Slides:
Motion planning
November
17, 2020, at 11.50, on Teams:
Mid-term exam.
4. Vertex
Coloring
November 19, 2020 (Dott.
Stefano Leucci): The Vertex Coloring
(VC) problem. A 2D-coloring algorithm. A (D+1)-coloring algorithm (description of the protocol).
PART II: Algorithms for CONCURRENT DS: Mutual
exclusion
November 24, 2020 (Dott.
Mattia D’Emidio): Shared-memory model. The mutual exclusion (mutex)
problem. The mutex problem with Read/Write registers.
The bakery algorithm. Waiting
boundedness, unboundedness of the register values.
November 26, 2020 (Dott. Mattia
D’Emidio): Mutex algorithm for 2
processors with bounded register values. Extension to the case of n processors:
the tournament tree algorithm.
PART III: Algorithms for UNRELIABLE DS: The consensus problem
December 1, 2020: Fault-tolerance
in MPSs: the consensus problem. Link
failures: the 2-general problem. Node crash failures: (f+1)-rounds algorithm
for f crash failures. Lower bound for f crash failures.
December 3, 2020 (Dott. Mattia
D’Emidio): Byzantine failures: the King algorithm. Exercise: failing execution of the King algorithm
with n=4 and f=1.
December 10, 2020: Byzantine
failures: impossibility with 3 processors out of which
one is Byzantine. General impossibility result. Exponential-Gathering
Information (EGI) algorithm.
December 15, 2020 (Dott. Mattia
D’Emidio): Randomized Byzantine consensus.
Exercise: Non-termination of the randomized protocol with n=9 and f=1.
December 17, 2020: Correctness and
analysis of the EGI algorithm.
Exercise: failing execution of the EGI algorithm with n=3 and f=1.
December 22, 2020: Consensus in the
shared-memory model: impossibility result for the Read-Write type variable.
PART IV: Distributed methods of payment
January 12, 2021: The distributed
ledger problem. Cryptographic elements of Bitcoin: Hash functions, One-way functions,
Cryptographic hash functions and attacks, Digital Signatures. Drawbacks of a centralized implementation.
Architecture of Bitcoin: Addresses, Wallets, Transactions, Blocks and the Blockchain. Mining and the Proof-of-Work idea. Lightweight
(SPV) nodes and proof of inclusion using Merkle
trees.
January 14, 2021: Advanced issues
on the Bitcoin protocol. Blockchain forks and their
resolution. Miners and incentives. The Double-Spend attack, the 51% attack.
Consistency and eventual consistency in the distributed ledger problem. Bitcoin
as a repeated consensus problem. Fault-tolerance aspects: crash failures, and
byzantine failures. The sybil
attack. The Fair Consensus problem and a solution through randomized leader
election. Strategic aspects: rational selfish failures, the Rational Fair
Consensus problem, equilibria concepts, selfish mining.