Calcolo distribuito

ModelsEdit

Molti compiti che vorremmo automatizzare usando un computer sono di tipo domanda-risposta: vorremmo fare una domanda e il computer dovrebbe produrre una risposta. Nell’informatica teorica, tali compiti sono chiamati problemi computazionali. Formalmente, un problema computazionale consiste di istanze insieme a una soluzione per ogni istanza. Le istanze sono domande che possiamo porre, e le soluzioni sono le risposte desiderate a queste domande.

L’informatica teorica cerca di capire quali problemi computazionali possono essere risolti usando un computer (teoria della computabilità) e con quale efficienza (teoria della complessità computazionale). Tradizionalmente, si dice che un problema può essere risolto usando un computer se possiamo progettare un algoritmo che produce una soluzione corretta per qualsiasi istanza data. Un tale algoritmo può essere implementato come un programma che gira su un computer generico: il programma legge un’istanza del problema dall’input, esegue qualche calcolo e produce la soluzione come output. Formalismi come le macchine ad accesso casuale o le macchine di Turing universali possono essere usati come modelli astratti di un computer sequenziale di uso generale che esegue tale algoritmo.

Il campo del calcolo concorrente e distribuito studia questioni simili nel caso di più computer o di 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 è affatto ovvio cosa si intenda per “risolvere un problema” nel caso di un sistema concorrente o distribuito: per esempio, qual è il compito del progettista di algoritmi, e qual è l’equivalente concorrente o distribuito di un computer sequenziale general-purpose?

La discussione che segue si concentra sul caso di più computer, anche se molte delle questioni sono le stesse per i processi concorrenti in esecuzione su un singolo computer.

Sono comunemente usati tre punti di vista:

Algoritmi paralleli nel modello a memoria condivisa

• Tutti i processori hanno accesso a una memoria condivisa. Il progettista dell’algoritmo sceglie il programma eseguito da ogni processore.
• Un modello teorico è quello delle macchine parallele ad accesso casuale (PRAM) che vengono utilizzate. Tuttavia, il modello PRAM classico presuppone un accesso sincrono alla memoria condivisa.
• I programmi a memoria condivisa possono essere estesi ai sistemi distribuiti se il sistema operativo sottostante incapsula la comunicazione tra i nodi e unifica virtualmente la memoria in tutti i singoli sistemi.
• Un modello che è più vicino al comportamento delle macchine multiprocessore del mondo reale e tiene conto dell’uso di istruzioni macchina, come Compare-and-swap (CAS), è quello della memoria condivisa asincrona. C’è un ampio corpo di lavoro su questo modello, un riassunto del quale può essere trovato in letteratura.

Algoritmi paralleli nel modello message-passing

• Il progettista dell’algoritmo sceglie la struttura della rete, così come il programma eseguito da ogni computer.
• Sono usati modelli come i circuiti booleani e le reti di ordinamento. Un circuito booleano può essere visto come una rete di computer: ogni porta è un computer che esegue un programma estremamente semplice. Allo stesso modo, una rete di ordinamento può essere vista come una rete di computer: ogni comparatore è un computer.

Algoritmi distribuiti nel modello message-passing

• Il progettista dell’algoritmo sceglie solo il programma del computer. Tutti i computer eseguono lo stesso programma. Il sistema deve funzionare correttamente indipendentemente dalla struttura della rete.
• Un modello comunemente usato è un grafo con una macchina a stato finito per nodo.

Nel caso degli 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 è illustrato nel seguente esempio.

Un esempioModifica

Considera il problema computazionale di trovare una colorazione di un dato grafico G. Campi diversi potrebbero adottare i seguenti approcci:

Algoritmi centralizzati

• Il grafico G è codificato come una stringa, e la stringa è data come input ad un computer. Il programma del computer trova una colorazione del grafico, codifica la colorazione come una stringa e produce il risultato.

Algoritmi paralleli

