Presentazione della candidata e attività svolta




Скачать 24.33 Kb.
НазваниеPresentazione della candidata e attività svolta
Дата04.10.2012
Размер24.33 Kb.
ТипДокументы
Presentazione della candidata Giovanna Melideo

Presentazione della candidata e attività svolta

Studi

La candidata si è laureata con lode in Scienze dell'Informazione nel mese di Luglio 1997 presso l'Università degli Studi di L’Aquila con la tesi ``Apprendimento di serie razionali"; relatore, il Prof. Stefano Varricchio.


Attività di ricerca

L’attività di ricerca si è sviluppata prevalentemente nell’ambito dei sistemi distribuiti. In questo contesto è stato affrontato il problema della caratterizzazione e rappresentazione efficiente della relazione di causalità fra eventi prodotti dall'esecuzione di un programma distribuito asincrono. Lo studio è stato condotto sia da un punto di vista teorico che sperimentale.

Altre attività di ricerca sono state condotte durante gli studi di Dottorato su tematiche di apprendimento automatico e serie formali.

Descrizione della Tesi di Dottorato

La tesi presentata dal candidato si inquadra nel campo dei sistemi distribuiti. In particolare, essa ha per oggetto la caratterizzazione e rappresentazione efficiente della relazione (parziale) di causalità fra eventi prodotti dall'esecuzione di un programma distribuito asincrono.


Rilevare la relazione di causalità fra eventi on-the-fly, cioè concorrentemente all'esecuzione della computazione è fondamentale per la risoluzione di molti problemi come distributed debugging, detection of obsolete data, replicate data management, consistent global state selection. Molti protocolli proposti a questo scopo sono basati su timestamps assegnati agli eventi, che sono valori appartenenti ad un opportuno dominio parzialmente ordinato rispetto ad una relazione <, e sulla propagazione di informazione di controllo sui messaggi (message timestamps) necessaria per aggiornare i timestamps. Tutti questi protocolli, che rappresentano la causalità on-the-fly (cioè la causalità è rappresentata in modo isomorfico), devono risolvere il problema della dimensione dei message timestamps, che potrebbe diventare proibitiva.

Ad esempio, il protocollo dei Vector Clocks, introdotto simultaneamente e indipendentemente da Fidge e Mattern nel 1988, caratterizza la causalità on-the-fly e permette la rilevazione della corretta relazione fra ogni coppia di eventi dal solo confronto dei rispettivi timestamps associando ad ogni evento un vettore di interi di dimensione pari al numero n di processi coinvolti nella computazione. Il principale svantaggio è il loro costo, espresso in termini della dimensione dell'informazione di controllo sui messaggi (un vettore n-dimensionale di interi), che da origine a problemi di scalabilità. Tuttavia, Charron-Bost nel 1991 ha provato che se i timestamps sono strutturati come vettori di interi, allora la dimensione n è necessaria per caratterizzare la causalità on-the-fly.


La tesi affronta il problema della riduzione della dimensione dei message timestamps, affrontando i principali trade-off tra:

1- dimensione dell'informazione locale vs dimensione dei message timestamps;

2- dimensione dei timestamps vs un'approssimazione della relazione di causalità;

3- dimensione dei message timestamps vs ritardo nella rilevazione della relazione di causalità.


In particolare, i risultati della tesi possono essere cosi' riassunti.


Il primo risultato, introdotto nel Capitolo 3 (dopo i capitoli iniziali dedicati all’introduzione dei problemi studiati nella tesi e alla definizione del modello computazionale) propone un framework formale per protocolli di timestamping che caratterizzano la causalità on-the-fly e fornisce lower bounds sulla quantità di informazione (in termini di bits) che deve essere contenuta nei timestamps e message timestamps al fine di rappresentare la causalità in modo isomorfico. Questi bounds rispondono al problema aperto proposto da Swartz e Mattern nel 1994, e confermano il risultato di Charron-Bost sulla necessità di usare n interi se si vuole strutturare i timestamps come vettori. Ragionevoli considerazioni permettono di supporre che il gap tra i lower bounds forniti e gli upper bounds rappresentati dal numero di bits usati dal protocollo dei vector clocks sia in realtà stretto, ossia che non possa esistere nessun protocollo che caratterizzi la causalità on-the-fly associando agli eventi timestamps strutturati in modo diverso dai vector clocks, impiegando un numero minore di bits.


