Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA

Distributed Systems
A.Y. 2020/21 Prof. Guido Proietti



October 6, 2020: 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

October 8, 2020: Leader election in rings. Sense of direction. Impossibility for the anonymous case. The Chang & Roberts algorithm.

October 13, 2020: Analysis of the Hirschberg & Sinclair algorithm. Leader election in synchronous non-uniform rings with synchronized start.

October 15, 2020: Leader election in synchronous uniform rings: the Frederickson & Lynch algorithm. Leader election in general topologies (summary of results).

October 20, 2020: 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.

Slides: Leader election


2. Minimum Spanning Tree

October 22, 2020: The Minimum Spanning Tree (MST) problem for non-anonymous arbitrary topologies. Preliminary lemmas. Asynchronous and synchronous distributed version of the Prim’s algorithm.

October 27, 2020: 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 29, 2020: Asynchronous version of the GHS algorithm. Correctness (sketch of proof) of asynchronous GHS. Time and message complexity analysis of asynchronous GHS.

Slides: MST

November 3, 2020:  Exercise: execution of the GHS algorithm in a pseudo-synchronous system.

Slides: GHS execution


3. Maximal Independent Set

November 5, 2020: 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.

Slides: MIS

November 10, 2020 (Dott. Stefano Leucci): The Luby’s algorithm for finding a MIS with O(logD D log n) rounds w.h.p.

Slides: Luby

November 12, 2020 (Seminar by Dott. Stefano Leucci): Motion planning problems. Definition of goals: Connectivity, Independent Set, and Clique. Measures: Sum, Max, and Number. Hardness and approximability of Independent Set w.r.t. the Max measure.

Slides: Motion planning


November 17, 2020, at 11.50, on Teams: Mid-term exam.


4. Vertex Coloring

November 19, 2020 (Dott. Stefano Leucci): The Vertex Coloring (VC) problem. A 2D-coloring algorithm. A (D+1)-coloring algorithm (description of the protocol).

Slides: Coloring.


5. Minimum Dominating Set

November 12, 2020: Monitoring a DS: query model. The Minimum Dominating Set (MDS) problem. Greedy algorithm for the MDS problem. Distributed version of the greedy algorithm.  

Slides: Monitoring.

PART II: Algorithms for CONCURRENT DS: Mutual exclusion

November 24, 2020 (Dott. Mattia D’Emidio) (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 26, 2020 (Dott. Mattia D’Emidio) (Dott. Mattia D’Emidio): Mutex algorithm for 2 processors with bounded register values. Extension to the case of n processors: the tournament tree algorithm.

Slides: Mutex.

November 21, 2020: (Seminar by Dott. Mattia D’Emidio) Distance queries in modern large-scale complex networks. Existing solutions and limitations. Dyamic algorithms. Fault-tolerant schemes.

Slides: Distance queries.


PART III: Algorithms for UNRELIABLE DS: The consensus problem

December 1, 2020: 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.

December 3, 2020 (Dott. Mattia D’Emidio): Byzantine failures: the King algorithm. Exercise: failing execution of the King algorithm with n=4 and f=1.

December 10, 2020: Byzantine failures: impossibility with 3 processors out of which one is Byzantine. General impossibility result. Exponential-Gathering Information (EGI) algorithm.

December 15, 2020 (Dott. Mattia D’Emidio): Randomized Byzantine consensus. Exercise: Non-termination of the randomized protocol with n=9 and f=1.

December 17, 2020: Correctness and analysis of the EGI algorithm. Exercise: failing execution of the EGI algorithm with n=3 and f=1.

December 22, 2020: Consensus in the shared-memory model: impossibility result for the Read-Write type variable.

Slides: Consensus.


PART IV: Distributed methods of payment

January 12, 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.

Slides: Bitcoins (Part I)

January 14, 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.

Slides: Bitcoins (Part II)