Algoritmi distribuiti e reti complesse

ESAME DEL 14/06

Si informano gli studenti interessati che nell'appello in oggetto, la parte Game Theory non verra' verificata:   chi deve ancora sostenere tale parte e' invitato a contattare via email il dr Guala' per fissare una data.

esito ESONERO

RISULTATI ESONERO   ADRC (I PARTE - Clementi) del 07/01/16

·      Alessandro (m. 0234365):   21/30

·      Simone V.  (m. 0225306):  30/30 e Lode

·      Federico F. (m. 0225303): 28/30

·      Christian S. (m. 0225360):  21/30

·      Alessandro B. (m. 0225305): 30/30 e Lode

·      Damiano R. (m. 0225359):  30/30

Nota. Gli studenti che non compaiono sulla lista e che hanno consegnato lo scritto, sono quelli che  hanno riportato una votazione   insufficiente.

ESONERO PARTE I

Il giorno 07/01/16 alle ore 14.30 IN AULA 7, si terra' l'esonero scritto della prima parte (Clementi) del corso ADRC. La prova durera' due ore.

Gli interessati sono pregati di inviare una email di prenotazione a

clementi@mat.uniroma2.it

Le domande riguarderanno esclusivamente gli argomenti trattati a lezione e presenti sul libro di testo e/o nel materiale messo a disposizione su questo sito.

Seminario Vito Trianni: articoli scientifici

Per gli studenti, credo che questi articoli possano essere sufficienti. Come dicevo,
il main text dovrebbe essere fruibile da tutti, mentre il supplementary material potrebbe essere un po’ ostico.
1. Reina, A., Valentini, G., Fernández-Oto, C., Dorigo, M., & Trianni, V. (2015). A
Design Pattern for Decentralised Decision Making. PLoS ONE, 10(10), e0140950–18.
http://doi.org/10.1371/journal.pone.0140950
2. Seeley, T. D., Visscher, P. K., Schlegel, T., Hogan, P. M., Franks, N. R., &
Marshall, J. A. R. (2012). Stop Signals Provide Cross Inhibition in Collective
Decision-Making by Honeybee Swarms. Science, 335(6064), 108–111.
http://doi.org/10.1126/science.1210361

Sempre per gli studenti, qualcosa di più divulgativo (anche in italiano):
3. Marshall, J., & Franks, N. R. (2009). Colony-level cognition. Current Biology :
CB, 19(10), R395.
4. Vito Trianni, Elio Tuci, Swarm Cognition: collective behaviours,
self-organisation and cognitive processes, in "Sistemi intelligenti" 2/2011, pp.
329-336, doi: 10.1422/35359 - https://www.rivisteweb.it/doi/10.1422/35359

LEZIONE - SEMINARIO ADRC

ADRC: Lezione del 2 novembre

La lezione in oggetto non avra' luogo.

IL modello distributo GOSSIP ed Uniform GOSSIP.

Il problema del consensus e del plurality consensus binario

La dinamica del 3-majority.

Analisi della catena di Markov del processo e determinazione

del tempo di completamento medio.

Introduzione ai protocolli randomizzati. Valor medio di della v.a. **tempo**.

Il protocollo di broadcast randomizzato BGI su reti layered.

Gap esponenziale tra broadcast  deterministico e randomizzato.

Reti wireless.

Il protocollo di broadcast deterministico basato sulle famiglie selettive.

Correttezza ed analisi del tempo di completamento

Conoscenza dei parametri n,D, d

Il problema del Broadcast su reti wireless.

l'algoritmo round robin.

analisi e correttezza.

Il concetto di famiglie selettive.

Elezione di un Leader in un anello: 

La Stage technique ed un protocollo con communication cost n \log n

Elezione in una mesh.

IL modello wireless: introduzione, motivazioni, caratteristiche.

Il problema della collisione.

Il problema del Broadcast.

- Elezione di un Leader in un anello:

Algoritmi all-the-way e versione migliorata con communication cost n^2.

Computationi distribuite su alberi:

La tecnica della Saturazione per il calcolo dell'eccentricita'

Calcolo del centro di un albero

Calcolo del ranking di un nodo 

Computazioni Distribuiti su Alberi.

La tecnica della Saturazione

Calcolo del minimo

IL problema dello spanning tree distribuito:

il protocollo shout+ ed il miglioramento della msg complexity

Arbitrarieta' della soluzione ottenuta rispetto al diametro

Risultato di impossibilita' se ci sono piu  initiator con dimostrazione

Token traversal:  protocollo sequenziale e protocollo con parte parallela

dimostrazione di correttezza e analisi della msg complexity e del tempo

IL problema dello spanning tree distribuito

conoscenza locale della soluzione

il protocollo Shout

Correttezza e message complexity

IL problema del Wake-UP su topologie specifiche

IL caso del grafo completo.

Il lower bound \Omega(n log n)

Lezione-Seminario

(Vito Trianni): A Design Pattern for Decentralised Decision Making

Lezione del Dr. Guala':

Una prima introduzione ai modelli distribuiti con agenti egoistici

e la teoria dei giochi.

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

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

Protocolli per il Broadcast su grafi generali: FLOOD

Analisi del FLOOD:

correttezza,

msg complexity,

completion time

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

Introduzione al calcolo distribuito

Esempi di decisioni locali

Motivazioni generali 

descrizione del corso, del materiale didattico, delle propedeudicita', e delle prove

Il corso 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.
 
Nella seconda parte di 3 cfu, 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.
 
Gli argomenti fondamentali trattati durante il corso sono i seguenti:
 
Parte I:  Algoritmi Distribuiti (6 CFU)
- 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
 
Parte II (3 CFU)
 
**** - da inserire *****