* Teacher: Linda Pagli, office hours: thursday 16-18, room 277/DE, Dept of Informatica

• Lectures schedule:
  • Tuesday 16-18 room C;
  • Thursday 14-16 room C;
• Code: 284AA;

• Credits: 6 CFU.

• Grade: Determined by a written test.

• Semester: First.

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.

• The PRAM model
• Other models for parallel computation.
• The distributed model.

• Prefix sums, List Ranking, Euler tour.
• Standard techniques and inner sequential problems.

• Communication complexity.
• Control algorithms.
• Fault tolerant algorithms .
• Distributed data manipulation.

• Coordination and Control.
• Broadcast e Spanning tree.
• Computation on trees: Saturation, functions evaluation.
• Election on Ring and other networks.
• Routing.

Nicola Santoro. Design and Analysis of Distributed Algorithms, Whiley ed., 2006
Look also at the official website of the text book.

The slides of the lectures will be available for the students of the course only. slides

• LIST OF LECTURES