Course Details for A.Y. 2014/2015

The information on this page refer to the academic year 2014/2015. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2014/2015

Name:

Algoritmi per Sistemi Distribuiti / Algorithms for Distributed System

Type:

Course

Basic information

Code:

F0057

Sector:

INF/01

Credits:

: Bachelor Degree in Computer Science 6 CFU (b)
: Master Degree in Computer Science 6 CFU (b)

Term:

1^st semester

Degree(s):

Bachelor Degree in Computer Science 3^rd anno curriculum General Elective
Master Degree in Computer Science 1^st anno curriculum General Compulsory

Language:

English

Course Objectives

The course provides the foundations for designing and analyzing (distributed) algorithms for both cooperative (reliable, faulty, concurrent), and non-cooperative distributed systems (elements of cryptography, equilibria in strategic distributed systems, algorithmic mechanism design).

Course Content

Algorithms for COOPERATIVE Distributed Systems (DS) 1. Leader Election 2. Minimum Spanning Tree 3. Maximal Independent Set
Algorithms for UNRELIABLE DS: The consensus problem
Algorithms for CONCURRENT DS: Mutual exclusion
Security aspects of DS: Elements of cryptography
Algorithms for NON COOPERATIVE (i.e., strategic) DS 1. Equilibria in networks 2. Algorithmic mechanism design

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

By the end of this module students will be able to: 1) understand the difference between a centralized and a distributed algorithm; 2) analyze the resources (space and time) needed by a distributed algorithm; 3) known efficient algorithms for basic computational distributed problems (leader election, consensus, etc.); 4) understand the difference between a canonical and a strategic distributed system.
The aim is to make the student capable of abstracting models and formal algorithmic problems from real distibuted computational problems, and designing efficient algorithmic solutions.
Through the presentation and the comparison of different solutions to a given probelm, students will be guided to learn and to identify independently their most efficient solution.
The course will encourage the development of the following skills of the student: capability of formally presenting and modelling concrete problems, focusing on their main features and discarding the inessential ones.
The course aims to develop in graduate students competencies and abilities necessary in their future studies, especially with respect to doctoral studies on algorithmic topics.

Prerequisites and Learning Activities

Knowledge of basic courses of discrete mathematcs and algorithms.

Assessment Methods and Criteria

Mid-term written examination, followed by a final oral examination, which, for those who performed successfully in the mid-term examination, will be restricted to the second part of the course.

Textbooks

P. Ferragina e F. Luccio, Crittografia , Bollati Boringhieri.
H. Attiya e J. Welch, Distributed Computing , Wiley.
C. Montet e D. Serra, Game Theory & Economics , Palgrave.

Internet Resources

Homepage:

http://www.di.univaq.it/~proietti/didattica.html

Course page updates

This course page is available (with possible updates) also for the following academic years:

To read the current information on this course, if it is still available, go to the university course catalogue .

Course information last updated on: 20 marzo 2014, 13:06