Per affrontare il problema della scalabilità, nel Capitolo 4 è proposto uno schema generale per timestamping protocols, detto k-Dependency Vectors, che esprime un trade-off fra la dimensione dei message timestamps ed il ritardo introdotto nella rilevazione della causalità (detection with delay). In particolare, per k=n si ottiene esattamente il protocollo dei Vector Clocks (ritardo nullo) e per $k=1$ si ottiene il ben noto protocollo delle Dipendenze Dirette, che manifesta il ritardo massimo nella rilevazione delle dipendenze. Inoltre uno studio di simulazione permette di confrontare le performances dei k-dependency vectors con quelle delle Dipendenze Dirette e mostrare che già per k=7 si ha una riduzione del ritardo nella rilevazione di oltre 300 volte in un sistema di 100 processi.


Oltre a proporre protocolli migliori di quelli esistenti, nella tesi si considera il caso più generale in cui solo un sottoinsieme degli eventi è rilevante dal punto di vista dell'applicazione.


Sotto questa ipotesi più generale, nel Capitolo 5 è proposta una suite di implementazioni efficienti dei vector clocks che muove localmente la complessità di gestire vector clocks, riducendo in media la dimensione dei message timestamps a scapito di una informazione locale extra consistente di una matrice n-dimensionale di booleani, in un contesto in cui i canali non devono essere necessariamente fifo. Inoltre, si propone un'estensione dell'implementazione efficiente di Singhal e Kshemkalyani del 1992 (che assumeva l'uso di canali di comunicazione fifo e richiedeva un'informazione di controllo locale extra pari a due vector clocks) al caso in cui non tutti gli eventi sono rilevanti. Sotto l'ipotesi di usare canali di comunicazione fifo, i protocolli proposti risultano da una prova formale più efficienti di quello esteso di Singhal e Kshemkalyani. Questa suite di protocolli esprime il trade-off fra dimensione dell'informazione locale e dimensione dei message timestamps.


Infine, nel Capitolo 6 è fornita una caratterizzazione dell'insieme degli eventi rilevanti che assicura la conservazione delle informazioni di dipendenza fra eventi nel caso in cui si usino message timestamps di dimensione limitata. In particolare si caratterizza la minima dimensione necessaria ad impedire perdite di informazioni rispetto ad una data computazione ed un dato insieme di eventi rilevanti. Si evidenzia un trade-off fra la dimensione dell'informazione da propagare ed il numero di eventi rilevanti. Sebbene la minima dimensione possa essere nota solo se anche la computazione è nota, essa può essere usata per eseguire analisi off-line della computazione.


L’ultimo capitolo è dedicato all’esposizione dei problemi aperti evidenziati dal lavoro di tesi e suggerisce direzioni per eventuali sviluppi.

Formazione nell'ambito del Dottorato

Nell'ambito del programma del dottorato in Informatica ha superato gli esami dei seguenti corsi di dottorato:

  • Impianti di elaborazione (prof. A. Marchetti-Spaccamela)

  • Intelligenza artificiale (prof. L. C. Aiello)

  • Risoluzione approssimata di problemi (prof. G. Ausiello, prof. P. Crescenzi, ing. S. Leonardi)

  • Tecniche algoritmiche avanzate (prof. A. Marchetti-Spaccamela, prof. G. Di Battista)

  • Algoritmi on-line (prof. A. Marchetti-Spaccamela)



Ha frequentato le seguenti scuole:

  • School and Workshop on On-line Algorithms - OLA'98 (Udine, 31 agosto - 5 settembre 1998).


Ha partecipato ai seguenti congressi nazionali:

  • Sixth Italian Conference on Theoretical Computer Science. Prato, Italia. 9--11 Novembre, 1998.

  • Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi. L'Aquila. 13--15 Settembre, 1999.


Ha partecipato ai seguenti congressi internazionali:

  • 9th International Conference on Algorithmic Learning Theory. Otzenhausen, Germania. 8--10 Ottobre, 1998.

  • Final ALCOM-IT Review Meeting. Barcellona. 7--9 Giugno, 1999.

  • 26th International Workshop on Graph-Theoretic Concepts in Computer Science. Konstanz, Germania. 15-17 Giugno, 2000.

  • 7th International Colloquium on Structural Information and Communication Complexity. L'Aquila, Italia. 20-22 Giugno, 2000.


Inoltre, nel periodo di frequenza del corso di Dottorato si è recata in visita presso IRISA - "Institut de Recherche en Informatique et Systemes aleatoires", Rennes, Francia, da Novembre 1999 a Febbraio 2000, per un periodo complessivo di tre mesi, collaborando all' attività di ricerca nell'ambito del progetto ADP (“Distributed Algorithms and Protocols”) con il Prof. Michel Raynal ed il Prof. Jean Michel Hélary.

Pubblicazioni

Atti di convegni

  • G. Melideo, C. Pasquarelli e S. Varricchio: "On the extension of Fine and Wilf's periodicity theorem to linear automata". Proc. of the Sixth Italian Conference on Theoretical Computer Science (ICTCS'98), P.Degano, U.Vaccaro, G.Pirillo Ed.s, World Scientific, 371--383, 1998.

  • G. Melideo e S. Varricchio: "Learning unary output two-tape automata from multiplicity and equivalence queries". Proc. of the 9th International Conference on Algorithmic Learning Theory (ALT'98), Lecture Notes in Artificial Intelligence, Springer Verlag, 1501:371--383, 1998.

  • G. Melideo, C. Pasquarelli e S. Varricchio: "Linear Automata, Rational Series and a Theorem of Fine and Wilf”. Jewels are Forever Contributions on Theoretical Computer Science in Honor of Arto Salomaa, Springer 1799:157--168, 1999.

  • R. Baldoni, A. Marchetti Spaccamela, M. Mechelli and G. Melideo: "Timestamping Algorithms: A Characterization and a Few Properties". Proc. of the European Conference on Parallel Computing (Euro-Par'00), LNCS 1900:609--616, 2000.

  • J. M. Helary and G. Melideo: "Minimal size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization". Proc. of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'00).

  • J.M. Helary, G. Melideo and M. Raynal: "Tracking Causality in Distributed Systems: a Suite of Efficient Protocols". Proc. of the 7th International Colloquium on Structural Information and Communication Complexity (Sirocco'00), Carleton University Press, 181--195, 2000.



Rapporti tecnici

  • [TRI-1] R. Baldoni, M. Mechelli and G. Melideo: "A General Scheme for Dependency Tracking in Distributed Computations". Technical Report n. 17-99, Dipartimento di Informatica e Sistemistica, Roma, 1999.

  • [TRI-2] R. Baldoni, A. Marchetti-Spaccamela, M. Mechelli and G. Melideo: “Necessary Conditions for Characterizing Causality in Distributed Computations”. ". Technical Report n. 28-99, Dipartimento di Informatica e Sistemistica, Roma, 1999.

  • [TRI-3] J.M. Helary, G. Melideo and M. Raynal: "Tracking Causality in Distributed Systems: a Suite of Efficient Protocols". Publication Interne n. 1300, IRISA. Rennes, France, 2000

  • [TRI-4] J.M. Helary and G. Melideo: "Minimal size of piggybacked information for tracking causality: a graph-based characterization". Publication Interne n. 1301, IRISA. Rennes, France, 2000.


Lavori proposti per la pubblicazione su rivista

  • R. Baldoni, M. Mechelli and G. Melideo: "A General Scheme for Dependency Tracking in Distributed Computations". Proposto per pubblicazione su IEEE Transactions on Software Engineering (TSE).

  • J.M. Helary, M. Raynal, G. Melideo and R.Baldoni: "Efficient Causality-Tracking Timestamping". Proposto per pubblicazione su IEEE Transactions on Knowledge and Data Engineering (TKDE).

  • R. Baldoni and G. Melideo: "A Lower Bound on the Minimal Information to Encode Timestamps in Distributed Computations". Proposto per pubblicazione su Information Processing Letters.


Lavori proposti a conferenza

  • R. Baldoni and G. Melideo.:"k-Dependency Vectors: A Scalable Causality-Tracking Protocol". Proposto alla International Conference on Distributed Computing Systems (ICDCS 2000).

Похожие:

Presentazione della candidata e attività svolta iconAutorità per le Garanzie nelle Comunicazioni Relazione annuale sull’attività svolta e sui programmi di lavoro. Presentazione del Presidente Corrado Calabrò |

Presentazione della candidata e attività svolta iconAccademia della Crusca : la storia, le attività, l'organizzazione. Firenze : [s n.], 2004. 12 p ILL color.; 24 cm

Presentazione della candidata e attività svolta iconDella learning community del Centro Studi di Terapia della Gestalt

Presentazione della candidata e attività svolta iconPresentazione generale del progetto

Presentazione della candidata e attività svolta icon«Ecco ora IL momento favorevole» (2Cor 6,2)
«collaboratori della gioia», che ci è chiesta di testimoniare nell’oggi della storia, I laici di Azione Cattolica intendono assumere...
Presentazione della candidata e attività svolta iconБиблиография умберто эко в италии и в россии дамиано ребеккини
О литературе” (Sulla letteratura, 2002), исследовании о переводе “Сказать почти то же самое” (Dire quasi la stessa cosa, 2003), иллюстрированном...
Presentazione della candidata e attività svolta iconSettore “Attività culturali e turistiche”

Presentazione della candidata e attività svolta iconObiettivo/i educativi formativi complessivi dell’attività formativa

Presentazione della candidata e attività svolta iconObiettivo nazionale/ regionale di Educazione Continua in Medicina a cui fa riferimento l’attività

Presentazione della candidata e attività svolta iconObiettivo nazionale/ regionale di Educazione Continua in Medicina a cui fa riferimento l’attività

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница