Algoritmi distribuiti e reti complesse

ADRC

A causa della nota pandemia COVID-19, le lezioni del corso per l'a.a. 2020-21 avranno luogo in modalità on line, secondo l'orario ufficiale disponibile sul sito del corso di laurea:

LUNEDI et GIOVEDI  dalle 14:30 alle 16:30. 

IL corso si svolgera' sulla piattaforma TEAM. Nel Team

CLEMENTI-8065531-ALGORITMI_DISTRIBUITI_E_RETI_COMPLESSE

troverete tutte le informazioni e gli appuntamenti relativi al corso. E' fortemente consigliato partecipare attivamente a tutti gli eventi on-line del corso.

Per iscriversi al suddetto TEAM specifico, *dopo* aver verificato l'attivazione ed il funzionamento delle proprie credenziali sulla suddetta piattaforma (rivolgendosi eventualmente ed esclusivamente ai contatti utili per  questa procedura), in caso di problemi specifici con il team di ADRC, lo studente interessato è pregato di inviare una email ai docenti del corso ADRC specificando nel soggetto "ADRC Team".

ADRC: MODALITA' ESAMI ONLINE

Gli appelli della sessione estiva saranno svolti oralmente in modalita' on-line utilizzando la piattaforma TEAMS, ovvero altri strumenti di comunicazione comunicati agli studenti. A tal fine si prega ogni studente interessato di: iscriversi al Team di ADRC su TEAMS, e, per chi intende  prenotarsi per   l'appello di giugno, di inviare una email ai proff clementi e guala' entro il 10 giugno (oltre a prenotarsi su DELPHI).

ESONERO ADRC DEL 09-01-2020: ESITO

• STUDENTE (sigla o matricola)        VOTAZIONE
• 0286217 .....................................      20/30
• ML    ..........................................      28/30
• MAR-POL ....................................      28/30

ESONERO DEL 9-01-2020

Si conferma che giovedi dalle 14.00 alle 16 (circa), 

in aula 7, si terra' l'esonero relativo alla parte del corso del Prof. Clementi. Pertanto, la lezione del dr. Guala' e' posticipata al lunedi successivo.

LEZIONE DI LUNEDI 28/10

La lezione di  Lunedì 28/10/2019 non avrà luogo.

Test intermedio per il I Modulo

I Protocolli PUSH-PULL per il Broadcast su  grafi Expanders. Analisi del protocollo PULL su Expanders. 

 Dinamiche di Voting per il Consensus: Definizioni, e prime proprietà. Analisi della k-majority per il Majority Consensus. 

I Modelli di Comunicazione: GOSSIP. Introduzione e definizione formale dei modelli PULL et PUSH

Il protocollo BGI per il Broadcast su Radio Networks. Analisi della correttezza e del Tempo (Parte II) 

Il protocollo BGI per il Broadcast su Radio Networks. Analisi della correttezza e del Tempo (Parte I)  

Introduzione ai protocolli randomizzati: Definizioni generali. Esempio: Leader Election su Unlabeled Ring. 

RADIO BROADCAST

- Il Protocollo SELECT: Analisi correttezza e complessità in funzione del grado d.

- Il Metodo Probabilistico in Computer Science: nozioni fondamentali

- Costruzione probabilistica  di famiglie (n.k)-selettive di dimensione ottimale.

- Un Lower Bound al RADIO BROADCAST per protocolli deterministici (senza dimostrazione).

(si veda note ed articoli nel materiale didattico allegato)

RADIO BROADCAST

- Analisi della correttezza e della convergenza del protocollo RoundRobin RR.

- Conoscenza locale del parametro n: tecniche di simulazione e guess.

- Crticità del protocollo RR.

- Il concetto di famiglia (n,k)-selettiva H

- Un primo utilizzo ``sbagliato'' di H

- Il protcollo SELECT per grafi di grado limitato d

- Riassunto della Leader Election su Ring

- Leader Election su Meshes

- Introduzione al modello Radio Networks

- Motivazioni e definizione formale

- assunzioni del modello

- Il problema del Broadcast

- Introduzione al protocollo Round Robin

- Analisi della Saturation Techniques su Alberi

Applicazioni: il calcolo del minimo, della media, funzioni algebriche calcolabili.

- Il problema della Leader Election: Motivazioni e Definizione

- Risultato di Angluin: Non calcolabilita'

- La Leader Election su Ring: 2 protocolli semplici

- Le Leader Election su Ring: Il protocollo Controlled Distance

- Il task "Depth First Traversal" (DFT): motivazioni e definizione

- Restrizioni

- Il protocollo DFT: descrizione dettagliata  e correttezza

- Il protocollo DFT:  analisi della msg complexity e della time complexity.

