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. 2014/15 Prof. Guido Proietti

 


PART I: Algorithms for COOPERATIVE Distributed Systems (DS)

1. Leader Election

September 30, 2014: Introduction. Message Passing System. Synchronicity, symmetry, uniformity, anonymity. Example: distributed Depth First Search  tree computation.

Slides: Introductory elements.

October 2, 2014: Leader election in rings. Sense of direction. Impossibility for the anonymous case. Chang&Roberts algorithm. Hirschberg&Sinclair algorithm.

October 9, 2014: Leader election in synchronous non-uniform rings with synchronized start. Leader election in synchronous uniform rings. Leader election in general topologies (summary of results).

October 14, 2014: Exercise: execution of the slow-fast algorithm and pseudo-code generation.

Slides: Leader election.

 

2. Minimum Spanning Tree

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

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

October 28 2014: Exercise: execution of the GHS algorithm in a pseudo-synchronous system.

Slides: MST.

 

3. Maximal Independent Set

October 30 2014: 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) phases w.h.p.

Slides: MIS.

 

PART II: Algorithms for UNRELIABLE DS: The consensus problem

November 4, 2014: 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 6, 2014: Byzantine failures: the King algorithm. Byzantine failures: impossibility with 3 processors out of which one is Byzantine. General impossibility result.

November 11, 2014 (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 13, 2014: Exponential-tree algorithm. Correctness of the exponential-tree algorithm.

November 18, 2014: Monitoring a DS: query model. The Minimum Dominating Set (MDS) and the Minimum Identifying Code (MIC) problem. L-reduction: definition.

November 20, 2014: Exercise: example of execution of the King and the exponential tree algorithm. Question time.

Slides: Consensus.

 

PART III: Algorithms for CONCURRENT DS: Mutual exclusion

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

November 25, 2014: Exercise: example of execution of the King and the exponential tree algorithm and of the tournament tree algorithm.

Slides: Mutex.

 

          December 2, 2014, at 11.00, Room A1.6: Mid-term exam.

 

December 5, 2014: L-reduction from Set Cover (SC) to MDS, and vice versa. Greedy algorithm for the MDS problem. Distributed version of the greedy algorithm. Summary of results for the MIC problem.

Slides: Monitoring.

 

 

PART IV: Algorithms for STRATEGIC DS

1.     Equilibria in networks

December 4, 2014: Introduction to game theory. Equilibria. Dominant strategy equilibrium: the prisoners’ dilemma. Nash equilibrium (NE): the battle of sexes. Games without equilibria.

December 9, 2014: Existence of NE. The price of anarchy (PoA). The selfish routing problem. Pigou’s example and Braess’ paradox. Existence of a Nash flow. PoA for the selfish routing: linear and non-linear latencies.

Slides: Selfish routing.

December 11, 2014: Global connection games. Existence of a NE: the potential method. The price of stability (PoS). Lower and upper bounds for the PoA and the PoS.

Slides: Global connection games.

December 16, 2014: Network creation games. Stable graphs: cliques and stars. Upper bound to the PoS. PoA: state-of-the-art.

Slides: Network creation games.

December 18, 2014 (Seminar by Dott. Stefano Leucci): Network creation games with a host graph (HG). Definition of Maxgame+HG, Maxgame+HG is not a potential game, Convergence issues, Lower bound of Ω(sqrt(n/(1+alpha))) to the PoA.

Slides: Network creation games with HG.

 

2.     Algorithmic mechanism design (AMD)

January 8, 2015: The implementation problem. Second-price auction. Mechanism design. Computational aspects of mechanisms. Strategy-proof mechanisms. Utilitarian problems.

Lecture notes: Algorithmic Mechanism Design (print from page 2 to page 14).

Slides: Algorithmic mechanism design.

January 13, 2015: VCG mechanisms. Clarke payments. Algorithmic Mechanism Design for graph optimization problems.

January 15, 2015: VCG-mechanism for the private-edge Shortest-Path problem. Trivial O(mn) time implementation. Efficient O(m + n log n) time implementation based on the Malik, Mittal, and Gupta algorithm.

Slides: VCG-mechanism for the private-edge SP problem.

January 20, 2015: VCG-mechanism for the private-edge Minimum Spanning Tree problem. Trivial O(mn α(m,n)) time implementation. Efficient O(m α(m,n)) time implementation based on the transmuter.

Slides: VCG-mechanism for the private-edge MST problem.

January 22, 2015: Non-utilitarian, one-parameter problems. One-parameter mechanism for the private-edge Shortest-Path Tree problem. Trivial O(mn) time implementation. Efficient O(m + n log n) time implementation based on the transmuter.

Slides: VCG-mechanism for the private-edges SPT problem.

January 25, 2015: Summary and question time.