Unit ADVANCED AND DISTRIBUTED ALGORITHMS
- Course
- Informatics
- Study-unit Code
- A002042
- Curriculum
- In all curricula
- Teacher
- Alfredo Navarra
- Teachers
-
- Alfredo Navarra
- Maria Cristina Pinotti (Codocenza)
- Hours
- 42 ore - Alfredo Navarra
- 21 ore (Codocenza) - Maria Cristina Pinotti
- CFU
- 9
- Course Regulation
- Coorte 2023
- Offered
- 2023/24
- Learning activities
- Caratterizzante
- Area
- Discipline informatiche
- Academic discipline
- INF/01
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian
(ENGLISH on demand) - Contents
- Introduction to Distributed Systems. Distributed algorithms and cost measures. Classical algorithms revisited for the distributed environment. Behavior with respect to different graph topologies. In-depth studies about recent research directions and simulation software for distributed systems.
Advanced Design Techniques: Dynamic Programming (DP), and network flow (NF). - Reference texts
- T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduction to algorithms, McGraw-Hill, 2010, ISBN: 978-88-386-6515-8.
J. KLEINBERG and E. TARDOS: Algorithm Design. Pearson Addison Wisley, 2005
Instructional materials used during lectures of Modulo 2 (3 CFU) are, usually, also made available on Unistudium.
N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons. - Educational objectives
- The course provides higher, characterizing algorithmic skills for the CdS.
Learn advanced programming techniques and apply them in new contexts.
Advanced knowledge on distributed algorithm issues.
Increasing critical and application skills - Prerequisites
- Algorithms at intermediate level
- Teaching methods
- Lectures in class
Seminars - Learning verification modality
- Oral exam. The test as a whole makes it possible to ascertain both the capacity for knowledge and understanding, the ability to apply the acquired skills, as well as the ability to exposition.
In case the student intends to advance the examination in a year prior to the one scheduled in the study plan, it is recommended to attend the lecture series and
to take the exam in the first useful call after the said lectures are finished, thus respecting the semester of the teaching schedule. - Extended program
- Introduction to Distributed Systems: Entities, Events, Actions and Communications. Axioms and Restrictions. Costs and Complexity. The Broadcast as example. Flooding algorithm. Complexity of Flooding. States, Events and Configurations. Problems and Solutions. Termination and Correctness. Lower bounds for the Broadcast. Broadcast over complete graphs. Hypercube topology. Dimensional hypercubes. Broadcasting over hypercubes. Wake-Up problem. Wake-Up over hypercubes. Proof about the absence of cycles in Hk(x). Wake-Up over trees. Wake-up over complete graphs. Adversary technique. Traversal problem. DF_Traversal algorithm. Improvements for DF_Traversal algorithm: DF+, DF++. Spanning Tree problem. Shout protocol. Correctness, computational costs and improvements of the Shout protocol. Anonymous graph exploration by means of a finite state automaton. Ad-hoc local orientation for the construction of a Spanning Tree. Right-hand rule. Spanning tree with multiple initiators. Spanning Tree with unique identifiers. MultiShout protocol. Introduction to the saturation technique. Saturation technique. Minimum value search by means of saturation. Leader Election: impossibility results, tree topology, ring topology. AsFar protocol. Gathering problem. Look-Compute-Move Model. Gathering on Rings, Trees, and Grids. Synchronous environment: TwoBits protocol, Speed protocol.
Techniques: Dynamic Programming (DP),
and Network Flow(NF). Examples of DP: knapsack 0/1; minimum number of scalar products for multiplying a sequence of matrices, minimum number of coins for forming a certain amount of money, selection of weighted intervals, Longest Common subsequence.
Network Flow: pseudopolynomial, weakly polynomial and strictly polynomial solutions. Matching.