Università degli
Studi dell'Aquila
Dipartimento di Informatica
Via Vetoio, Località Coppito,
COURSE PROGRAM
Algorithms for Distributed Systems
A.Y. 2011/12 Prof. Guido Proietti
PART I: Algorithms for COOPERATIVE Distributed Systems (DS)
1. Leader Election
October 3,
2011: Introduction. Message Passing System. Synchronicity, simmetry, uniformity, anonymousity.
Example: distributed Depth First Search tree computation.
Slides: Introductory
elements.
October 5,
2011: Leader election in rings. Sense of direction.
Impossibility for the anonymous case. Chang&Roberts
algorithm. Hirschberg&Sinclair algorithm.
October 10,
2011: Leader election in synchronous non-uniform rings with synchronized
start. Leader election in synchronous uniform rings.
October 12,
2011: Leader election in general topologies (summary of
results). Exercise: execution of the slow-fast algorithm and pseudo-code
generation.
Slides:
Leader election.
2. Minimum Spanning Tree
October 17, 2011: The Minimum Spanning Tree (MST)
problem for non-anonymous arbitrary topologies. Preliminary lemmas. Asynchronous
distributed version of the Prim’s algorithm. High-level description of the Gallager, Humblet e Spira (GHS) algorithm.
October 19,
2011: Detailed description of the synchronous version of
the GHS algorithm. Correctness and time and message complexity analysis.
October 24,
2011: Asynchronous version of the GHS algorithm.
Correctness (sketch of proof) and time and message complexity analysis of
asynchronous GHS.
October 26,
2011: Exercise: execution of the GHS algorithm in a
pseudo-synchronous system.
3. Maximal Independent Set
November 2, 2011: 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 7, 2011: 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 9, 2011: Byzantine
failures: King algorithm. Byzantine failures: impossibility with 3 processors
out of which one is Byzantine. General impossibility result.
November 14, 2011: Exponential-tree
algorithm. Correctness of the exponential-tree algorithm.
November 16, 2011: Exercise:
execution of the King algorithm and the Exponential-tree algorithm.
November
23, 2011, at 15.00:
Mid-term assignment
PART III: Algorithms for CONCURRENT DS: Mutual exclusion
November 28, 2011: 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 30, 2011: Mutex algorithm
for 2 processors with bounded register values. Extension to the case of n
processors: the tournament tree
algorithm.
December 7, 2011: Tournament tree algorithm: no lockout,
waiting unboundedness. Exercise: example of
execution.
PART IV: Security aspects of DS: Elements of
cryptography
December 12,
2011: Network security. Types of attacks. Symmetric-key cryptography.
Perfect cipher. Examples: one-time pad.
December 14,
2011: Public-key cryptography. Message
encryption and digital signature. The RSA
algorithm.
December 21,
2011: RSA algorithm: examples. The Miller&Rabin algorithm. Examples.
Slides: Cryptography. (for the Italian version click
here).
PART VI: Algorithms for STRATEGIC DS
Equilibria in
networks
January 9,
2012: Introduction to game theory. Equilibria.
Dominant strategy equilibrium: the prisoners’ dilemma. Nash equilibrium (NE):
the battle of sexes. Games without equilibria.
January 11, 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 16,
2012: 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.
Algorithmic mechanism design (AMD)
January 18, 2012: The implementation problem. Second-price
auction. Mechanism design. Strategy-proof mechanisms. Utilitarian problems. VCG
mechanisms.
January 23, 2012: 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 26, 2011: 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.