The course introduces the main algorithmic techniques related to parallel and distributed computational models. In particular, we will define the most common complexity concepts useful to analyze these models and their computational limits, and we will introduce the necessary tools to deal with the design and analysis of distributed and parallel algorithms.

Syllabus
1) Computational models:
a. The PRAM model
b. The BSP model
c. The distributed model
2) Basic techniques for the design and analysis of parallel algorithms:
a. Prefix sums, List ranking, Euler tour.
b. Other techniques, and problems hard to parallelize
3) Basic techniques for the design and analysis of distributed algorithms:
a. Communication complexity
b. Control algorithms
c. Fault tolerant algorithms
d. Distributed data
4) Classic problems:
a. Coordination and control
b. Broadcast and Spanning Tree
c. Computation on trees: Saturations and functions' evaluation
d. Election on the ring and in arbitrary networks
e. Routing