Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA
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.
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.
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.
November 3, 2020: Exercise: execution of the GHS algorithm in a pseudo-synchronous system.
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.
November 10, 2020 (Dott. Stefano Leucci): The Luby’s algorithm for finding a MIS with O(logD D log n) rounds w.h.p.
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.
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).
PART II: Algorithms for CONCURRENT DS: Mutual exclusion
November 24, 2020 (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) : 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
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.
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.
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.