Università degli
Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio,
Località Coppito,
COURSE PROGRAM
Algorithms for Distributed Systems
A.Y. 2012/13 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
October 1,
2012: Introduction. Message Passing System. Synchronicity,
symmetry, uniformity, anonymity. Example: distributed Depth First Search
tree computation.
Slides: Introductory
elements.
October 3,
2012: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. Chang&Roberts
algorithm. Hirschberg&Sinclair algorithm.
October 8,
2012: Leader election in synchronous non-uniform rings with
synchronized start. Leader election in synchronous uniform rings.
October 10,
2012: Leader election in general topologies (summary of
results). Exercise: execution of the slow-fast algorithm and pseudo-code
generation.
2. Minimum Spanning Tree
October 15, 2012: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas.
Asynchronous distributed version of the Prim’s algorithm.
October 17,
2012: 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,
2012: Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) and time and message complexity analysis of
asynchronous GHS.
October 24,
2012: Exercise: execution of the GHS algorithm in a
pseudo-synchronous system.
3. Maximal Independent Set
October 29, 2012: 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
October 31, 2012: 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 5, 2012: Byzantine
failures: King algorithm. Byzantine failures: impossibility with 3 processors
out of which one is Byzantine. General impossibility result.
November 12, 2012: Exponential-tree
algorithm. Correctness of the exponential-tree algorithm.
PART III: Algorithms for CONCURRENT DS: Mutual exclusion
November 14, 2012: 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 19, 2012: Mutex algorithm
for 2 processors with bounded register values. Extension to the case of n
processors: the tournament tree
algorithm.
November 21, 2012: Exercise: example of execution of the
tournament tree algorithm.
November
28, 2012, at 15.00:
Mid-term assignment
PART IV: Algorithms for UNRELIABLE DS: Node failure monitoring
December 3, 2012: Monitoring a DS: query model. The Minimum
Dominating Set (MDS) and the Minimum
Identifying Code (MIC) problem. L-reduction from Set Cover (SC) to MDS, and
vice versa.
December 5, 2012: Greedy algorithm for the MDS problem.
Distributed version of the greedy algorithm. Summary of results for the MIC
problem.
PART V: Security aspects of DS: Elements of
cryptography
December 10,
2012: Network security. Types of attacks. Symmetric-key
cryptography. Perfect cipher. Examples: one-time pad. Public-key cryptography. Message encryption and digital signature.
December 12,
2012: The RSA
algorithm. The Miller&Rabin algorithm.
PART VI: Algorithms for STRATEGIC DS
Equilibria in
networks
December 17,
2012: Introduction to game theory. Equilibria.
Dominant strategy equilibrium: the prisoners’ dilemma. Nash equilibrium (NE):
the battle of sexes. Games without equilibria.
December 19, 2012: 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,
2013: Global connection games. Existence of a NE: the
potential method. Price of anarchy and price
of stability. Lower and upper bounds.
Slides: Global connection games.
January 9,
2013: Network creation games. Stable graphs: cliques and
stars. Price of anarchy and price of stability: upper bounds.
Slides: Network creation games.
Algorithmic mechanism design (AMD)
January 14, 2013: The implementation problem. Second-price auction.
Mechanism design. Strategy-proof mechanisms. Utilitarian problems. VCG
mechanisms.
January 16, 2013: VCG mechanisms: Clarke payments.
Computational aspects of mechanisms. Algorithmic Mechanism Design for graph
optimization problems.
Lecture notes: Algorithmic Mechanism Design (print from page 2 to
page 14).
Slides: Algorithmic mechanism design.
January 21, 2013: VCG-mechanism for the selfish-edges
Shortest-Path (SP) problem. Trivial implementations. Efficient O(m + n logn) time implementation based on the Malik, Mittal, and
Gupta algorithm.