• Ancora una volta, il grafico G è codificato come una stringa. Tuttavia, più computer possono accedere alla stessa stringa in parallelo. Ogni computer potrebbe concentrarsi su una parte del grafico 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 grafico G è la struttura della rete di computer. C’è un computer per ogni nodo di G e un collegamento di comunicazione per ogni bordo di G. Inizialmente, ogni computer conosce solo i suoi vicini immediati nel grafico G; i computer devono scambiarsi messaggi l’un l’altro per scoprire di più sulla struttura di G. Ogni computer deve produrre il proprio colore come output.
• L’attenzione principale è sul coordinamento del funzionamento di un sistema distribuito arbitrario.

Mentre il campo degli algoritmi paralleli ha un focus diverso dal campo degli algoritmi distribuiti, c’è molta interazione tra i due campi. Per esempio, l’algoritmo di Cole-Vishkin per la colorazione dei grafi è stato originariamente presentato come un algoritmo parallelo, ma la stessa tecnica può anche essere usata direttamente come un algoritmo distribuito.

Inoltre, un algoritmo parallelo può essere implementato sia in un sistema parallelo (usando la memoria condivisa) sia in un sistema distribuito (usando il message passing). Il confine tradizionale tra algoritmi paralleli e distribuiti (scegliere una rete adatta vs. eseguire in qualsiasi rete data) non si trova nello stesso posto del confine tra sistemi paralleli e distribuiti (memoria condivisa vs. message passing).

Misure di complessitàModifica

Negli algoritmi paralleli, un’altra risorsa oltre al tempo e allo spazio è il numero di computer. Infatti, spesso c’è un trade-off tra il tempo di esecuzione e il numero di computer: il problema può essere risolto più velocemente se ci sono più computer che lavorano in parallelo (vedi speedup). Se un problema decisionale può essere risolto in tempo polilogaritmico usando un numero polinomiale di processori, allora si dice che il problema appartiene alla classe NC. La classe NC può essere definita altrettanto bene usando il formalismo PRAM o i circuiti booleani – le macchine PRAM possono simulare efficientemente i circuiti booleani e viceversa.

Nell’analisi degli algoritmi distribuiti, di solito si presta più attenzione alle operazioni di comunicazione che ai passi di calcolo. Forse il modello più semplice di calcolo distribuito è un sistema sincrono in cui tutti i nodi operano in modo lockstep. Questo modello è comunemente noto come modello LOCAL. Durante ogni giro di comunicazione, tutti i nodi in parallelo (1) ricevono gli ultimi messaggi dai loro vicini, (2) eseguono calcoli locali arbitrari, e (3) inviano nuovi messaggi ai loro vicini. In tali sistemi, una misura centrale di complessità è il numero di cicli di comunicazione sincrona richiesti per completare il compito.

Questa misura di complessità è strettamente legata al diametro della rete. Sia D il diametro della rete. Da un lato, qualsiasi problema calcolabile può essere risolto banalmente in un sistema distribuito sincrono in circa 2D round di comunicazione: basta raccogliere tutte le informazioni in una posizione (D round), risolvere il problema, e informare ogni nodo sulla soluzione (D round).

D’altra parte, se il tempo di esecuzione dell’algoritmo è molto più piccolo di D round di comunicazione, allora i nodi della rete devono produrre il loro output senza avere la possibilità di ottenere informazioni su parti lontane della rete. In altre parole, i nodi devono prendere decisioni globalmente coerenti basate su informazioni che sono disponibili nel loro vicinato D locale. Sono noti molti algoritmi distribuiti con un tempo di esecuzione molto più piccolo di D round, e capire quali problemi possono essere risolti da tali algoritmi è una delle questioni centrali di ricerca del campo. Tipicamente un algoritmo che risolve un problema in tempo polilogaritmico nella dimensione della rete è considerato efficiente in questo modello.

Un’altra misura comunemente usata è il numero totale di bit trasmessi nella rete (cfr. complessità della comunicazione). Le caratteristiche di questo concetto sono tipicamente catturate con il modello CONGEST(B), che similmente definito come il modello LOCAL ma dove i singoli messaggi possono contenere solo B bit.

Altri problemiModifica

I problemi computazionali tradizionali prendono la prospettiva che l’utente fa una domanda, un computer (o un sistema distribuito) processa la domanda, poi produce una risposta e si ferma. Tuttavia, ci sono anche problemi in cui al sistema è richiesto di non fermarsi, incluso il problema dei filosofi che pranzano e altri problemi simili di esclusione reciproca. In questi problemi, si suppone che il sistema distribuito coordini continuamente l’uso delle risorse condivise in modo che non si verifichino conflitti o deadlock.

