Algoritmi distribuiti e reti complesse

Docente: Andrea Clementi

Comunicazioni

NEWS!!!!

12-09-2017 10:26

Ci sono delle importanti novita' di topics e di struttura per il corso

ADRC. Per maggiori informazioni, si veda il Programma sul sito ufficiale del corso e/o si contatti il prof. Clementi via email.

ADRC II Appello: variazione orario

21-02-2017 10:03

l appello di adrc di giovedi 23 / 02

è spostato alle ore 14.30

ESONERO DEL 12/01/17

13-01-2017 10:20

ESITO ESONERO:

MATR. N. 0225360 : INSUFFICIENTE

FAKHOURY D. : 18/30

VARRICCHIO G. : 24/30

MATR. N. 0248558 : INSUFFICIENTE

POSTICIPO ESONERO

03-01-2017 15:07

Per sopraggiunti impegni medici, l'esonero del 09/01/17 e' spostato in data giovedì 12/01/17 alle ore 14.30 in aula 7.

ESONERO ADRC: INFOS E PRENOTAZIONE

02-01-2017 09:37

Per l'esonero del 9/1/17, gli studenti possono portare i loro appunti e le slides del corso. Gli esercizi e le domande poste saranno relative a progetto ed analisi di protocolli distribuiti per versioni di modelli di comunicazione e di task leggermente diversi da quelli visti a lezione.

Si pregano gli studenti interessati all'esonero di inviare una email di partecipazione al docente (clementi **at**mat uniroma2 it) entro il 6/1/17.

ADRC: Esonero Parte del Prof. Clementi

14-12-2016 09:57

il giorno lunedi 9 gennaio in aula 7 alle ore 14.30

si terra' un esonero scritto, valido per tutti gli studenti interessati, sulla parte del corso tenuta dal Prof. Clementi (Si veda diario delle lezioni a.a. 2016-17)

Lezioni

16	12-12-2016 BROADCAST SU RADIO NETS: LE FAMIGLIE SELETTIVE ED IL LOWER BOUND PER PROTOCOLLI DETERMINISTICI I PROTOCOLLI RANDOMIZZATI: - UN PROTOCOLLO RANDOMIZZATO NON EFFICIENTE IL PROTOCOLLO BGI ANALISI DEL TEMPO DI CONVERGENZA DI BGI SU GRAFI REGOLARI LAYERED. CONFRONTO CON I PROTOCOLLI DETERMINISTICI: IL GAP ESPONENZIALE RANDOM vs DETERMINISTIC
15	05-12-2016 BROADCAST SU RADIO NETS LE FAMIGLIE SELETTIVE UN PROTOCOLLO ERRATO IL PROTOCOLLO SELECTIVE. CORRETTEZZA ANALISI DEL TEMPO DI CONVERGENZA IN FUNZIONE DEL GRADO CONFRONTO CON IL ROUND ROBIN
14	05-12-2016 BROADCAST SU RADIO NETS IL PROTOCOLLO ROUND ROBIN CORRETTEZZA E TEMPO DI CONVERGENZA LA CONOSCENZA DEI PARAMETRI N E D TERMINAZIONE LOCALE E COMPLETAMENTO
13	01-12-2016 - IL MODELLO RADIO NETWORKS - LE STAZIONI RADIO SUL PIANO - LA COMUNICAZIONE NODE-BASED - IL PROBLEMA DELLA COLLISIONE - IL GRAFO DIRETTO DI COMUNICAZIONE - ESEMPI - IL PROBLEMA DEL BROADCAST - FALLIMENTO DEL FLOODING
12	01-12-2016 Elezione di un Leader in un anello La Stage technique Distanza controllata Analisi della correttezza Analsisi della message complexity : O(n log n)
11	21-11-2016 Elezione di un leader Definizione e restrizioni del problema Risultati negativi Elezione in un anello bidirezionale Il protocollo All-The-Way Il protocollo All-The-Way migliorato Analsisi della correttezza, terminazione e message-complexity
10	17-11-2016 Computazioni distribuite su Alberi non etichettati. La tecnica SATURATION per l'elezione di DUE CO-LEADERS Applicazioni della Saturation: Find-Min, Averaging Eccentricita' dei nodi
9	14-11-2016 Il problema del Graph Traversal (DFT in distribuito). Analsisi del problema Il protocollo DFT prima versione. Analisi delle performance Seconda versione del protocollo che migliora il tempo di convergenza da m ad n: la parallelizzazione della scoperta dei nodi visitati.
8	10-11-2016 IL problema dello Spanning Tree Definizione della versione distribuita del problema Confronti con il problema del Broadcast Prime soluzioni informali Il protocollo SHOUT Analsisi della correttezza IL problema dello ST. Analisi della msg complexity del protocollo SHOUT Un possibile miglioramento: il protocollo SHOUT+ Il problema dello ST senza l'assunzione : Single Initiator Risultato di impossibilità. Il problema del Graph Traversal (DFT in distribuito). Analsisi del problema Il protocollo DFT prima versione. Analisi delle performance Seconda versione del protocollo che migliora il tempo di convergenza da m ad n: la parallelizzazione della scoperta dei nodi visitati.
7	07-11-2016 IL problema del Wake-Up sul grafo completo etichettato. il lower bound n log n. Seconda parte della dimostrazione formale Analisi della message complexity di ogni fase formula ricorsiva globale conclusione della dimostrazione Conclusioni sul problema del wake-up
6	03-11-2016 IL problema del Wake-Up sul grafo completo etichettato. il lower bound n log n. La tecnica degli stage e degli universi paralleli: Introduzione informale Prima parte della dimostrazione formale
5	27-10-2016 Conclusione dell'analisi del Broadcast su Hypercube IL problema del Wake-UP IL protocollo WFLOOD Analisi generale in funzione del n. di sorgenti. Analsisi su topologie specifiche.
4	24-10-2016 L'architettura Labeled HYPERCUBE: analisi del diametro, grado, calcolo di cammini minimi. UN protocollo di broadcast ottimale per Hypercube. Analsisi della correttezza, message complexity e tempo di convergenza Valutazioni generali sul problema del broadcast in funzione della topologia della rete.
3	20-10-2016 Un lower bound generale per il problema del Broadcast: dimostrazione formale ed implicazioni. Grafi densi e grafi sparsi: un'alternativa al flood. Architetture parallele efficienti: diametro e grado. Concetto di scalability Introduzione dell'architettura HYPERCUBE
2	17-10-2016 Protocolli per il Broadcast su grafi generali: FLOOD Analisi del FLOOD: correttezza, msg complexity, completion time
1	13-10-2016 IL modello di Calcolo Distributo: Concetti di Base e definizioni informali i grafi di comunicazione le restrizioni gli assiomi definizione di protocollo operazione atomiche tempo e messaggi terminazione locale e globale Un esempio: IL Broadcast
0	10-10-2016 Motivazioni generali IL calcolo distribuito Esempi di decisioni locali descrizione del corso, del materiale didattico, delle propedeudicita', e delle prove

