|
Calcolo distribuitoIl calcolo distribuito è un campo dell'informatica che studia i sistemi distribuiti, ovvero sistemi che consistono in numerosi computer autonomi che interagiscono/comunicano tra loro attraverso una rete al fine di raggiungere un obiettivo comune (un software eseguito in un sistema distribuito è detto programma distribuito, e la programmazione distribuita è il processo di scrittura di tali software). Un tipico esempio di applicazione del calcolo distribuito è l'uso di sistemi distribuiti per risolvere problemi computazionali di una certa complessità: in tale ambito un problema è suddiviso a sua volta in molti sottocompiti ognuno dei quali è risolto da un singolo computer. StoriaL'uso di processi concorrenti che comunicano con il passaggio di messaggi ha le sue radici nelle architetture di sistemi operativi studiati negli anni 1960. Il primo sistema distribuito diffuso è stato il local-area network come Ethernet che è stato inventato negli anni 1970. ARPANET, il predecessore di Internet, è stato introdotto nei tardi anni 1960 e l'ARPANET e-mail è stata inventata nei primi anni 1970. La posta elettronica divenne l'applicazione di maggior successo di ARPANET ed è probabilmente il primo esempio di applicazione distribuita su larga scala. In aggiunta ad ARPANET ed al suo successore Internet, altre prime reti di computer in tutto il mondo sono state Usenet e Fidonet dagli anni 1980, entrambe le quali sono state utilizzate per sostenere sistemi distribuiti di discussione. Lo studio del calcolo distribuito divenne propriamente branca dell'informatica nei tardi anni 1970 e primi 1980. La prima conferenza nel campo “Simposio dei principi del calcolo distribuito”, risale al 1980 e la sua controparte europea “Simposio internazionale sul calcolo distribuito” fu per la prima volta tenuta nel 1985. DescrizioneLa parola distribuito in termini come “sistema distribuito”, “programmazione distribuita”, e “algoritmo distribuito” originariamente si riferiva a reti di computer dove singoli computer erano fisicamente distribuiti in certe aree geografiche. I termini sono oggi utilizzati in un più ampio senso, anche quando si riferiscono a processi autonomi che sono eseguiti sullo stesso computer fisico ed interagiscono tra loro tramite il passaggio di messaggi. Mentre non c'è una singola definizione di sistema distribuito, le seguenti proprietà sono comunemente usate:
In questa trattazione, le entità computazionali verranno chiamate computer o nodi. Un sistema distribuito può avere un obiettivo comune, come risolvere un grande problema computazionale. Alternativamente, ogni computer può avere il proprio utente con bisogni individuali, e lo scopo del sistema distribuito è di coordinare l'uso delle risorse condivise o fornire servizi di comunicazione all'utente. Altre tipiche proprietà dei sistemi distribuiti sono le seguenti:
Calcolo parallelo o distribuito?I termini “calcolo concorrente”, “calcolo parallelo”, e “calcolo distribuito” hanno molte sovrapposizioni, e non esiste nessuna chiara distinzione tra di loro. Lo stesso sistema può essere caratterizzato sia come “parallelo” sia come “distribuito”; i processori in un sistema distribuito tipico elaborano concorrentemente, in parallelo. Il calcolo parallelo può esser visto come una forma particolare strettamente unita al calcolo distribuito, ed il calcolo distribuito può esser visto come una forma particolare strettamente unita al calcolo parallelo. Tuttavia è possibile classificare sistemi concorrenti come “paralleli” o “distribuiti” tramite i seguenti criteri:
L'immagine a destra illustra la differenza tra sistemi distribuiti e sistemi paralleli.  La figura (a) è la vista schematica di un tipico sistema distribuito: il sistema è rappresentato come un grafo in cui ogni nodo (vertex) è un computer ed ogni riga (linea tra due nodi) è un collegamento di comunicazione. La figura (b) mostra lo stesso sistema distribuito più in dettaglio: ogni computer ha la propria memoria locale, e le informazioni possono essere scambiate solamente grazie al passaggio di messaggi da un nodo ad un altro usando i nodi di comunicazione disponibili. La figura (c) mostra un sistema parallelo in cui ogni processore ha accesso diretto alla memoria condivisa. La situazione è ulteriormente complicata dai tradizionali usi dei termini algoritmo parallelo e distribuito che non corrispondono alla definizione di sistemi paralleli e distribuiti. Tuttavia, come regola generale, il calcolo parallelo ad alte prestazioni con memoria condivisa multiprocessore usa algoritmi paralleli mentre per la coordinazione di sistemi distribuiti su larga scala si usano algoritmi distribuiti. Fondamenti teoriciModelliMolti compiti che vorremmo automatizzare usando il computer sono di tipo domanda-risposta: facciamo una domanda ed il computer dovrebbe dare la risposta. In informatica questi compiti sono chiamati problemi computazionali. Formalmente, un problema computazionale consiste in istanze, unitamente ad una soluzione per ogni istanza. Le istanze sono domande che possiamo porre e le soluzioni sono le risposte desiderate a queste domande. L'informatica cerca di capire quali problemi computazionali si possono risolvere usando un computer (teoria della computabilità) e quanto efficientemente (teoria della complessità computazionale). Tradizionalmente è come dire che un problema può essere risolto usando un computer se possiamo scrivere un algoritmo che produce una soluzione corretta per qualsiasi istanza data. Un tale algoritmo può essere implementato come un software che viene eseguito su un generico computer: il programma legge l'istanza del problema da un input, esegue dei calcoli, e produce la soluzione come output. Formalismi come macchine ad accesso casuale o macchine universali di Turing possono essere usati come modelli astratti di un generico computer sequenziale che esegue un tale algoritmo. Il campo del calcolo concorrente e distribuito studia questioni simili nel caso di molti computer, o un computer che esegue una rete di processi interagenti: quali problemi computazionali possono essere risolti in una tale rete e con quale efficienza? Tuttavia non è così evidente cosa significhi risolvere un problema nel caso di sistemi concorrenti o distribuiti: per esempio, qual è il compito del progettista dell'algoritmo e qual è l'equivalente concorrente e/o distribuito per un generico computer? La discussione sotto si concentra sul caso di molti computer, ma in ogni caso molte di queste questioni sono le stesse per i processi concorrenti eseguiti su un singolo computer. Ci sono tre casi comunemente utilizzati: Algoritmi paralleli in modelli a memoria condivisa
Algoritmi paralleli nel modello a passaggio di messaggi
Algoritmi distribuiti nel modello a passaggio di messaggi
Nel caso di algoritmi distribuiti i problemi computazionali sono tipicamente legati ai grafi. Spesso il grafo che descrive la struttura della rete di computer è l'istanza del problema. Questo caso è illustrato nel seguente esempio. Un esempioSi consideri il problema computazionale di trovare una colorazione di un grafo G dato. Diversi settori potrebbero seguire i seguenti approcci: Algoritmi centralizzati
Algoritmi paralleli
Algoritmi distribuiti
Mentre il campo degli algoritmi paralleli ha una caratterizzazione diversa rispetto al campo degli algoritmi distribuiti, ci sono diverse interazioni tra i due campi. Per esempio, l'algoritmo Cole–Vishkin per la colorazione dei grafi è stato originariamente presentato come un algoritmo parallelo, ma la stessa tecnica può essere usata direttamente come algoritmo distribuito. Inoltre, un algoritmo parallelo può essere implementato sia in un sistema parallelo (usando memoria condivisa) che in un sistema distribuito (usando il passaggio di messaggi). Il confine tradizionale tra algoritmi paralleli e distribuiti (scegliere una rete adeguata vs esecuzione in ogni rete) non è come il confine tra sistemi paralleli e distribuiti (memoria condivisa vs passaggio di messaggi). Misure di complessitàUn algoritmo centralizzato è efficiente se non richiede molto tempo (numero di passi computazionali) o spazio (ammontare di memoria). Questa misura di complessità danno luogo a classi di complessità come P (problemi decisionali risolvibili in tempo polinomiale) e PSPACE (problemi decisionali risolvibili in spazio polinomiale). Negli algoritmi paralleli un'altra risorsa in aggiunta a tempo e spazio è il numero di computer. Infatti, spesso c'è un bilanciamento tra il tempo d'esecuzione ed il numero di computer: il problema può essere risolto velocemente se ci sono più computer che elaborano in parallelo. Se un problema decisionale può essere risolto in tempo polilogaritmico usando un numero polinomiale di processori allora il problema si dice che sia in classe NC. La classe NC si può definire altrettanto bene usando il formalismo PRAM o i circuiti booleani. Le macchine PRAM possono simulare efficientemente circuiti booleani e viceversa. Nelle analisi degli algoritmi distribuiti è data solitamente più attenzione alla comunicazione delle operazioni che ai passi computazionali. Forse il più semplice modello di calcolo distribuito è un sistema sincrono dove tutti i nodi operano in blocco. Durante ogni turno di comunicazione, tutti i nodi in parallelo (1) ricevono gli ultimi messaggi dai suoi vicini, (2) effettuano arbitrari calcoli locali e (3) mandano nuovi messaggi ai loro vicini. In tali sistemi, una misura di complessità centrale è il numero di turni di comunicazione sincroni richiesti per completare il compito. Questa misura di complessità è strettamente collegata al diametro della rete. Sia D il diametro della rete. Da un lato, qualsiasi problema computazionale può essere risolto banalmente in un sistema sincrono distribuito in approssimativamente 2D turni di comunicazione: semplicemente per raccogliere tutte le informazioni in un unico punto (D turni), risolvere il problema, ed informare ogni nodo circa la soluzione (D turni). Dall'altro lato, se il tempo d'esecuzione dell'algoritmo è molto inferiore a D turni di comunicazione, allora i nodi della rete devono produrre i loro risultati senza avere la possibilità di ottenere informazioni circa le parti lontane della rete. In altre parole, i nodi devono prendere decisioni a livello globale basate su informazioni che sono disponibili nei loro paraggi. Molti algoritmi distribuiti sono conosciuti con il tempo d'esecuzione molto più piccolo di D turni, e la comprensione di quali problemi possono essere risolti da tali algoritmi è uno degli obiettivi centrali della ricerca di questo campo. Un'altra misura comunemente usata è il numero totale di bit trasmessi nella rete (complessità di comunicazione). Altri problemiI problemi computazionali generalmente consistono nel porre una domanda ad un computer (o ad un sistema distribuito), che elabora la domanda per un po' ed infine produce una risposta e si ferma. Tuttavia, ci sono anche problemi in cui noi vogliamo che il sistema non si fermi mai. Esempi di tali problemi includono il problema dei filosofi a cena ed altri simili problemi a mutua esclusione. In questi problemi il sistema distribuito dovrebbe coordinare costantemente l'uso delle risorse condivise senza la presenza di conflitti o stallo. Ci sono anche fondamentali sfide che sono uniche per il calcolo distribuito. Il primo esempio è la sfida riguardante il fault-tolerance. Esempi di problemi connessi includono problemi di consenso, Byzantine fault tolerance, e auto stabilizzazione. Molte ricerche sono anche focalizzate sulla comprensione della natura asincrona dei sistemi distribuiti:
Proprietà dei sistemi distribuitiFinora l'attenzione si è concentrata sulla progettazione di un sistema distribuito che risolve un dato problema. Un problema di ricerca complementare è studiare le proprietà di un dato sistema distribuito. Il problema della terminazione è un esempio analogo al campo della computazione centralizzata: ci è dato un software ed il compito è decidere se si ferma o va per sempre. Il problema della terminazione è indecidibile nel caso generico, e naturalmente capire il comportamento di una rete di computer è almeno altrettanto difficile come capire il comportamento di un computer. Tuttavia, ci sono molti interessanti casi particolari che sono decidibili. In particolare, è possibile ragionare sul comportamento di una rete di macchine a stati finiti. Un esempio è dire se una determinata rete interagente di macchine a stati finiti (asincrona e non deterministica) può finire in una situazione di stallo. Questo problema è PSPACE completo, è decidibile, ma è improbabile che ci sia un algoritmo efficiente (centralizzato, parallelo o distribuito) che risolve il problema nel caso di una grande rete. ArchitetturePer il calcolo distribuito sono usate varie architetture hardware e software. A basso livello è necessario interconnettere CPU multiple con una sorta di rete, indipendentemente dal fatto che la rete sia stampata su un circuito o composta da dispositivi e cavi. Ad alto livello è necessario invece interconnettere i processi eseguiti su quelle CPU con una sorta di sistema di comunicazione. La programmazione distribuita di solito cade in uno dei numerosi elementi architettonici di base o categorie: Client-server, architettura 3-tier, architettura N-tier, oggetti distribuiti, loose coupling, tight coupling.
Un altro aspetto basilare delle architetture di calcolo distribuito è il metodo di comunicazione ed i lavori di coordinamento tra processi concorrenti. Tramite vari protocolli di scambio messaggi, i processi possono comunicare direttamente con un altro, tipicamente con relazione master/slave. Alternativamente, un'architettura con database centrale potrebbe rendere il calcolo distribuito eseguito senza nessuna forma di comunicazione inter processo, utilizzando un database condiviso. ApplicazioniCi sono due principali ragioni per usare sistemi distribuiti ed il calcolo distribuito. Primo, la natura dell'applicazione può richiedere l'uso di un network di comunicazione che collega più computer. Per esempio, i dati sono prodotti in una certa locazione fisica e servono in un'altra locazione. Secondo, sono molti i casi in cui l'uso di un singolo computer sarebbe possibile in linea di principio, ma l'uso di un sistema distribuito è vantaggioso per motivi pratici. Per esempio, può essere più efficiente ottenere il livello prestazionale desiderato usando un cluster di diversi computer di fascia bassa, in confronto con un sistema non distribuito e non ci sono single point of failure. Inoltre, un sistema distribuito può essere più facile da espandere e dirigere confronto ad un sistema uniprocessore monolitico. Esempi di sistemi distribuiti ed applicazioni di calcolo distribuito sono inclusi di seguito:
NoteLibri
Articoli
Siti web
Voci correlate
Altri progetti
Collegamenti esterni
|
