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. 2013/14 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
October 1,
2013: Introduction. Message Passing System. Synchronicity,
symmetry, uniformity, anonymity. Example: distributed Depth First Search
tree computation.
Slides: Introductory
elements.
October 3,
2013: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. Chang&Roberts
algorithm. Hirschberg&Sinclair algorithm.
October 8, 2013: 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 10,
2013: Exercise: execution of the slow-fast algorithm and
pseudo-code generation.
2. Minimum Spanning Tree
October 15, 2013: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous distributed version of the Prim’s algorithm.
October 17,
2013: 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,
2013: Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) and time and message complexity analysis of
asynchronous GHS.
October 24,
2013: Exercise: execution of the GHS algorithm in a
pseudo-synchronous system.
3. Maximal Independent Set
October 31, 2013: 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.
PART II: Algorithms for UNRELIABLE DS: The consensus problem
November 5, 2013: Fault-tolerance
in MPSs: the consensus problem. Benign failures in links: the 2 generals
problem. Benign failures in nodes: (f+1)-rounds algorithm for f failing
processors.
November 7, 2013: Byzantine
failures: King algorithm. Byzantine failures: impossibility with 3 processors
out of which one is Byzantine. General impossibility result.
November 12, 2013 (Seminar by Dott. Stefano Leucci): Motion planning
problems. Goals: Connectivity, Independent Set, and Clique. Measures: Sum, Max,
and Number. Hardness and approximability of
Independent Set w.r.t. the Max measure.
November 14, 2013: Exponential-tree
algorithm. Correctness of the exponential-tree algorithm.
November 19, 2013: Monitoring a DS: query model. The Minimum Dominating Set (MDS) and the Minimum Identifying Code (MIC) problem.
L-reduction: definition.
November 21, 2013: Exercise: example of execution of the
King and the exponential tree algorithm. Question time.
November
26, 2013, at 15.00, Room A1.6:
Mid-term assignment (postponed due to bad weather conditions)
December 3, 2013: Mid-term assignment.
December 5, 2013: 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.
PART III: Algorithms for CONCURRENT DS: Mutual exclusion
December 10, 2013: 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.
December 12, 2013: Mutex algorithm
for 2 processors with bounded register values. Extension to the case of n
processors: the tournament tree
algorithm.
PART IV: Algorithms for STRATEGIC DS
Equilibria in
networks
December 17,
2013: Introduction to game theory. Equilibria.
Dominant strategy equilibrium: the prisoners’ dilemma. Nash equilibrium (NE):
the battle of sexes. Games without equilibria.
December 19, 2013: 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.
January 7,
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.
January 9,
2014: Network creation games. Stable graphs: cliques and
stars. Upper bound to the PoS. PoA:
state-of-the-art.
Slides: Network creation games.
January 14, 2014: 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.
Algorithmic mechanism design (AMD)
January 21, 2014: The implementation problem. Second-price
auction. Mechanism design. Strategy-proof mechanisms. Utilitarian problems. VCG
mechanisms. Clarke payments.
Lecture notes: Algorithmic Mechanism Design (print from page 2 to
page 14).
Slides: Algorithmic mechanism design.
January 23, 2014: Computational aspects of mechanisms.
Algorithmic Mechanism Design for graph optimization problems. VCG-mechanism for
the private-edge Shortest-Path (SP) problem. Trivial implementations. Efficient
O(m + n logn) time implementation based on the Malik,
Mittal, and Gupta algorithm.
Slides: VCG-mechanism for the selfish-edges SP problem.