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.
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.
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.
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.
November 13, 2014: Exponential-tree
algorithm. Correctness of the exponential-tree algorithm.
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.
December
2, 2014, at 11.00, Room A1.6:
Mid-term exam.
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.
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.