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. 2017/18 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
September 19,
2017: Introduction. Message Passing System (MPS).
Synchronicity, symmetry, uniformity, anonymity. Example: distributed Depth
First Search tree computation.
Slides: Introductory
elements.
September 21,
2017: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. Chang&Roberts
algorithm.
September 26, 2017: Analysis of the Hirschberg&Sinclair algorithm.
Leader election in synchronous non-uniform rings with synchronized start.
September 28,
2017: Leader election in synchronous uniform rings: the
“slow-fast message” algorithm. Leader election in general topologies (summary
of results).
October 3,
2017: Exercise:
execution of the slow-fast algorithm and pseudo-code generation.
2. Minimum Spanning Tree
October 5, 2017: The Minimum Spanning Tree (MST) problem
for non-anonymous arbitrary topologies. Preliminary lemmas. Asynchronous and
synchronous distributed version of the Prim’s algorithm.
October 10,
2017: 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 12,
2017: Asynchronous version of the GHS algorithm. Correctness
(sketch of proof) and time and message complexity analysis of asynchronous GHS.
October 17,
2017: Exercise:
execution of the GHS algorithm in a pseudo-synchronous system.
3. Maximal Independent Set
October 19, 2017: 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.
4. Minimum Dominating Set
October 24, 2017: Monitoring a DS: query model. The Minimum Dominating Set (MDS) and the Minimum Identifying Code (MIC) problem.
October 26, 2017: L-reduction from Set Cover (SC) to MDS, and vice versa.
October 31, 2017, 14.30-16.30: (Seminar
by Dott. Mattia D’Emidio) Distance
queries in modern large-scale complex networks.
October 31, 2017, 16.30-17.30: Greedy
algorithm for the MDS problem. Distributed version of the greedy algorithm.
Summary of results for the MIC problem.
November
7, 2017, at 14.30, Room A1.2:
Mid-term exam.
PART II: Algorithms for CONCURRENT DS: Mutual exclusion
November 14, 2017: 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, 2017: 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 22, 2017: 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 24, 2017: Byzantine
failures: the King algorithm. Exercise: failing execution of the King algorithm with n=4 and f=1..
November 28, 2017: Byzantine
failures: impossibility with 3 processors out of which one is Byzantine.
General impossibility result. Exponential-Gathering Information (EGI)
algorithm.
November 30, 2017: Correctness and
analysis of the EGI algorithm.
Exercise: failing execution of the EGI algorithm with n=3 and
f=1.
December 5, 2017: Randomized
Byzantine consensus.
Exercise: Non-termination of the randomized protocol with n=9
and f=1.
December 7, 2017: Consensus in the
shared-memory model: impossibility result for the Read-Write type variable.
PART IV: Distributed methods of payment
December 14, 2017 (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 19, 2017 (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.