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. 2023/24 Prof. Guido Proietti
September 26,
2023: 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 28,
2023: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
October 3, 2023: The Hirschberg
& Sinclair algorithm. Leader election in synchronous non-uniform rings with
synchronized start.
October 5,
2023: Leader election in synchronous uniform rings: the
Frederickson & Lynch algorithm. Leader election in general topologies
(summary of results).
2. Minimum Spanning Tree
October 10,
2023: Exercise: execution of the slow-fast
algorithm. The Minimum Spanning Tree (MST) problem for non-anonymous
arbitrary topologies. Preliminary lemmas.
October 12, 2023: Asynchronous and synchronous distributed
version of the Prim sequential algorithm. Exercise: an O(n log
n)-messages asynchronous LE algorithm for the clique topology.
October 17,
2023: 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 19,
2023: Asynchronous version of the GHS algorithm.
Correctness and time and message complexity analysis.
October 24,
2023: Exercise:
execution of the GHS algorithm in a pseudo-synchronous system.
3. Some
classic NP-hard problems: Minimum Dominating Set, Vertex Coloring, and Maximal
Independent Set
October 26, 2023: 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.
October 31, 2023: 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 running w.h.p.
in O(D log n) rounds.
November 2, 2023: The Vertex Coloring
problem. A MIS-based (D+1)-coloring algorithm. A 2D-coloring algorithm running w.h.p. in O(log n) rounds.
November 7, 2023 (prof. Stefano Leucci): The Luby s algorithm for finding a MIS with O(logD log n) rounds w.h.p.
Mid-term exam: November 9,
2023 at 14.30 in Room A1.2.
PART II: Algorithms for CONCURRENT DS: Mutual exclusion
November 14, 2023 (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 16, 2023 (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 21, 2023: 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.
November 28, 2023: Byzantine
failures: the King algorithm. Exercise: failing execution of the King algorithm with n=4
and f=1.
November 30, 2023: 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 5, 2023: Exercise: failing execution of the EGI algorithm with n=3
and f=1. Correctness and analysis of
the EGI algorithm.
December 7, 2023: Randomized
Byzantine consensus.
December 12, 2023: Exercise: Non-termination of the randomized protocol with n=9
and f=1. Consensus in the shared-memory
model: impossibility result for the Read-Write type variable.
December 14, 2023: Exercise: Executions of the randomized protocol with n=8
and f=1.
PART IV: Distributed methods of payment
December 19, 2023: 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, 2023: 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.