Ci sono anche sfide fondamentali che sono uniche per il calcolo distribuito, per esempio quelle relative alla tolleranza agli errori. Esempi di problemi correlati includono problemi di consenso, tolleranza ai guasti bizantina e auto-stabilizzazione.

Molte ricerche sono anche concentrate sulla comprensione della natura asincrona dei sistemi distribuiti:

• I sincronizzatori possono essere usati per eseguire algoritmi sincroni in sistemi asincroni.
• Gli orologi logici forniscono un ordine causale “happened-before” degli eventi.
• Gli algoritmi di sincronizzazione dell’orologio forniscono un’indicazione del tempo fisico globalmente coerente.

ElectionEdit

L’elezione del coordinatore (o elezione del leader) è il processo di designare un singolo processo come organizzatore di qualche compito distribuito tra diversi computer (nodi). Prima che il compito sia iniziato, tutti i nodi della rete non sanno quale nodo servirà come “coordinatore” (o leader) del compito, o non sono in grado di comunicare con il coordinatore corrente. Dopo che un algoritmo di elezione del coordinatore è stato eseguito, tuttavia, ogni nodo in tutta la rete riconosce un particolare e unico nodo come coordinatore del compito.

I nodi della rete comunicano tra loro per decidere chi di loro entrerà nello stato di “coordinatore”. Per questo, hanno bisogno di qualche metodo per rompere la simmetria tra loro. Per esempio, se ogni nodo ha identità uniche e comparabili, allora i nodi possono confrontare le loro identità, e decidere che il nodo con l’identità più alta è il coordinatore.

La definizione di questo problema è spesso attribuita a LeLann, che lo ha formalizzato come un metodo per creare un nuovo token in una rete ad anello in cui il token è stato perso.

Gli algoritmi di elezione del coordinatore sono progettati per essere economici in termini di byte totali trasmessi, e di tempo. L’algoritmo suggerito da Gallager, Humblet e Spira per i grafi generali non direzionati ha avuto un forte impatto sulla progettazione di algoritmi distribuiti in generale, e ha vinto il premio Dijkstra per un articolo influente nel calcolo distribuito.

Molti altri algoritmi sono stati suggeriti per diversi tipi di grafi di rete, come anelli non direzionati, anelli unidirezionali, grafi completi, griglie, grafi diretti di Eulero, e altri. Un metodo generale che disaccoppia il problema della famiglia di grafi dalla progettazione dell’algoritmo di elezione del coordinatore è stato suggerito da Korach, Kutten e Moran.

Per eseguire il coordinamento, i sistemi distribuiti impiegano il concetto di coordinatori. Il problema dell’elezione del coordinatore è quello di scegliere un processo tra un gruppo di processi su diversi processori in un sistema distribuito per agire come coordinatore centrale. Esistono diversi algoritmi di elezione del coordinatore centrale.

Proprietà dei sistemi distribuitiModifica

Finora ci si è concentrati sulla progettazione di un sistema distribuito che risolva un dato problema. Un problema di ricerca complementare è lo studio delle proprietà di un dato sistema distribuito.

Il problema dell’arresto è un esempio analogo dal campo del calcolo centralizzato: ci viene dato un programma per computer e il compito è quello di decidere se si arresta o funziona per sempre. Il problema dell’arresto è indecidibile nel caso generale, e naturalmente capire il comportamento di una rete di computer è difficile almeno quanto capire il comportamento di un solo computer.

Tuttavia, ci sono molti casi speciali interessanti che sono decidibili. In particolare, è possibile ragionare sul comportamento di una rete di macchine a stato finito. Un esempio è dire se una data rete di macchine a stati finiti interagenti (asincrone e non deterministiche) può raggiungere un deadlock. Questo problema è PSPACE-completo, cioè è decidibile, ma non è probabile che ci sia un algoritmo efficiente (centralizzato, parallelo o distribuito) che risolva il problema nel caso di grandi reti.