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. 2016/17 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
September 20,
2016: Introduction. Message Passing System. Synchronicity,
symmetry, uniformity, anonymity. Example: distributed Depth First Search
tree computation.
Slides: Introductory
elements.
September 22,
2016: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. Chang&Roberts
algorithm.
September 27, 2016: Analysis of the Hirschberg&Sinclair algorithm.
Leader election in synchronous non-uniform rings with synchronized start.
September 29,
2016: Leader election in synchronous uniform rings: the
“slow-fast message” algorithm. Leader election in general topologies (summary
of results).
2. Minimum Spanning Tree
October 4, 2016: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous distributed version of the Prim’s algorithm.
October 6,
2016: 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, 2016 (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.
October 13,
2016: Asynchronous version of the GHS algorithm. Correctness
(sketch of proof) and time and message complexity analysis of asynchronous GHS.
October 18,
2016: Exercise:
execution of the GHS algorithm in a pseudo-synchronous system.
3. Maximal Independent Set
October 20, 2016: The Maximal Independent Set (MIS)
problem. A sequential and a general 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 25, 2016: Monitoring a DS: query model. The Minimum Dominating Set (MDS) and the Minimum Identifying Code (MIC) problem.
November 3, 2016: Greedy algorithm for the MDS problem.
Distributed version of the greedy algorithm. Summary of results for the MIC
problem.
November
8, 2016, at 14.30, Room A1.2:
Mid-term exam.
PART II: Algorithms for CONCURRENT DS: Mutual exclusion
November 15, 2016: 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 17, 2016: 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, 2016: Fault-tolerance
in MPSs: the consensus problem. Link
failures: the 2 generals problem. Crash failures in nodes: (f+1)-rounds
algorithm for f crash failures. Lower
bound for f crash failures.
November 24, 2016: Byzantine
failures: the King algorithm.
November 30, 2016: Byzantine
failures: impossibility with 3 processors out of which one is Byzantine.
General impossibility result.
December 1, 2016: Exponential-tree
algorithm. Correctness of the exponential-tree algorithm.
December 6, 2016: Exercise: example of execution of the King and the
exponential tree algorithm.
PART IV: Advanced topics in DS
December 13, 2016 (Seminar by Dott. Giacomo Scornavacca): Distributed methods of payment (Part I).
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
December 15, 2016 (Seminar by Dott. Giacomo Scornavacca): Distributed methods of payment (Part II).
Analysis of the Bitcoin protocol. Vulnerabilities in
the anonymity and in the mining process, and their relationships with
information spreading in peer-to-peer networks.
December 20, 2016: Distributed Storage. Consistent Hashing. Hypercubic Networks. Skip
Lists. Distributed Hash Table (with churn).
Slides:
Distributed Storage. (This
topic will not be part of the final examination)
December 21, 2016: Distributed Sorting. Odd-even sorting. Shearsort. Sorting
networks.
Slides:
Distributed Sorting. (This
topic will not be part of the final examination)