The goal of the course is to introduce the main algorithmic techniques in the framework of parallel and distributed models of computing; to define the most significant complexity parameters and the computational limits of parallelism and concurrency. Finally computational tools to design and analyze parallel and distributed algorithms are given.

Syllabus
1) Models of computation
a. The PRAM model
b. Bounded degree networks. BSP.
c. The distributed model.
2) Design and analysis of parallel algorithms
a. Prefix sums, List Ranking, Euler tour.
b. Standard techniques and inner sequential problems.
3) Design and analysis of distributed algorithms
a. Communication complexity.
b. Control algorithms.
c. Fault tolerant algorithms .
d. Distributed data manipulation.
4) Classical examples
a. Coordination and Control.
b. Broadcast e Spanning tree.
c. Computation on trees: Saturation, functions evaluation.
d. Election on Ring and other networks.
e. Routing.

Exam consists on a written test, including both the design of algorithms and theoretical questions, and a seminar.