Parallel and Distributed Algorithms 2010-2011

* 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 B;
• 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.

• Seminar's evaluation and registrations: Thursday 27/1/2011 14-16, room B.

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

Chapter 1

Chapter 2

Chapter 3

Chapter 4

The slides of the lectures are available here. slides

• LIST OF LECTURES