- Parallelizzare i messaggi di Feedback: DFT+, un protocollo più veloce.

- Analisi della complessità di DFT+

- Topologie ad Albero: introduzione alla Saturation

- IL task "Spanning Tree": motivazioni e definizione.

- Restrizioni

- Il protocollo Shout

- Analisi correttezza e complessità di Shout

- Migliorare la message complexity: Il protocollo Shout+

- Analisi di Shout +

- Il caso Multiple Initiator: la rottura della simmetria ed risultato di non-calcolabilità forte.

 - Il Broadcast su    Labeled Hypercube H.

-  Il protocollo Hyper-Flood

- Analisi  della correttezza e della complessità di HF

- il sottoalbero generato da HF

- Il problema del Wake-UP

- Un protocollo  per WU su topologie generali: correttezza e

complessità. Dipendenza dal numero di initiators.

- Considerazioni e confronto tra Broadcast e WU nei vari settings

- Il lower Bound per il WU nel caso del grafo completo

- Argomenti  generali  di lower bound su modelli di calcolo distribuiti

- Un'applicazione per il Broadcast: il lower bound ottimale  sulla msg complexity

- Topologie di reti particolari: La Labeled Hypercube H.

- Proprietà topologiche di H: grado, diametro, cammini minimi.

Concetti formali e caratteristiche fondamentali del Modello Distribuito Link-Based

Correttezza e terminazione locale e globale

Istruzioni Atomiche

Modelli sincroni ed asincroni

Message Complexity

Ideal Parallel Time

Il Problema del Broadcast

Restrizioni Standard

Definizione del protocollo Flood

Analisi della Correttezza di Flood

Cap I-II  del libro di Santoro

08-10-2018

Panoramica dei  modelli di calcolo distribuito che verranno studiati nel corso.

Il modello link-based ed il modello radio networks, cenni.

Grafi

Definizioni di problemi/task computazionali in modelli distribuiti: Input ed Ouput. 

Un esempio di task distribuito: la classe di bambini che giocano.

Il concetto di visione locale e sincronizzazione

Definizione degli ingredienti fondamentali di un modello distribuito (Parte I)

Cap I del libro di Santoro

RADIO BROADCAST AND SELECTIVE FAMILIES

notes on consensus processes

notes on randomized protocols

Slides del Corso

Il corso ADRC per l'a.a. 2019-20 sarà costituito da due moduli:

a) Calcolo Distribuito  (Prof. Clementi)

b) Teoria Algoritmica dei Giochi (Dr. Gualà)

Il modulo (a)

presenta i principi fondamentali del calcolo distribuito sia da un punto di vista dei modelli di comunicazione/computazione più importanti che per quanto riguarda i metodi algoritmici fondamentali per tali modelli. 

L'obiettivo formativo e' quello di fornire degli strumenti efficienti e rigorosi per il Problem Solving in cui, rispetto ai corsi algoritmici della triennale, per la prima volta le entità computazionali (agenti)  sono molteplici ed interagenti.
Questo nuovo paradigma offre ottime  basi per progettare  protocolli efficienti per problemi fondamentali ed estremamente attuali nel mondo dei moderni sistemi distribuiti.
Questa parte sarà tenuta del Prof. Clementi e sarà di 6 cfu.
 
Nel modulo (b), il Dr. Gualà tratterà un altro aspetto fondamentale
dei sistemi distribuiti moderni: la presenza di comportamenti egoistici degli agenti di un sistema distribuito. Tale presenza ha portato negli ultimi decenni a sviluppare un'importante teoria:
l'Algorithmic Game Theory. Profondamente ispirata dalla famosa Game Theory (Nash Equilbria), questa teoria viene trattata nel corso per affrontare importanti problematiche nel campo dell'ottimizzazione di reti di comunicazione e di altre applicazioni.

Qui sotto vengono riportati i  programmi preliminari per i 2 moduli. 
 
Modulo (a):  Algoritmi Distribuiti  
- Modelli di computazione distribuiti: paradigmi, algoritmi, misure di complessità, comunicazione
- Un processo epidemico: Il  Broadcast e l'Information Spreading
- Il problema del Wake-Up
- Il problema dello Spanning Tree
- Il problema del Leader Election
- Il Modello Wireless: il fenomeno delle collisioni
- Il Broadcast su Wireless Networks: protcolli  deterministici e randomizzati
- Modelli e Processi  Distribuiti avanzati in    Network Science  
 
Modulo (b)  Teoria Algoritmica dei Gioghi
 
**** - da inserire *****

N. Santoro: 

Design and analysis of Distributed Algorithms +  Slides e Note del Docente disponibili sulla piattaforma Teams

Per appuntamento via email con i Docenti.