Unit ADVANCED AND DISTRIBUTED ALGORITHMS
- Course
- Informatics
- Study-unit Code
- A002042
- Curriculum
- In all curricula
- Teacher
- Maria Cristina Pinotti
- Teachers
-
- Maria Cristina Pinotti
- Alfredo Navarra (Codocenza)
- Hours
- 21 ore - Maria Cristina Pinotti
- 42 ore (Codocenza) - Alfredo Navarra
- CFU
- 9
- Course Regulation
- Coorte 2020
- Offered
- 2020/21
- 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
- Advanced Combinatorial Algorithms. 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.
- 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
- The Maximum Flow Problem:
Computing Maximum Flows
Cuts in a Flow Network
Max-Flow Equals Min-Cut
The Preflow-Push Maximum Flow Algorithm
Applications: Disjoint Paths and Bipartite Matchings
Minimum Cost Perfect Matchings .
Computational Geometry:
Line-segment properties
Determining whether any pair of segments intersects
Finding the convex hull
Finding the closest pair of points
Finding Delaunay triangulation
Speeding-up Dynamic programming:
The Monge property
The SMAWK algorithm
Applications.
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.