Università degli
Studi dell'Aquila
Dipartimento di Informatica
Via Vetoio, Località Coppito,
COURSE PROGRAM
Algorithms for Distributed Systems
A.Y. 2010/11 Prof. Guido Proietti
PART
I: Algorithms for COOPERATIVE Distributed Systems (DS)
1.
Leader Election
· October 11, 2010: Introduction. Message Passing System.
Synchronicity, simmetry, uniformity, anonymousity. Example: distributed Depth First Search
tree computation.
Slides: Introductory elements.
· October 13, 2010: Leader election in rings. Sense of
direction. Impossibility for the anonymous case. Chang&Roberts
algorithm. Hirschberg&Sinclair algorithm.
· October 18, 2010: Leader election in synchronous non-uniform
rings with synchronized start. Leader election in synchronous uniform rings.
· October 20, 2010: Leader election in general topologies
(summary of results). Exercise: execution of the slow-fast algorithm and
pseudo-code generation.
2.
Minimum Spanning Tree
·
October 25, 2010: 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 27, 2010: Detailed description of the synchronous version of the GHS algorithm.
Correctness and time and message complexity analysis. Asynchronous version of
the GHS algorithm. Correctness and time and message complexity analysis.
·
November 3, 2010: Execution of the GHS algorithm in a pseudo-synchronous system.
3.
Maximal Independent Set
· November 8, 2010: 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 10, 2010: 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 15, 2010: Byzantine failures: King algorithm.
Byzantine failures: impossibility with 3 processors out of which one is
Byzantine. General impossibility result.
· November 17, 2010: Exponential-tree algorithm. Correctness
of the exponential-tree algorithm.
·
November 24, 2010: Mid-term assignment
·
November 29, 2010: Mid-term assignment - Solution
PART III: Algorithms for CONCURRENT DS: Mutual exclusion
·
December 1, 2010: 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 6, 2010: Mutex algorithm for 2 processors with bounded
register values. Extension to the case of n processors. No lockout, waiting unboundedness.
PART IV: Algorithms for WIRELESS DS
·
December 13, 2010: Introduction to wireless networks: radio
networks and sensor networks. Signal propagation. The Euclidean model. Broadcasting
in static radio networks: message collision. Round Robin protocol. Selective families protocol.
·
December 15, 2010: Topology control in wireless DS (with no messagge
collision). Overview of topology control algorithms. XTC algorithm.
Properties of XTC on symmetric graphs and unit disk graphs.
PART V: Security aspects of DS: Elements of cryptography
·
December 20, 2010: Network security. Types of attacks. Private-key cryptography.
Public-key cryptography. Message encryption and digital
signature.
·
December 22, 2010: The RSA algorithm. The Miller&Rabin
algorithm. Examples.
PART VI: Algorithms for STRATEGIC DS
1.
Equilibria in
networks
· January 10, 2011: Introduction to game theory. Equilibria. Dominant strategy equilibrium: the prisoners’
dilemma. Nash equilibrium (NE): the battle of sexes. Games without equilibria.
· January 12, 2011: 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 17, 2011: Global connection games. Existence of a
NE: the potential method.
· January 19, 2011: Global connection games: price of anarchy
and price of stability. Lower and
upper bounds.
Slides: Global connection games.
1.
Algorithmic
mechanism design (AMD)
·
January 24, 2011 (3 hours): The implementation problem. Second-price auction. Mechanism design.
Strategy-proof mechanisms. 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.
· 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.
·