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.