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. 2019/20 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
September 24,
2019: Introduction. Message Passing System (MPS).
Synchronicity, symmetry, uniformity, anonymity. Example: distributed Depth
First Search tree
computation.
Slides: Introductory
elements.
September 26,
2019: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
October 1, 2019: Analysis of the
Hirschberg & Sinclair algorithm. Leader election in synchronous non-uniform
rings with synchronized start.
October 3,
2019: Leader election in synchronous uniform rings: the
Frederickson & Lynch algorithm. Leader election in general topologies
(summary of results).
October 8,
2019: Exercise: execution of the slow-fast
algorithm and pseudo-code generation.
2. Minimum Spanning Tree
October 10, 2019: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous and synchronous distributed version of the Prim’s algorithm.
October 15,
2019: 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 17,
2019: Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) of asynchronous GHS.
October 22,
2019: Time and message complexity analysis of asynchronous
GHS. Exercise: execution of the GHS
algorithm in a pseudo-synchronous system.
3. Maximal
Independent Set
October 24, 2019: 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.
October 29, 2019 (Dott. Giacomo Scornavacca): The Luby’s algorithm for finding a
MIS with O(logD D log n) rounds w.h.p.
4. Vertex
Coloring
October 31, 2019 (Dott.
Giacomo Scornavacca): Contention resolution. The Vertex
Coloring (VC) problem. A 2D-coloring algorithm. A (D+1)-coloring algorithm (description of the
protocol).
Slides: Contention resolution,
November
5, 2019, at 14.30, Room A1.2:
Mid-term exam.
5. Minimum
Dominating Set
November 12, 2019: Monitoring a DS:
query model. The Minimum Dominating
Set (MDS) problem.
PART II: Algorithms for CONCURRENT DS: Mutual
exclusion
November 14, 2019 (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 19, 2019 (Dott. Mattia
D’Emidio): Mutex algorithm for 2 processors
with bounded register values. Extension to the case of n processors: the tournament tree algorithm.
November 21, 2019: (Seminar by Dott.
Mattia D’Emidio) Distance queries in modern large-scale
complex networks. Existing solutions and limitations. Dyamic
algorithms. Fault-tolerant schemes.
PART III: Algorithms for UNRELIABLE DS: The consensus problem
November 26, 2019: Fault-tolerance
in MPSs: the consensus problem. Link
failures: the 2 generals problem. Node crash failures:
(f+1)-rounds algorithm for f crash failures. Lower bound for f crash failures.
November 28, 2019 (Dott. Mattia
D’Emidio): Byzantine failures: the King algorithm. Exercise: failing execution of the King algorithm
with n=4 and f=1.
December 3, 2019: Byzantine
failures: impossibility with 3 processors out of which
one is Byzantine. General impossibility result. Exponential-Gathering
Information (EGI) algorithm.
December 5, 2019: Correctness and
analysis of the EGI algorithm.
Exercise: failing execution of the EGI algorithm with n=3 and f=1.
December 10, 2019 (Dott. Mattia
D’Emidio): Randomized Byzantine consensus.
Exercise: Non-termination of the randomized protocol with n=9 and f=1.
December 12, 2019: Consensus in the
shared-memory model: impossibility result for the Read-Write type variable.
PART IV: Distributed methods of payment
December 18, 2019: Electronic
currencies versus traditional currencies.
Drawbacks of a centralized implementation of an electronic currency.
Decentralized implementation of an electronic currency: the double-spending
problem as a consensus problem. The Bitcoin protocol and the Proof-of-Work
idea. The Blockchain.
December 19, 2019: Advanced issues
on the Bitcoin protocol. Dedicated hardware. Memory Based Proof of work.
Selfish mining. Vulnerabilities in the anonymity and in the mining process, and
their relationships with information spreading in peer-to-peer networks.