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. 2024/25 Prof. Guido Proietti
September 23,
2024: 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 25,
2024: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
October 1, 2024: The Hirschberg
& Sinclair algorithm. Lower bound of W(n log n)
messages for asynchronous rings.
October 3,
2024: Leader election in
synchronous non-uniform rings with synchronized start. Leader
election in synchronous uniform rings: the Frederickson & Lynch algorithm.
Leader election in general topologies (summary of results).
2. Minimum Spanning Tree
October 8,
2024: Exercise: execution of the slow-fast
algorithm. The Minimum Spanning Tree (MST) problem for non-anonymous
arbitrary topologies. Preliminary lemmas.
October 10, 2024: Asynchronous and synchronous distributed
version of the Prim sequential algorithm.
October 15,
2024: 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 17,
2024: Asynchronous version of the GHS algorithm.
Correctness and time and message complexity analysis.
October 24,
2024: 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 29, 2024: 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.
October 30, 2024: 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.
Mid-term exam: Tuesday November 5, 2024 at 16.30 in Room
A1.4.
November 12, 2024: 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 14, 2024: Two (D+1)-coloring algorithms running w.h.p. in O(log n) rounds.
PART II: Algorithms for CONCURRENT DS: Mutual exclusion
November 19, 2024: 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 20, 2024: Mutex algorithm
for 2 processors with bounded register values. Extension to the case of n
processors: the tournament tree (TT)
algorithm. Exercise:
sample execution of the TT algorithm.
PART III: Algorithms for UNRELIABLE DS: The consensus problem
November 26, 2024: 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 27, 2024: Byzantine
failures: the King algorithm. Exercise: failing execution of the King algorithm with n=4
and f=1.
December 3, 2024: 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 4, 2024: Correctness and
analysis of the EGI algorithm. Exercise: failing execution of the EGI algorithm with n=3
and f=1.
December 10, 2024: Randomized
Byzantine consensus for n>8f processors in O(log n) rounds w.h.p.
December 11, 2024: Exercise: Example of 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.
PART IV: Distributed methods of payment
December 18, 2024: The distributed
ledger problem. Hash functions, One-way functions, Digital Signatures. Relations
with the consensus problem: collusions and Sybil attacks. Drawbacks of a
centralized implementation: Consistency and eventual consistency in the
distributed ledger problem.
December 19, 2024: Architecture of
the Bitcoin network: Addresses, Wallets, Transactions. The Bitcoin Blockchain: Mining and the Proof-of-Work idea. Blockchain forks and their resolution. Miners and
incentives. Lightweight (SPV) nodes and proof of inclusion using Merkle trees.