OBIETTIVI DEL CORSO

In questo corso è prevista l'acquisizione da parte degli studenti di elementi di base relativi agli ambienti distribuiti. Si vogliono rendere familiari agli studenti problematiche, tecniche e metodologie di ricerca proprie degli ambienti distribuiti.

ESAME

  L'esame consiste in un colloquio orale. Data e ora possono essere concordate con il docente. 

 PROGRAMMA 

   I. Introduzione agli Ambienti Distribuiti: Entità, Eventi, Azioni e Comunicazioni. Assiomi e Restrizioni.
  II. Stati, Eventi e Configurazioni. Problemi e Soluzioni. Terminazione e Correttezza. Costo e complessità degli algoritmi distribuiti.
 III. Problema del Broadcast. Algoritmo Flooding e sua complessità. Lower bounds. Broadcast su alberi e grafi completi, Topologia dell'ipercubo dimensionale. Broadcasting sugli ipercubi. Algoritmo HyperFlood e sua correttezza. Prova dell'assenza di cicli in Hk(x).
  IV. Problema del Wake-Up. Wake-Up su ipercubi, alberi e grafi completi. Lower bound per il Wake-Up nel caso di grafi completi e Id unici. Tecnica dell'avversario.
   V. Problema dell'attraversamento. Algoritmo DF_Traversal. Costi computazionali. Miglioramenti: DF+, DF++. Traversal su alberi, ring e grafi completi
  VI. Costruzione di uno Spanning Tree. Protocollo Shout. Correttezza, costi computazionali e miglioramento del protocollo Shout.
 VII. Esplorazione di un grafo anonimo tramite automa a stati finiti. Orientamento locale ad-hoc per la costruzione di uno Spanning Tree. Regola della mano destra. Correttezza algoritmo di esplorazione e possibili miglioramenti.
VIII. Spanning tree con iniziatori multipli. Spanning Tree con Identificatori unici. Protocollo MultiShout.
IX. Tecnica della saturazione e relativi costi. Ricerca del minimo, dell'eccentricità e del centro tramite saturazione.
X. Leader Election: Risultati di impossibilità, topologia ad albero e ring. Protocollo AllTheWay, Protocollo AsFar, Protocollo ControlDis. Topologia a griglia e grafi completi.
  XI. Sistemi Sincroni. Protocollo Speed. Protocollo TwoBits.
 XII. Problema del Gathering. Modello Look-Compute-Move e Multiplicity detection. Gathering su ring, alberi e griglie.
XIII. Modelli di computazione: ASYNC, SSYNC, FSYNC, Robot con luci;

TESTI CONSIGLIATI

1. N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons
   

ARTICOLI SCIENTIFICI CORRELATI

1. D. Ilcinkas: "Setting Port Numbers for Fast Graph Exploration". Theoretical Computer Science, vol. 401(1-3): 236-242, 2008
   
2. R. Klasing, E. Markou, A. Pelc: "Gathering Asynchronous Oblivious Mobile Robots in a Ring", Theoretical Computer Science, vol. 390(1), pp. 27-39, 2008
   
3. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita, “Autonomous mobile robots with lights,” Theoretical Computer Science, vol. 609: 171-184, 2016