Il 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.
Storia L'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.
Descrizione La 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: Ci sono molte entità computazionali autonome, ognuna delle quali ha la propria memoria locale. Le entità comunicano tra loro con il passaggio di messaggi.
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: Il sistema tollera guasti a singoli computer. La struttura del sistema (topologia di rete, latenza di rete, numero di computer) non è conosciuta in anticipo, il sistema può consistere in differenti tipi di computer e collegamenti di rete, e può cambiare durante l'esecuzione del programma distribuito. Ogni computer ha solamente una vista limitata ed incompleta del sistema. Ogni computer conosce solo una parte dell'input.
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: Nel calcolo parallelo tutti i processori devono accedere ad una memoria condivisa. La memoria condivisa può essere usata per lo scambio di informazioni tra i processori. Nel calcolo distribuito ogni processore ha la propria memoria privata (memoria distribuita). Le informazioni sono scambiate grazie al passaggio di messaggi tra i processori.
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 teorici Modelli Molti 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 Tutti i computer hanno accesso alla memoria condivisa. Il progettista dell'algoritmo sceglie il programma eseguito da ogni computer. Un modello teorico è la macchina ad accesso parallelo casuale (PRAM). Tuttavia, il classico modello PRAM assume accesso sincrono alla memoria condivisa. Un modello che è più vicino al comportamento delle macchine multiprocessore del mondo reale prende in considerazione l'uso di istruzioni macchina come Compare-and-swap (CAS) che è quello della memoria asincrona condivisa.
Algoritmi paralleli nel modello a passaggio di messaggi Il progettista dell'algoritmo sceglie la struttura della rete nonché il programma eseguito da ogni computer Sono usati modelli come circuiti booleani e reti di ordinamento. Un circuito booleano può esser visto come una rete di computer: ogni gate è un computer che esegue un programma estremamente semplice. Similmente, anche una rete di ordinamento può esser vista come una rete di computer: ogni comparatore è un computer.
Algoritmi distribuiti nel modello a passaggio di messaggi Il progettista dell'algoritmo sceglie solamente il programma. Tutti i computer eseguono lo stesso programma. Il sistema deve funzionare correttamente a prescindere dalla struttura della rete. Un modello comunemente usato è il grafo con una macchina a stati finiti per nodo. 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 esempio Si consideri il problema computazionale di trovare una colorazione di un grafo G dato. Diversi settori potrebbero seguire i seguenti approcci:
Algoritmi centralizzati Il grafo G è codificato come una stringa, e la stringa è data come input ad un computer. Il programma trova una colorazione del grafo, codifica la colorazione come una stringa e dà il risultato in output.
Algoritmi paralleli Ancora, il grafo G è codificato come una stringa. Tuttavia più computer possono accedere alla stessa stringa in parallelo. Ogni computer si può focalizzare su una parte del grafo e produrre una colorazione per quella parte. L'attenzione principale è sul calcolo ad alte prestazioni che sfrutta la potenza di elaborazione di più computer in parallelo.
Algoritmi distribuiti Il grafo G è la struttura della rete di computer. C'è un computer per ogni nodo di G e un collegamento per ogni estremità di G. Inizialmente ogni computer conosce solamente i suoi immediati vicini nel grafo G; i computer devono scambiarsi messaggi tra loro per scoprire di più della struttura di G. Ogni computer deve produrre il proprio colore come output. L'attenzione principale è sul coordinamento dell'operazione su un arbitrario sistema distribuito.
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).