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. 2021/22 Prof. Guido Proietti
September 28,
2021: 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 30,
2021: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
October 5, 2021: Analysis of the
Hirschberg & Sinclair algorithm. Leader election in synchronous non-uniform
rings with synchronized start.
October 8,
2021: Leader election in synchronous uniform rings: the
Frederickson & Lynch algorithm. Leader election in general topologies
(summary of results).
October 12,
2021: 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 14, 2021: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous and synchronous distributed version of the Prim’s algorithm.
October 19,
2021: 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 21,
2021: Asynchronous version of the GHS algorithm.
Correctness of asynchronous GHS: Termination.
October 26,
2021: Correctness of asynchronous GHS: sketch of proof Time
and message complexity analysis of asynchronous GHS. Exercise: execution of the GHS algorithm in
a pseudo-synchronous system.
3. Maximal Independent
Set
October 28, 2021: 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 2, 2021 (Dott. Stefano Leucci): The Luby’s
algorithm for finding a MIS with O(logD D log n) rounds w.h.p.
November 4, 2021: 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.
Slides: Network monitoring
Mid-term exam: November 9,
2021 at 14.30 in Room A1.3, in attendance and on a remote basis for DAD
authorized students only on the private channel of the Team ”Distributed Sytems - A.A. 2021-2022”
PART II: Algorithms for CONCURRENT DS: Mutual
exclusion
November 16, 2021 (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 18, 2021 (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 23, 2021: 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 25, 2021: Byzantine
failures: the King algorithm. Exercise: failing execution of the King algorithm with n=4
and f=1.
November 30, 2021: 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 2, 2021: (Seminar by Dott. Mattia D’Emidio) Distance queries in modern large-scale
complex networks. Existing solutions and limitations. Dyamic
algorithms. Fault-tolerant schemes.
December 7, 2021: Correctness and
analysis of the EGI algorithm.
December 9, 2021 (Dott. Mattia D’Emidio): Randomized
Byzantine consensus.
Exercise: Non-termination of the randomized protocol with n=9 and f=1.
December 14, 2021: Exercise: failing execution of the EGI algorithm with n=3
and f=1. Consensus in the shared-memory
model: impossibility result for the Read-Write type variable.
PART IV: Distributed methods of payment
December 16, 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.
December 21, 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.