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


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.

Slides: MST.

 

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.

Slides: MIS.

 

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.

Slides: Consensus.

 

          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.

Slides: Mutex.

 

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.

Slides: Selfish routing.

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.

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