Materiale didattico

Slides + Dispense del corso
Slides + Dispense del corso

Informazioni

Anno accademico	2016-2017
Crediti	9
Settore	INF/01
Anno	1
Semestre	1
Propedeuticità	Nessuna

Programma

Il corso quest'anno avra' un'importante novita'.

Oltre ai due mouli standard di:

a) Calcolo Distribuito (Prof. Clementi)

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

vi sara' un ulteriore modulo (di circa 10 ore di lezione) (Modulo c) che verra' svolto dal Prof. Luca Trevisan che sara' Visiting Professor nel nostro Dipartimento in cui verranno trattati argomenti fondamentali dell'analisi di grafi di grandi dimensioni.

Luca Trevisan è full professor all'Università di Berkeley (CA - USA) e Senior Scientist al

Simons Institute for the Theory of Computing.

https://people.eecs.berkeley.edu/~luca/

Il Prof. Trevisan rappresenta uno dei più importanti scienziati in Theoretical Computer Science in campo internazionale. Questa terza parte verrà erogata nel mese di maggio 2018 e sarà parte integrante del corso ADRC.

L'esame del corso, pertanto, sarà strutturato in due parti.

Negli appelli invernali (febbraio 2018) vi sarà un test intermedio sui moduli (a) e (b), mentre

in tutti gli appelli successivi, gli studenti potranno dare l'esame (ed i test relativi) su tutti e tre i moduli

(a,b, e c).

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 algoritmico 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.

Il modulo (c) il prof. Trevisan introdurra' importanti tecniche di analisi e progettazione di algoritmi

per problemi di ottimizzazione e/o detection su grafi di grandi dimensione. In particolare,

vista la grande dimensione dei dati, verranno studiate tecniche di natura statistica che permettono l'analisi delle performance non nel ''worst-case''.

Qui sotto vengono riportati i programmi preliminari per i 3 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
- Problemi distribuiti avanzati in Social Networks e Data Science

Modulo (b) Teoria Algoritmica dei Gioghi

**** - da inserire *****

Modulo (c) (in inglese - versione preliminare)

Worst-case analysis sometimes overestimates the difficulty of certain problems in practice. In this course we will review more refined methods for the analysis of algorithms, including average-case analysis for random instances, analysis of distributions with a "planted" solution, semi-random models which combine random and adversarial choices, and machine learning problems in which the input is a collection of iid samples from an arbitrary unknown distribution. We will conclude with a brief overview of the theory of average-case complexity, and the evidence that we have that certain problems remain hard even when analyzed with respect to natural classes of distributions. Here is a tentative list of topics that we will cover:

Properties of random graphs
Cliques in random graphs
Independent sets in random graphs
Planted bisection and the stochastic block model
Finding cuts in semi-random graph models
Stable cuts and stable clustering
An introduction to average-case complexity

Testi di riferimento

N. Santoro: Distributed Algorithms + Slides ed Note del Docente

Ricevimento studenti

per appuntamento via email

Modalità di esame

Esame Orale. In base alle richieste degli studenti, verra' presa in considerazione la possibilita' di un esonero intermedio per la prima parte del corso a gennaio.