Comunicazioni
ESONERO ADRC DEL 10-01-19: VISIONE11-01-2019 15:50Gli studenti interessati alla visione delle correzioni del proprio scritto possono venire lunedi 14-01 alle ore 12 presso lo studio del prof. Clementi.
|
ESONERO ADRC DEL 10-01-19: ESITO11-01-2019 13:06
Gli studenti non riportati nella lista quì sopra hanno conseguito una votazione largamente insufficiente.
Si ricorda che la votazione (positiva) verra' mantenuta per tutti i prossimi appelli a meno che uno studente non decida e comunichi di voler ripetere la prova. |
ESONERO PARTE I19-12-2018 18:25Si comunica che la prova di esonero scritto relativa alla parte del Prof. Clementi avra' luogo GIOVEDI 10 GENNAIO, ORE 14, in AULA 7. E' richiesta la prenotazione per ogni interessato inviando una email all'indirizzo del prof. Clementi: clementi@mat.uniroma2.it con Subject;: ESONERO ADRC
|
NOTE: II VERSIONE28-11-2018 15:44Si avvisano gli studenti che entro domani mattina sara' disponibile una nuova versione delle note relative alle lezioni sui protocolli randomizzati del Prof. Clementi |
ADRC: orario inizio lezioni22-11-2018 14:12Si ricorda agli studenti che a partire da giovedi 22/11, l'orario di inizio del corso e' fissato alle 14.30
|
Inizio corso26-09-2018 10:08Il corso avrà inizio lunedi 8 ottobre alle 14.30 con il I modulo (Prof. Clementi) |
Lezioni
| 25 | 24-01-2019 Il problema del calcolo di un Equilibrio di Nash (in strategie pure) in un Congestion Game. Perché è improbabile che il problema sia NP-hard. La giusta classe di complessità: PLS-completezza. |
| 24 | 21-01-2019 Stackelberg Minimum Spanning Tree Game. Un problema di prezzatura di reti che nasce da uno scenario di teoria dei giochi. Hardness del problema e un algoritmo di approssimazione con fattore logaritmico. |
| 23 | 17-01-2019 Generalizzando l'asta del singolo oggetto: il problema dell'asta combinatorica. Un meccanismo VCG veritiero ed esatto per il problema, ma non implementabile in tempo polinomiale (a meno che P=NP). Meccanismo one-parameter approssimato: un buon algoritmo monotono per il problema di ottimizzazione soggiacente. |
| 22 | 14-01-2019 Il problema del cammino minimo tra due nodi in un grafo con archi privati: un meccanismo VCG. Il problema dell'albero dei cammini minimi con archi privati: problemi non utilitari. Problemi one-parameter e meccanismi one-parameter: truthfulness e monotonia. |
| 21 | 07-01-2019 Algorithmic Mechanism Design. Asta singolo oggetto (versione massimizzazione e minimizzazione). Una soluzione elegante: second-price auction. Meccanismi VCG. Pagamenti di Clarke e volontaria partecipazione. |
| 20 | 20-12-2018 Local Connection Game. Stima del prezzo della stabilità. Stima del prezzo dell'anarchia. Complessità computazionale del problema di trovare la best move. |
| 19 | 17-12-2018 Introduzione ai Formation Games; Global Connection Game. Stima del prezzo dell'anarchia. Tecnica del potenziale. Esistenza dell'equilibrio, convergenza all'equilibrio. Stima del prezzo della stabilità. Complessità computazionale del problema di trovare dei buoni equilibri di Nash. Un esercizio: Max-Cut game. |
| 18 | 13-12-2018 Introduzione al corso. Di cosa di si occupa l'Algorithmic Game Theory. Due tradizioni si incontrano: Teoria degli Algoritmi e Teoria dei Giochi. Concetti fondamentali: gioco, giocatori, strategie, outcome ed equilibri. Equilibro in strategie dominanti. Equilibrio di Nash in strategie pure e miste. Teorema di Nash. Prezzo dell'Anarchia e Prezzo della Stabilità. Esempi di giochi. Selfish Routing e paradosso di Braess. |
| 17 | 10-12-2018 - Processi di Information Spreading su Expanders:
I protocolli Push-Pull
Analsisi della convergenza del protocollo Pull su alcune classi di grafi expanders. discussioni finali sul I modulo |
| 16 | 06-12-2018 - Analisi del Protocollo RTA II: Dimostrazione delle proprieta' di espansione del Grafo di output nel caso d= log n
- Processi di Information Spreading su Expanders: Introduzione
|
| 15 | 03-12-2018 Il protocollo RTA per la costruzione di grafi random G. Analisi in concentrazione del grado massimo: caso d costante e caso d = logn n.
Concetto di Vertex Expansion di un Grafo Diametro di un Expander: dimostrazione mediante BFS. |
| 14 | 29-11-2018 La 3-Majority dynamics: conclusione dell'analisi delle tre fasi del processo in valor medio ed in concentrazione.
La costruzione di grafi random mediante protocolli distribuiti Il Protocollo Request Then Accept (RTA). Analisi del grafo random in output di RTA: - numero di archi, numero di messaggi e grado medio
|
| 13 | 26-11-2018 Analisi della 3-Majority partendo da un Bias iniziale. Dimostrazione del tempo convergenza (PARTE I) con applicazione dei Chernoff's Bounds. |
| 12 | 22-11-2018 Analisi probabilistica del protocollo randomizzato per la Leader Election: Risultati in alta concentrazione della misura.
- Il problema del Consenso e del Majority Consenso - I meccanismi di comunicazione random: PUSH & PULL - Concetto di Efficienza: numero di rounds, numero di messaggi, congestion, numero di random queries. - Metodi di alta concentrazione per distribuzione binomiali: Chernoff's Bounds - Obiettivi strategici: campionamento distribuito ed aggregato e confronto con campionamento centralizzato - Le dinamiche h-majority - Analsisi del ''Expected-Drift'' della 1-majority (e della 2-majority) |
| 11 | 19-11-2018 Leader Election su Anelli: la Stage Technique. -Correttezza e Message complexity del Protocollo.
Introduzione agli Algoritmi Distribuiti Randomizzati Concetti e notazioni fondamentali: Spazi di Probabilità, Variabili Aleatorie, Valor Medio. Un primo esempio di Protocollo Randomizzato: La Leader Election su un anello con nodi non etichettati. |
| 10 | 15-11-2018 - Il Protocollo ALL-the-way per la Leader Election su Anelli. Analisi della correttezza e della message e time complexity
- Il Protocollo As Far (as it can): analisi della correttezza e del miglioramento della message complexity worst-case e best-case.
|
| 9 | 12-11-2018 Ulteriore analisi della Saturation Techniques. Il prblema della Leader Election (LE) Non calcolabilita' della LE in anonymous networks. LE mediante Saturazione in un Albero LE in un anello: un primo protocollo. |
| 8 | 08-11-2018 Risultato di impossibilità di calcolo dello ST in caso di piu' initiator Terminazione locale e globale e gli alberi di broadcast Il problema DFS distribuito: la distribuzione di un token in un sistema distribuito in mutua asclusione. Un protocollo corretto: analisi della msg complexity un protocollo corretto ed efficiente: analisi della time complexity Processi di saturazione in un albero Analsisi della correttezza e della message complexity della saturazione su alberi Applicazioni della saturazione: il calcolo del minimo; il calcolo della media Proprieta' delle funzioni calcolabili mediante saturazione |
| 7 | 05-11-2018 Analisi della Message Complexity del Protocollo Shout Modifica e descrizione del Protocollo Shout+ Analisi del Protocollo Shout+ Proprieta degli alberi costruiti da Shout
|
| 6 | 25-10-2018 Definizione formale del problema Spanning Tree Restrizioni Il protocollo Shout Analisi della correttezza |
| 5 | 22-10-2018 Protocollo HyperFlood: Analisi rigorosa della message complexity Analisi rigorosa del time complexity Introduzione al problema dello Spanning Tree Distribuito e sue applicazioni Il problema Wake-Up sulla Clique: il bound superlineare (senza dimostrazione) |
| 4 | 18-10-2018
LEZIONE 4: 15-10-2018 (2.15 ore) Topologie Sparse e Scalability Sequenze di operazioni di Broadcast: analisi ammortizzata e calcolo di Spanning Tree La struttura Hypercube Il grado, il diametro e le proprieta' di Hypercube L'algoritmo efficiente Hyperflood |
| 3 | 15-10-2018
LEZIONE 3: 15-10-2018 Analisi della sua Message Complexity ed Ideal Time di Flood Un lower bound banale per Broadcast Un lower bound Omega(m) per Broadcast |
| 2 | 11-10-2018
LEZIONE 2: 11-10-2011
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 |
| 1 | 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
|
Materiale didattico
NOTES ON RANDOMIZED DISTRIBUTED PROTOCOLS |  |
GOSSIP MODEL | |
Informazioni
| Anno accademico | 2018-2019 |
|---|---|
| Crediti | 9 |
| Settore | INF/01 |
| Anno | 1 |
| Semestre | 1 |
| Propedeuticità | Nessuna |
Programma
Il corso ADRC per l'a.a. 2018-19 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.
Qui sotto vengono riportati i programmi preliminari per i 2 moduli.
|
Testi di riferimento
N. Santoro: Design and analysis of Distributed Algorithms + Slides e Note del Docente |
Ricevimento studenti
Su appuntamento via email con il Docente:
clementi/guala@mat.uniroma2.it
|
Modalità di esame
prova orale |