Università degli Studi dell'Aquila
Dipartimento di Informatica
Via Vetoio, Località Coppito, 67010 L'AQUILA

COURSE PROGRAM
Algorithms for Distributed Systems
A.Y. 2009/10 Prof. Guido Proietti

---

PART I: Algorithms for COOPERATIVE Distributed Systems (DS)

1. Leader Election

· October 19, 2009: Introduction. Message Passing System. Synchronicity, simmetry, uniformity, anonymousity. Example: distributed Depth First Search  tree computation.

Slides: Introductory elements.

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

· October 26, 2009: Leader election in synchronous non-uniform rings with synchronized start.

· October 28, 2009: Leader election in synchronous uniform rings. Leader election in general topologies (summary of results).

Slides: Leader election.

2. Minimum Spanning Tree

· November 2, 2009: 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.

· November 4, 2009: Detailed description of the synchronous version of the GHS algorithm. Correctness and time and message complexity analysis.

· November 9, 2009: Asynchronous version of the GHS algorithm. Correctness and time and message complexity analysis.

· November 16, 2009: Execution of the GHS algorithm in a pseudo-synchronous system.

Slides: MST.

3. Maximal Independent Set

· November 11, 2009: 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 16, 2009: 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. Byzantine failures: King algorithm.

· November 18, 2009: Byzantine failures: impossibility with 3 processors out of which one is Byzantine. General impossibility result. Exponential-tree algorithm.

· November 23, 2009: Correctness of the exponential-tree algorithm.

Slides: Consensus.

PART III: Algorithms for CONCURRENT DS: Mutual exclusion

· November 30, 2009: 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 2, 2009 : Mutex algorithm for 2 processors with bounded register values. Extension to the case of n processors. No lockout, waiting unboundedness.

Slides: Mutex.

· December 7, 2009: Preparation to the mid-term assignment

· December 9, 2009: Mid-term assignment

· January 4, 2010: Mid-term assignment - Solution

PART IV: Security aspects of DS: Elements of cryptography

· December 16, 2009: Network security. Types of attacks. Private-key cryptography. Public-key cryptography. Message encryption and digital signature.

· December 21, 2009: The RSA algorithm. The Miller&Rabin algorithm. Examples.

Slides: Cryptography.

PART V: Algorithms for NON COOPERATIVE (i.e., strategic) DS

1. Equilibria in networks

· January 11, 2010: Introduction to game theory. Equilibria. Dominant strategy equilibrium: the prisoners’ dilemma. Nash equilibrium (NE): the battle of sexes. Games without equilibria.

· January 13, 2010: 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.

· January 18, 2010: Global connection games. PoA: lower and upper bounds.

· January 20, 2010: Existence of a NE: the potential method. The price of stability (PoS): lower and upper bounds.

Slides: Global connection games.

2. Algorithmic mechanism design (AMD)

· January 25, 2010: The implementation problem. Second-price auction. Mechanism design. Strategy-proof mechanisms.

· January 27, 2010: Utilitarian problems. 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.

· February 1, 2010: 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.

Slides: VCG-mechanism for the selfish-edges SP problem.

· February 3, 2010: VCG-mechanism for the Minimum Spanning Tree (MST) problem. Trivial implementation. Efficient O(m·а(m,n)) time implementation based on the transmuter.

Slides: VCG-mechanism for the selfish-edges MST problem.