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 2021
- Offered
- 2021/22
- 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
- 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 Greedy (DP). Examples of DP: knapsack 0/1; minimum number of scalar products for multiplying a sequence of matrices, assembly lines, minimum number of coins for forming a certain amount of money.
Examples of G: inetrval coloring, activity selection, fractionary knapsack. The flow maximum problem. - 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.
N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons. - Educational objectives
- Learning solutions to problems that recur in several applications.
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
- 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 Greedy (DP). Examples of DP: knapsack 0/1; minimum number of scalar products for multiplying a sequence of matrices, assembly lines, minimum number of coins for forming a certain amount of money.
Examples of G: interval coloring, activity selection, 'sand' (fractional) knapsack. The flow maximum problem: Ford-Fulkerson, Scaling Algorithm, Fat paths, Shortest paths, Preflow-push algorithm.