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. 2022/23 Prof. Guido Proietti
September 27,
2022: 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
September 29,
2022: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
October 4, 2022: The Hirschberg
& Sinclair algorithm. Leader election in synchronous non-uniform rings with
synchronized start.
October 6,
2022: Leader election in synchronous uniform rings: the
Frederickson & Lynch algorithm. Leader election in general topologies
(summary of results).
October 11,
2022: 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 13, 2022: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas. Asynchronous
and synchronous distributed version of the Prim sequential algorithm.
October 18,
2022: High-level description of the Borůvka sequential
algorithm. Synchronous version of the Gallager, Humblet e Spira (GHS) algorithm.
Correctness and time/message complexity analysis.
October 20,
2022: Asynchronous version of the GHS algorithm.
Correctness and time and message complexity analysis.
October 25,
2022: Exercise:
execution of the GHS algorithm in a pseudo-synchronous system.
3. Some classic
NP-hard problems: Maximal Independent Set, Minimum Dominating Set, and Vertex
Coloring
October 27, 2022: 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(D log n)
rounds w.h.p.
November 3, 2022 (Dott. Stefano Leucci): The Luby’s
algorithm for finding a MIS with O(logD log n) rounds w.h.p.
November 8, 2022: Network monitoring: the 1-node-failure problem. Hardness of the Minimum
Dominating Set (MDS) problem. The O(log n)-approximation ratio greedy centralized algorithm for MDS,
and its distributed version. Notable cases: unit-disk graphs and planar graphs.
November 10, 2022: The Vertex Coloring
problem. A (D+1)-coloring algorithm based on the
Luby’s algorithm. A 2D-coloring algorithm running w.h.p. in O(log n) rounds.
Mid-term exam: November 17,
2022 at 14.30 in Room A1.3.
PART II: Algorithms for CONCURRENT DS: Mutual exclusion
November 22, 2022 (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 24, 2022 (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
November 29, 2022: 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 1, 2022: Byzantine
failures: the King algorithm. Exercise: failing execution of the King algorithm with n=4
and f=1.
December 6, 2022: Byzantine
failures: impossibility with 3 processors out of which one is Byzantine.
General impossibility result. Exponential-Gathering Information (EGI)
algorithm: the auxiliary tree data structure.
December 13, 2022: Exercise: failing execution of the EGI algorithm with n=3
and f=1. Correctness and analysis of
the EGI algorithm.
December 15, 2022: Randomized
Byzantine consensus.
Exercise: Non-termination of the randomized protocol with n=9 and f=1.
PART IV: Distributed methods of payment
December 16, 2022: 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.
December 21, 2022: 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.