Parallel and Distributed Algorithms 2010-2011

General informations

* 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.

Course Outline

Models of computation
  • The PRAM model
  • Other models for parallel computation.
  • The distributed model.
Design and analysis of parallel algorithms
  • Prefix sums, List Ranking, Euler tour.
  • Standard techniques and inner sequential problems.
Design and analysis of distributed algorithms
  • Communication complexity.
  • Control algorithms.
  • Fault tolerant algorithms .
  • Distributed data manipulation.
Classical examples
  • 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.

Course Material

Text Book

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


magistraleinformaticanetworking/alp/alp1011/start.txt · Ultima modifica: 01/02/2011 alle 17:04 (13 anni fa) da Linda Pagli