UN SEMPLICE ESEMPIO DI PROTOCOLLO AUTO-STABILIZZANTE : " SELF-STABILIZING TOKEN RING "
Nel 1974 Edsger W. Dijkstra introdusse la nozione di "auto-stabilizazione" presentando molti algoritmi "auto-stabilizzanti". Nove anni dopo, nel suo discorso richiesto al PODC, Leslie Lamport mise in evidenza questo scritto, poco conosciuto, come "una pietra miliare nel lavoro sulla tolleranza ai guasti".
Gli attuali sistemi di "auto-stabilizzazione" mostrano una notevole capacità di auto-organizzazione. Iniziando da un punto in cui ogni componente è in uno stato arbitrario, il sistema converge inevitabilmente in un legale stato di funzionamento e rimane corretto da lì in poi.
Gli algoritmi classici sul fault-tolerance seguono un approccio pessimistico, diffidando di tutte le informazioni ricevute e facendo precedere tutti i passi, che un processo compie, da un numero sufficiente di test in maniera da garantirne la validità.
Viceversa gli algoritmi auto-stabilizzanti seguono un approccio ottimistico, nel senso che i processi corretti possono comportarsi in maniera inconsistente, ma devono tornare ad un comportamento corretto, al termine di quello incorretto, entro un tempo finito.
Questo vuol dire che gli algoritmi auto-stabilizzanti si proteggono da fallimenti temporanei. L’approccio auto-stabilizzante, piuttosto che considerare tutti i processi come fallibili, assume che tutti i processi operano correttamente ma che un qualsiasi stato può essere "corrotto" arbitrariamente durante un errore temporaneo.
La necessità di una vera e propria inizializzazione dell’algoritmo è eliminata, poiché partendo da un qualsiasi stato "corrotto" l’algoritmo auto-stabilizzante deve alla fine comportarsi correttamente.
Affrontando questo argomento sono necessarie delle domande preliminari :
Durante lo sviluppo di questa tesina si è cercato di dare una risposta alle domande sopracitate.
La tesina è suddivisa in quattro capitoli; nel primo si introduce il concetto di auto-stabilizzazione e viene descritto un semplice protocollo auto-stabilizzante (self-stabilizing token ring), il secondo parla del problema della mutua esclusione esplorando tre possibili algoritmi, nel terzo capitolo si esplora la differenza tra stabilizzazione e pseudo-stabilizzazione, infine nel quarto capitolo si affronta il tema dell’auto-stabilizzazione nel contesto del passaggio dei messaggi.
1.2 AUTO-STABILIZZAZIONE SECONDO DIJKSTRA
Come accennato nell'introduzione nel 1974 Dijkstra introdusse nella computer science la nozione di auto-stabilizzazione nel contesto dei sistemi distribuiti. Egli definì un sistema come auto-stabilizzante quando "partendo da uno stato iniziale viene garantito il suo arrivo in uno stato legittimo con un numero finito di passi".
Un sistema che non è auto-stabilizzante può rimanere in uno stato illegittimo per sempre. La nozione di Dijkstra di auto-stabilizzazione, che originariamente aveva un range limitato nelle applicazioni, sta ora cercando di fornire un approccio formale al problema del fault-tolerance nei sistemi distribuiti.
1.3 UN SEMPLICE ESEMPIO DI PROTOCOLLO AUTO-STABILIZZANTE : " SELF-STABILIZING TOKEN RING "
In questo paragrafo viene descritto il progetto di un protocollo "fault-tolerance token ring" che può rimpiazzare un già esistente protocollo token ring come l'IBM token ring oppure l'FDDI.
Per descrivere tale protocollo si fa riferimento ad una LAN (Local Area Network) con una topologia ad anello, costituita cioè da un certo numero di DTE (Data Terminal Equipment) connessi in catena tra loro. Ogni DTE è, nel contesto delle reti, una macchina vista come un nodo, pertanto il nostro anello è costituito da diversi nodi, in cui ognuno di essi è dotato di un contatore. Tra tutti i nodi ne esiste uno principale chiamato monitor. Quando il token viene fatto passare dentro l’anello, i contatori dei nodi diventano uguali a quello del nodo più alto; alla fine il token torna al nodo principale che incrementa il suo contatore e inizia un nuovo ciclo.
La figura 1 mostra un token ring con 3 nodi che fornisce un semplice esempio dell’ approccio utilizzato in questo protocollo. Per ogni nodo , viene assegnato un valore al corrispondente contatore; nel nostro esempio il monitor viene inizialmente posto ad essere uguale a 7 e i rimanenti nodi uguali a 6.
Quando il token è passato dentro l'anello , il contatore del nodo che riceve il token viene posto ad essere uguale a quello del monitor (7). Alla fine il token ritorna al monitor, che incrementa il suo contatore a 8 e inizia un nuovo ciclo.
I contatori permettono ai nodi di trasmettere periodicamente i token perché il valore del contatore consente al nodo successivo di eliminare i duplicati. Per esempio, se nella seconda configurazione della figura 1, il monitor spedisce un secondo token al nodo successivo(in senso orario), egli lo respingerà perché il contatore di tale nodo (7) è uguale al contatore del monitor (anch’egli 7).
La cosa più interessante è che persino quando i valori dei contatori nello stato iniziale sono arbitrari l'anello ritorna presto ad un buon funzionamento (questo può essere verificato analizzando direttamente il protocollo). Questa proprietà è chiamata auto-stabilizzazione e ciò assicura che l'anello è altamente tollerante agli errori.
In questo progetto ci sono ancora un numero di dettagli, come le priorità ed altre caratteristiche, che devono ancora essere calcolate; naturalmente il progetto globale includerebbe la realizzazione di questi dettagli per fornire tutte le caratteristiche trovate nel protocollo token ring IBM 802.1 .