Il tema di ricerca affrontato ha riguardato il riconoscimento della topologia di un grafo rappresentante la rete di un sistema distribuito. Il problema consiste nel richiedere a ogni nodo di una rete anonima di produrre deterministicamente l’immagine di un grafo che sia una copia etichettata isomorfa al grafo che rappresenta la rete. Il problema è inaffrontabile senza che ai nodi sia assegnata a priori qualche informazione sulla struttura. Questo compito è assolto da un oracolo che, conoscendo l’intera rete, può assegnare ai singoli nodi una parte d’informazione, codificata tramite una stringa di bits. Per ricostruire la copia del grafo, i nodi possono (ovvero devono) usare le informazioni ad essi assegnate. Il tempo che occorre per ricostruire la tipologia è dato dal numero di rounds di comunicazione richiesto dai nodi e la dimensione dell’advice (informazione pre-assegnata ai nodi) é la massima lunghezza delle stringhe a loro assegnate. Il numero di messaggi che ogni nodo in ogni singolo round trasmette ai suoi vicini è il terzo valore considerato per calcolare la bontà della soluzione di un problema di riconoscimento di topologia in un sistema distribuito. Tipicamente l’ottimizzazione di una di queste misure comporta il peggioramento delle altre. E’ fondamentale, pertanto, trovare algoritmi che risolvano il problema raggiungendo un giusto punto di equilibrio (tradeoff) fra le misure sopra presentate.

Riconoscimento della topologia di un grafo rappresentante la rete di un sistema distribuito / A., Pelc; Petreschi, Rossella. - (2012).

Riconoscimento della topologia di un grafo rappresentante la rete di un sistema distribuito

PETRESCHI, Rossella
2012

Abstract

Il tema di ricerca affrontato ha riguardato il riconoscimento della topologia di un grafo rappresentante la rete di un sistema distribuito. Il problema consiste nel richiedere a ogni nodo di una rete anonima di produrre deterministicamente l’immagine di un grafo che sia una copia etichettata isomorfa al grafo che rappresenta la rete. Il problema è inaffrontabile senza che ai nodi sia assegnata a priori qualche informazione sulla struttura. Questo compito è assolto da un oracolo che, conoscendo l’intera rete, può assegnare ai singoli nodi una parte d’informazione, codificata tramite una stringa di bits. Per ricostruire la copia del grafo, i nodi possono (ovvero devono) usare le informazioni ad essi assegnate. Il tempo che occorre per ricostruire la tipologia è dato dal numero di rounds di comunicazione richiesto dai nodi e la dimensione dell’advice (informazione pre-assegnata ai nodi) é la massima lunghezza delle stringhe a loro assegnate. Il numero di messaggi che ogni nodo in ogni singolo round trasmette ai suoi vicini è il terzo valore considerato per calcolare la bontà della soluzione di un problema di riconoscimento di topologia in un sistema distribuito. Tipicamente l’ottimizzazione di una di queste misure comporta il peggioramento delle altre. E’ fondamentale, pertanto, trovare algoritmi che risolvano il problema raggiungendo un giusto punto di equilibrio (tradeoff) fra le misure sopra presentate.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/556348
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact