**Università degli
Studi dell'Aquila**

**Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica**

Via Vetoio,
Località Coppito, 67010 L'AQUILA

**COURSE PROGRAM**

**Algorithms for Distributed Systems**

A.Y. 2015/15 Prof. Guido Proietti

PART I: Algorithms for COOPERATIVE Distributed Systems (DS)

1. Leader Election

**September 29,
2015:** Introduction. Message Passing System. Synchronicity,
symmetry, uniformity, anonymity. Example: distributed *Depth First Search*
tree computation.

**Slides**: Introductory
elements.

**October 1,
2015: **Leader election in rings. Sense of direction.
Impossibility for the anonymous case. Chang&Roberts
algorithm. Introduction of the Hirschberg&Sinclair
algorithm.

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

**October 8,
2015: **Further variants of the Hirschberg&Sinclair algorithm.
Leader election in synchronous uniform rings. Leader election in general
topologies (summary of results).

**October 13,
2015:** Exercise:
execution of the slow-fast algorithm and pseudo-code generation.

2. Minimum Spanning Tree

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

**October 20,
2015:** 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 22,
2015:** Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) and time and message complexity analysis of
asynchronous GHS.

**October 27,
2015:** Exercise:
execution of the GHS algorithm in a pseudo-synchronous system.

3. Maximal Independent Set

**October 29, 2015:** 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

**November 3, 2015:** Monitoring a DS: query model. The *Minimum
Dominating Set* (MDS) and the *Minimum
Identifying Code* (MIC) problem.

**November 5, 2015:** L-reduction from Set Cover (SC) to MDS, and vice versa.

**November 10, 2015:** Greedy algorithm for the MDS problem.
Distributed version of the greedy algorithm. Summary of results for the MIC
problem.

PART II: Algorithms for CONCURRENT DS: Mutual exclusion

**November ****12, 2015:** 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, 2015:** Mutex algorithm
for 2 processors with bounded register values. Extension to the case of n
processors: the *tournament tree*
algorithm.

** November
24, 2015, at 15.00, Room A0.5:**
Mid-term exam.** **

PART III: Algorithms for UNRELIABLE DS: The consensus problem

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

**December 3, 2015: **Byzantine
failures: the King algorithm.

**December 10, 2015: **Byzantine
failures: impossibility with 3 processors out of which one is Byzantine.
General impossibility result.

**December 15, 2015: **Exponential-tree
algorithm. Correctness of the exponential-tree algorithm.

**December 17, 2015:** Exercise: example of execution of the
King and the exponential tree algorithm. Question time.

PART IV: Advanced topics in DS (All the topics here will not be part of the final
examination)

**December 22, 2015:** A list of advanced topics in distributed
systems.

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

**January 12, 2016: (Reference
group: Ravjndran Shankar Raman and Domenico Guglielmi): **Distributed
Systems Security.

**January 14, 2016: (Reference
group: Nicholas Angelucci and Domenico
Di Cesare):** Byzantine
agreement and databases.** **

** (Reference
group: Ayash Dima, Payares Kelwin, and Najem Tala):** Parallel
computation for matrix multiplication.

**January 19, 2016: (Reference
group: Stefania Cicchini
and Luana Dell'Elce):** Byzantine
agreement and Intrusion detection systems.** **

** ****(Reference group: Gabriella D'Andrea and Sara Ciccolone):** Luby's algorithm.

**(Reference group:** **Giuseppe Di Lena and Giuseppe Tomei):** Self-stabilizing
systems.

**January 21, 2016: (Reference
group: Roberta Capuano and Jha Vikas):** Rendez-vous on a ring.** **

** ****(Reference group: Daniele Alaggia and Mohammad
Sohrabi): **Parallel
processing of large graphs.

**(Reference group:** **Deepak Krishna and Riccardo Rubei):** Concurrent
Broadcast for Information Dissemination.