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. 2018/19 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
September 18,
2018: Introduction. Message Passing System (MPS).
Synchronicity, symmetry, uniformity, anonymity. Example: distributed Depth
First Search tree
computation.
Slides: Introductory
elements.
September 20,
2018: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. The Chang & Roberts algorithm.
September 25, 2018: Analysis of the Hirschberg & Sinclair algorithm. Leader election in
synchronous non-uniform rings with synchronized start.
September 27,
2018: Leader election in synchronous uniform rings: the Frederickson & Lynch algorithm. Leader election in
general topologies (summary of results).
October 2,
2018: Exercise:
execution of the slow-fast algorithm and pseudo-code generation.
2. Minimum Spanning Tree
October 4, 2018: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous and synchronous distributed version of the Prim’s algorithm.
October 9,
2018: 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 11,
2018: Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) and time and message complexity analysis of
asynchronous GHS.
October 18,
2018: Exercise:
execution of the GHS algorithm in a pseudo-synchronous system.
3. Maximal
Independent Set
October 16, 2018: 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.
October 23, 2018: The Luby’s algorithm for finding a
MIS with O(logD log n) rounds w.h.p.
4. Vertex
Coloring
October 25, 2018: Contention resolution. The Vertex Coloring
(VC) problem. A 2D-coloring algorithm. A (D+1)-coloring algorithm (description of the protocol).
Slides: Contention resolution,
October 30, 2018: Analysis of the (D+1)-coloring algorithm. Coloring
of a cycle: Cole-Vishkin algorithm.
Slides: Coloring of a cycle (see section 1.4).
November
6, 2018, at 14.30, Room A1.2:
Mid-term exam.
PART II: Algorithms for CONCURRENT DS: Mutual
exclusion
November 13, 2018: 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 15, 2018: Mutex algorithm
for 2 processors with bounded register values. Extension to the case of n
processors: the tournament tree
algorithm.
November 20, 2018: (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 22, 2018: 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 27, 2018: Byzantine
failures: the King algorithm. Exercise: failing execution of the King algorithm
with n=4 and f=1..
November 29, 2018: Byzantine
failures: impossibility with 3 processors out of which one is Byzantine.
General impossibility result. Exponential-Gathering Information (EGI)
algorithm.
December 4, 2018: Correctness and
analysis of the EGI algorithm.
Exercise: failing execution of the EGI algorithm with n=3 and
f=1.
December 6, 2018: Randomized
Byzantine consensus.
Exercise: Non-termination of the randomized protocol with n=9
and f=1.
December 11, 2018: Consensus in the
shared-memory model: impossibility result for the Read-Write type variable.
PART IV: Distributed methods of payment
December 18, 2018 (Seminar by Dott. Giacomo Scornavacca): 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 20, 2018 (Seminar by Dott. Giacomo Scornavacca): 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.