Un sistema distribuito è un insieme di calcolatori indipendenti che appaiono all'utente come un unico sistema coerente. Più formalmente, si tratta di computer che contengono molteplici processori connessi da una rete di comunicazione. Leslie Lamport, uno dei padri fondatori del settore, offre una definizione ironica e profonda: «Un sistema distribuito è quello in cui il crash di un computer di cui non hai mai sentito parlare ti impedisce di lavorare.»
Il professore Ricci apre questo modulo sottolineando l'importanza dell'inquadramento concettuale e filosofico dei sistemi distribuiti, non solo dell'aspetto tecnico. Le tecnologie cambiano rapidamente — e con l'avvento dell'IA la parte tecnica di basso livello viene sempre più delegata — ma la comprensione dei principi fondamentali resta essenziale per un ingegnere. Questa lezione si inserisce nel percorso iniziato con il modulo di Omicini sui sistemi distribuiti e con la parte laboratoriale di Giovanni Ciatto, collegando la programmazione concorrente (già studiata nel primo modulo) alla dimensione distribuita.
La differenza fondamentale rispetto ai sistemi paralleli è che nei sistemi distribuiti la comunicazione avviene esclusivamente attraverso lo scambio di messaggi su una rete, non tramite memoria condivisa. Questo cambia radicalmente il modo di progettare e ragionare sui programmi.
Perché adottare un'architettura distribuita? Le ragioni sono molteplici. La scalabilità permette di aggiungere risorse al sistema incrementando la capacità complessiva. La modularità e l'eterogeneità consentono di integrare componenti diversi, potenzialmente di fornitori diversi. La condivisione di dati e risorse è intrinseca al modello distribuito. La struttura geografica del problema spesso richiede una soluzione distribuita: sistemi bancari, piattaforme social, servizi cloud globali. L'affidabilità migliora perché il sistema può tollerare il guasto di alcuni nodi. Il costo ridotto deriva dalla possibilità di usare hardware commodity anziché supercomputer dedicati.
Esiste però un compromesso fondamentale: l'efficienza. Aggiornare una posizione di memoria è ancora molto più veloce che inviare un messaggio attraverso una rete. Questa differenza è alla base di molte delle sfide ingegneristiche del corso.
| Sistemi Paralleli | Sistemi Distribuiti |
|---|---|
| Memoria condivisa (fisica o virtuale) | Nessuna memoria condivisa |
| Orologio comune a tutti i processori | Nessun orologio comune |
| Comunicazione via bus o rete ad alta velocità | Comunicazione via rete a latenza variabile |
| Scalabilità limitata dall'architettura | Scalabilità orizzontale potenzialmente illimitata |
| Guasto dell'intero sistema se un componente critico si rompe | Tolleranza ai guasti: altri nodi subentrano |
Il professore Ricci identifica tre macro-sfide che caratterizzano ogni sistema distribuito, tre «assenze» che definiscono il campo di gioco e impongono vincoli profondi a ogni algoritmo distribuito.
È impossibile sincronizzare perfettamente gli orologi di processori diversi a causa dell'incertezza intrinseca nei tempi di comunicazione. Anche usando protocolli come NTP, rimane sempre una finestra di incertezza. Gli orologi fisici non possono essere usati per sincronizzare eventi in un sistema distribuito: non esiste un «adesso» globale. Questa è la ragione per cui Lamport ha introdotto il concetto di tempo logico, che vedremo nella seconda parte della lezione.
A differenza dei sistemi concorrenti tradizionali (dove i thread condividono la memoria dello stesso processo), in un sistema distribuito ogni nodo ha la propria memoria privata. È impossibile per un processore conoscere lo stato globale del sistema in un dato istante. Questa assenza rende difficile osservare e verificare proprietà globali del sistema, come la mutua esclusione o l'assenza di deadlock.
In un sistema asincrono (dove non esiste un limite superiore noto al tempo di consegna dei messaggi), è impossibile distinguere tra un processore lento e un processore guasto. Se non riceviamo una risposta entro un certo tempo, non sappiamo se il nodo è caduto o se il messaggio sta semplicemente impiegando più del previsto. Questa incertezza ha implicazioni profonde, come vedremo con il teorema FLP e il problema del consenso.
Nei sistemi asincroni, l'assenza di un limite superiore al tempo di comunicazione rende teoricamente impossibile risolvere alcuni problemi fondamentali, come il consenso in presenza di guasti. Nella pratica si utilizzano timeout e ipotesi di sincronia parziale per aggirare questa limitazione.
Enunciato da Eric Brewer nel 2000 come congettura e dimostrato formalmente da Gilbert e Lynch nel 2002, il teorema CAP stabilisce che un sistema distribuito che condivide dati può offrire al massimo due delle tre seguenti proprietà:
Il teorema ha implicazioni pratiche immediate. Supponiamo due nodi su lati opposti di una partizione di rete. Se permettiamo ad almeno un nodo di aggiornare lo stato, i nodi diventano inconsistenti (perdiamo C). Se scegliamo di preservare la consistenza, un lato deve comportarsi come se non fosse disponibile (perdiamo A). Solo quando i nodi comunicano possiamo preservare sia C che A (perdendo P).
La scelta tra C, A e P dipende dal contesto applicativo. Un sistema bancario sceglierà consistenza e partizione (CP), sacrificando la disponibilità durante una partizione. Un social media può scegliere disponibilità e partizione (AP), accettando consistenza eventuale. Un sistema monolitico su una singola macchina può scegliere consistenza e disponibilità (CA), ma in questo caso non è veramente distribuito.
Il teorema CAP va interpretato nel contesto delle partizioni di rete. In assenza di partizioni, un sistema può fornire sia C che A. È solo quando si verifica una partizione che si deve scegliere. Brewer stesso, in una retrospettiva del 2012 (CAP Twelve Years Later), ha chiarito che la scelta non è binaria ma riguarda quanto consistenza o disponibilità si è disposti a sacrificare operazione per operazione.
Nell'interpretazione classica, il teorema CAP ignora la latenza, ma nella pratica latenza e partizioni sono profondamente correlate. Brewer stesso, nell'articolo del 2012, ha chiarito questo punto cruciale: operativamente, l'essenza del CAP si manifesta durante un timeout, un periodo in cui il programma deve prendere una decisione di partizione (partition decision).
Le due opzioni sono nette:
Pragmaticamente, una partizione è un limite di tempo sulla comunicazione. Se non si riesce a raggiungere la consistenza entro quel limite, ci si trova di fronte a una partizione e quindi a una scelta tra C e A per quella specifica operazione. Questi concetti catturano il problema progettuale centrale: i due lati del sistema stanno avanzando senza comunicare? In altre parole, il tempo è un fattore determinante. Un sistema che tollera secondi di inconsistenza (DynamoDB, Cassandra) opera diversamente da uno che richiede consistenza immediata (un DB relazionale tradizionale).
La latenza non è solo un problema di prestazioni: è un problema di correttezza. Quando due parti del sistema non possono comunicare entro un tempo accettabile, devono decidere se procedere (rischiando inconsistenza) o bloccarsi (sacrificando disponibilità). Non esiste una scelta giusta in assoluto, solo scelte consapevoli.
Il modello di programmazione canonico per i sistemi distribuiti è semplice: applicazioni come insiemi di processi heavyweight che comunicano scambiandosi messaggi attraverso canali. Ogni processo può avere molteplici thread che comunicano attraverso memoria condivisa internamente. Su questo modello base si sono innestati diversi paradigmi tradizionali.
L'RPC estende il paradigma procedurale classico ai sistemi distribuiti. L'idea è che un programma possa chiamare una procedura eseguita su un nodo remoto come se fosse locale. La chiamata viene impacchettata: i parametri vengono serializzati (marshaling), inviati su TCP o UDP, ricevuti dall'altra parte, despacchettati (unmarshaling), e la procedura viene eseguita. Il componente che fa il marshaling si chiama proxy; quello che riceve si chiama stub. A livello applicativo, tutto è trasparente. Storicamente, questa è stata l'architettura dominante dagli anni '80 in poi, con implementazioni come Sun RPC e DCE/RPC.
Con l'avvento della programmazione orientata agli oggetti, l'RPC è stato esteso al Distributed Object Computing. L'idea è che oggetti su nodi diversi possano invocare metodi gli uni degli altri come se fossero locali. Java RMI (Remote Method Invocation) e CORBA (Common Object Request Broker Architecture) sono gli esempi più noti. Il professore sottolinea come Java, quando uscì nel 1996, avesse già abbracciato completamente questa idea, mentre Microsoft proponeva DCOM (Distributed Component Object Model). L'astrazione è potente: un oggetto Counter con interfaccia remota può essere invocato da un altro nodo con una semplice chiamata a metodo, nascondendo la complessità della rete.
Il message passing è il modello più esplicito e meno astratto: i processi comunicano inviando e ricevendo messaggi attraverso canali. Non c'è trasparenza: il programmatore sa che sta comunicando attraverso la rete e deve gestire esplicitamente l'asincronia, la serializzazione, l'indirizzamento. Questo modello è alla base dei Message-Oriented Middleware (MOM), del paradigma ad attori (Hewitt, 1973), e di sistemi moderni come Apache Kafka, RabbitMQ e ZeroMQ. È il modello che, come vedremo, meglio cattura la realtà dei sistemi distribuiti.
Il professore sottolinea che il middleware RMI può essere utile come componente per costruire altri middleware, ma non è un modello generale per programmare sistemi distribuiti. Il salto di qualità avviene quando si abbandona l'illusione della trasparenza.
Nonostante l'apparente eleganza, l'idea di applicare i paradigmi tradizionali (procedurale, OOP) alla computazione distribuita presenta un problema fondamentale: la trasparenza non funziona. Questo è il punto centrale di un articolo fondamentale del 1994: «A Note on Distributed Computing» di Jim Waldo, Geoff Wyant, Ann Wollrath e Sam Kendall.
Il problema è che rendere trasparente la distribuzione — far sembrare una chiamata remota identica a una chiamata locale — nasconde differenze cruciali. Una chiamata locale è veloce, affidabile, passa attraverso memoria condivisa. Una chiamata remota è lenta, può fallire per guasti di rete o del nodo remoto, richiede serializzazione dei dati, ha una latenza di diversi ordini di grandezza superiore. Pensare che siano uguali porta a problemi ingegneristici seri: l'assenza di un criterio di località può generare catene di chiamate remote che si intrecciano, causando deadlock e race condition. Il controllo sulla distribuzione viene perso.
Immaginate di fare load balancing in un sistema dove tutte le chiamate sono trattate come locali. Un oggetto chiama un oggetto remoto, che ne chiama un altro, poi un altro ancora, in una catena che potrebbe persino tornare indietro. Il risultato? Deadlock immediati, corsa critica, perdita totale del controllo sulla località delle computazioni.
La conclusione è netta: la trasparenza è un'illusione pericolosa. I sistemi distribuiti richiedono di gestire esplicitamente aspetti che non possono essere astratti: latenza, guasti parziali, concorrenza, eterogeneità. I modelli che funzionano abbracciano queste differenze invece di nasconderle. Si passa quindi a modelli basati su scambio di messaggi e architetture service-oriented, dove le interazioni sono esplicitamente asincrone e la località è un aspetto centrale del progetto.
Superati i limiti dei paradigmi tradizionali, la ricerca e l'ingegneria si sono orientate verso approcci basati sulla decentralizzazione del controllo e su modelli di interazione asincrona. Le principali direzioni emerse sono molteplici.
Le architetture Service-Oriented (SOA) e, in particolare, i microservizi scompongono il sistema in servizi indipendenti, ciascuno con un proprio dominio di responsabilità, che comunicano attraverso protocolli ben definiti come REST, gRPC o messaggistica asincrona. Il Domain-Driven Design fornisce gli strumenti concettuali per delimitare i confini dei servizi (bounded context).
Le architetture Event-Driven portano il disaccoppiamento ancora oltre: i componenti comunicano attraverso eventi asincroni. Un evento rappresenta un fatto accaduto nel sistema; chi lo produce non conosce né deve conoscere i consumatori. Questo disaccoppiamento temporale e spaziale è alla base di sistemi altamente scalabili e resilienti, come le architetture stream-based (Apache Kafka) e i microservizi event-driven.
Il paradigma ad Attori (Actor Model), proposto da Carl Hewitt nel 1973, anticipava già queste idee. Ogni attore è un'entità autonoma con un proprio stato, che comunica solo attraverso messaggi asincroni. Non c'è memoria condivisa, non c'è chiamata sincrona bloccante. Questo paradigma è stato ripreso modernamente da Akka, Erlang/OTP e Orleans, ed è considerato da molti il modello più naturale per il calcolo distribuito.
Il cloud computing completa il quadro fornendo piattaforme (AWS, Azure, GCP) che offrono infrastruttura, piattaforma e software come servizio, permettendo di costruire sistemi distribuiti su larga scala con astrazioni sempre più alte e scalabilità orizzontale demandata all'infrastruttura.
Il filo conduttore è il passaggio dalla sincronia all'asincronia, dall'accentramento alla decentralizzazione, dalla trasparenza all'esplicitazione della distribuzione. I sistemi distribuiti di successo non nascondono la complessità: la gestiscono.
Per ragionare formalmente sui sistemi distribuiti, abbiamo bisogno di modelli di computazione. Il modello adottato in questo corso è semplice ma potente:
Questo modello descrive un sistema distribuito asincrono: non ci sono limiti noti a priori sui tempi di consegna. È il modello più generale e più difficile per cui progettare algoritmi, ma è anche il più realistico per internet e le reti moderne. Il professore sottolinea che questa modellazione serve non solo per descrivere, ma per verificare proprietà di correttezza e per ragionare su tutti i possibili scenari di esecuzione di un programma distribuito.
flowchart LR
subgraph CANALI["Modello di Computazione Distribuita"]
direction LR
P1["Processo P"] -->|"canale (P→Q)"| Q1["Processo Q"]
Q1 -->|"canale (Q→P)"| P1
end
P1 -->|"invio messaggio"| M["messaggio m"]
M -->|"ritardo finito
(arbitrario)"| Q1
Ricordate le assunzioni del modello: canali unidirezionali, buffer infiniti, nessun errore, nessun ordinamento, ritardo arbitrario ma finito. Queste definiscono il contesto in cui gli algoritmi distribuiti che studieremo devono operare.
In questo modello, ogni processo è descritto come un insieme di stati, una condizione iniziale e un insieme di eventi. Ogni evento può modificare lo stato del processo e lo stato di al più un canale incidente a quel processo. Il comportamento di ciascun processo può essere descritto visivamente attraverso diagrammi di transizione di stato.
Nel contesto distribuito, gli eventi si classificano in tre tipi fondamentali: eventi interni (computazione locale, modificano solo lo stato del processo), eventi di send (invio di un messaggio su un canale) ed eventi di receive (ricezione di un messaggio da un canale). La distinzione è importante perché a seconda dell'applicazione può essere più naturale modellare il comportamento in termini di eventi piuttosto che di stati.
Esplorate i diversi tipi di stato che un processo può assumere durante la sua esecuzione nel sistema distribuito usando l'esploratore interattivo.
I diagrammi a eventi (event diagrams) sono spesso più adatti dei diagrammi di stato per catturare l'evoluzione di un sistema distribuito, perché mettono in primo piano le relazioni causali tra eventi che accadono in luoghi diversi.
Il modello interleaving è il più semplice e deriva direttamente dai modelli usati per i sistemi concorrenti tradizionali (quelli del primo modulo del corso). L'idea è di assumere un ordinamento totale tra tutti gli eventi del sistema distribuito, come se le esecuzioni dei vari processi fossero mescolate in una singola sequenza lineare.
Prendiamo l'esempio della lezione: due processi P (nodo N1) e Q (nodo N2). P inizializza A=1 (P1), invia A sul canale CH (P2), stampa ok (P3). Q stampa subito (Q1), riceve da CH ottenendo R (Q2), stampa R (Q3). Nel modello interleaving, una possibile esecuzione è P1, P2, Q1, Q2, P3, Q3. Un'altra: Q1, P1, P2, P3, Q2, Q3. Ogni ordinamento totale è un'esecuzione valida, purché rispetti l'ordine degli eventi all'interno di ciascun processo. Ma il modello interleaving ha limitazioni importanti.
Il modello interleaving non cattura i guasti (failure). Presuppone sempre che, ad esempio, Q2 possa essere eseguita. Ma se il nodo N2 va giù, Q2 non verrà mai eseguita. Per ragionare sui possibili fail serve un modello più astratto. Inoltre, il modello presuppone una sequenza globale osservabile che in realtà non esiste in un sistema distribuito: nessun nodo ha una visione completa di tutti gli eventi.
Il problema fondamentale è che in un sistema distribuito non esiste un osservatore globale in grado di produrre una sequenza totale degli eventi. Qualsiasi ordinamento totale sarebbe un artefatto, non una proprietà intrinseca del sistema. È questa l'osservazione che porta Lamport al modello successivo.
Lamport osservò che in un sistema veramente distribuito si possono definire solo ordinamenti parziali tra gli eventi, usando la relazione di happened-before (→). È una relazione causale: se un evento a potrebbe aver causato un evento b, allora a è accaduto prima di b.
La relazione happened-before (→) è la più piccola relazione che soddisfa:
Due eventi che non sono in relazione happened-before si dicono concorrenti: e || f = non (e → f) e non (f → e).
flowchart LR
subgraph P["Processo P (nodo N1)"]
direction TB
p1["P1: A := 1"] --> p2["P2: send(A, CH)"] --> p3["P3: print ok"]
end
subgraph Q["Processo Q (nodo N2)"]
direction TB
q1["Q1: print ready"] --> q2["Q2: receive(CH, R)"] --> q3["Q3: print R"]
end
p2 -.->|"send → receive
⇝"| q2
Nel diagramma, le frecce continue rappresentano l'ordine all'interno dello stesso processo: P1 → P2 → P3, Q1 → Q2 → Q3. La freccia tratteggiata rappresenta la comunicazione: P2 (send) → Q2 (receive). Per transitività, P1 → Q2 e P2 → Q3. Non c'è invece relazione tra P1 e Q1: sono eventi concorrenti, perché non esiste una catena causale che li connetta.
Una run nel modello happened-before è una tupla (E, →) dove E è l'insieme di tutti gli eventi e → è un ordine parziale su E tale che tutti gli eventi all'interno di un singolo processo sono totalmente ordinati. È questo il modello che useremo come base per gli algoritmi di ordinamento e coordinazione.
La relazione happened-before è stata introdotta da Lamport nel celebre articolo «Time, Clocks, and the Ordering of Events in a Distributed System» (1978). È il fondamento concettuale su cui si basano orologi logici, orologi vettoriali e la maggior parte degli algoritmi distribuiti che studieremo. La transitività è la proprietà chiave che permette di costruire catene causali anche lunghe.
Il modello happened-before assume un ordinamento totale tra gli eventi all'interno dello stesso processo. Tuttavia, non è vero che tutti questi eventi abbiano una relazione causa-effetto reale. Due eventi consecutivi in uno stesso processo potrebbero essere completamente indipendenti, come la ricezione di due messaggi da porte diverse che aggiornano oggetti distinti. L'ordine temporale non implica causalità.
La relazione di causalità reale è un ordine parziale anche all'interno dello stesso processo, ma è spesso difficile o costosa da determinare. Per questo si utilizza la relazione di causalità potenziale (→p), la più piccola relazione che soddisfa:
Due eventi non correlati da →p si dicono indipendenti. Esempio concreto: un processo con due thread che accedono a insiemi di oggetti mutualmente disgiunti. Gli eventi dei due thread non hanno relazione causale tra loro, anche se accadono sullo stesso processo. La causalità potenziale li tratta come indipendenti.
Un diagramma di causalità potenziale è equivalente all'insieme di tutti i diagrammi happened-before che sono consistenti con esso (cioè →p ⊆ →). La causalità potenziale è più astratta e meno vincolante: incorpora un maggior grado di nondeterminismo, il che è utile per applicazioni come il debugging distribuito.
Quale modello usare dipende dall'applicazione. I tre modelli offrono diversi livelli di astrazione e catturano diversi aspetti del comportamento di un sistema distribuito.
Ordinamento: totale tra tutti gli eventi del sistema.
Quando usarlo: per la verifica formale di programmi distribuiti. Per dimostrare proprietà come l'assenza di deadlock, l'interleaving è sufficiente ed è il modello più semplice da trattare analiticamente.
Limitazione: presuppone una sequenza globale osservabile che nei sistemi distribuiti non esiste. Non cattura i guasti.
Ordinamento: parziale tra eventi, totale all'interno di ogni processo.
Quando usarlo: per catturare il comportamento del sistema e verificare se una certa proprietà globale è diventata vera in un'esecuzione. L'osservazione si basa sull'ordinamento causale, non su un tempo globale.
Vantaggio: non richiede un osservatore globale. È il modello più adatto per descrivere esecuzioni in sistemi distribuiti asincroni.
Ordinamento: parziale anche all'interno dello stesso processo.
Quando usarlo: per il debug distribuito, dove ci si chiede se una proprietà globale avrebbe potuto diventare vera in un'esecuzione. È vantaggioso catturare solo gli ordini parziali corrispondenti alla causalità effettiva.
Vantaggio: elimina ordini forzati arbitrariamente, dando il massimo nondeterminismo e quindi il massimo potere espressivo.
La relazione gerarchica è importante: un programma distribuito può essere visto come un insieme di diagrammi di causalità potenziale che può generare. Ogni diagramma di causalità potenziale equivale a un insieme di diagrammi happened-before. Ogni diagramma happened-before equivale a un insieme di sequenze globali (interleaving). La scelta del modello determina quanta complessità viene catturata e quanta viene astratta.
Per implementare concretamente il modello happened-before, Lamport introdusse il concetto di orologio logico (logical clock). L'idea è assegnare un numero (timestamp) a ogni evento in modo tale che la relazione happened-before sia preservata numericamente.
Un orologio logico C assegna a ogni evento a del processo Pi un numero Ci(a) tale che:
∀ a ∈ Pi, b ∈ Pj : se a → b allora Ci(a) < Cj(b)
La Clock Condition è soddisfatta se:
Usando un semplice contatore C per ogni processo:
Usate il simulatore interattivo qui sotto per vedere il funzionamento passo-passo con due processi.
Con gli orologi logici vale: a → b implica C(a) < C(b), ma NON vale il viceversa. C(a) < C(b) non implica a → b. I contatori logici danno un ordinamento totale che avrebbe potuto accadere, non quello che è effettivamente accaduto. Per determinare se due eventi sono in relazione causale o sono concorrenti servono gli orologi vettoriali.
Proposti indipendentemente da Fidge (1988) e Mattern (1988), gli orologi vettoriali assegnano a ogni evento un vettore di dimensione k (numero di processi), tale che:
∀ a, b : a → b ⇔ VC(a) < VC(b)
La relazione è bi-direzionale: non solo la causalità implica un ordine nei vettori, ma l'ordine nei vettori implica causalità. Per due vettori v, w:
Se due vettori sono incomparabili (né v < w né w < v), gli eventi corrispondenti sono concorrenti. È questa capacità di rilevare la concorrenza che rende gli orologi vettoriali superiori a quelli scalari.
L'implementazione estende gli orologi logici: ogni processo Pi mantiene un vettore V di contatori (dimensione = numero processi). V[i] viene incrementato a ogni evento. Il vettore completo viene trasmesso nei messaggi. All'arrivo, il ricevente aggiorna ogni componente con max(Vproprio[k], Vricevuto[k]).
Esempio concreto dalla lezione: tre processi A, B, C partono da [0,0,0]. Dopo alcuni eventi interni, B arriva a [0,2,0] e C a [0,0,1]. Quando B invia un messaggio ad A, il vettore [0,3,0] viene trasmesso. A lo riceve e aggiorna: per ogni k, prende max(A[k], Vricevuto[k]). Così A acquisice conoscenza dello stato di B e C.
Esplorate l'implementazione nel codice commentato:
Passiamo ora agli algoritmi distribuiti della seconda parte della lezione. Il primo problema è la mutua esclusione in ambiente distribuito: analogo al caso concorrente, ma qui i processi sono su nodi diversi e non condividono memoria.
L'algoritmo centralizzato prevede un coordinatore (P0) che gestisce un token di accesso alla sezione critica. Le proprietà richieste sono:
Il punto cruciale è la fairness. Se s → t (lo stato s precede causalmente lo stato t), la richiesta fatta in s deve essere servita prima di quella fatta in t, anche se la richiesta t arriva al coordinatore prima. Come si realizza? Ogni processo include nel messaggio di richiesta il proprio vettore v, che cattura la conoscenza delle richieste fatte da tutti i processi fino a quel momento. Il coordinatore ritarda l'elaborazione di una richiesta t finché tutte le richieste che la precedono causalmente non sono arrivate.
Sul lato coordinatore (P0), le strutture dati sono reqList (coda delle richieste ricevute) e reqDone (vettore delle richieste soddisfatte per ogni processo). Una richiesta w è eleggibile se w.v ≤ reqDone: per ogni j ≠ w.p, w.v[j] == reqDone[j] (nessuna richiesta pendente da altri), e per j = w.p, w.v[j] == reqDone[j] + 1 (esattamente una richiesta pendente dal richiedente).
La condizione di eleggibilità è il cuore dell'algoritmo: garantisce che le richieste siano servite secondo l'ordine causale, non secondo l'ordine di arrivo al coordinatore. È un esempio perfetto di come gli orologi vettoriali possano essere usati per implementare fairness in un sistema distribuito.
L'algoritmo di Ricart-Agrawala (1981) è una soluzione decentralizzata: non richiede un coordinatore centrale. Per entrare in sezione critica, un processo deve ottenere il permesso da tutti gli altri N-1 processi.
req(myts) a tutti gli altri processi, azzera numOK.Numero di messaggi: 2(N-1) per accesso alla CS. L'algoritmo funziona anche con canali non FIFO, perché usa i timestamp per ordinare le richieste. È un esempio di come un timestamp logico possa fungere da «biglietto numerato» per determinare l'ordine di accesso a una risorsa condivisa senza un'autorità centrale.
L'algoritmo di Ricart-Agrawala dimostra che la mutua esclusione distribuita può essere implementata senza un coordinatore centrale, a costo di O(N) messaggi per accesso. È un compromesso classico tra centralizzazione (un singolo punto di guasto, ma pochi messaggi) e decentralizzazione (nessun punto di guasto singolo, ma più messaggi).
L'elezione del leader è un problema fondamentale: scegliere un processo tra N che svolga il ruolo di coordinatore, ad esempio per algoritmi centralizzati come quello appena visto. L'algoritmo di Chang-Roberts (1979) è elegante nella sua semplicità e si basa su una topologia ad anello logico sovrapposta alla rete sottostante.
Ogni processo ha un identificatore unico (PID). L'obiettivo è eleggere il processo con PID massimo.
(election, myid) al successivo nell'anello.(election, j):
(election, j).(leader, myid).(election, myid).(leader, j): registra j come leader, inoltra il messaggio (se non è il leader stesso).Numero di messaggi: caso peggiore 2N-1 messaggi di elezione + N messaggi di leader. È ampiamente usato per scegliere coordinatori in algoritmi centralizzati, sfruttando il fatto che la topologia ad anello è facile da mantenere e il protocollo è semplice da dimostrare corretto.
La computazione completamente asincrona non impone restrizioni sull'ordinamento dei messaggi: massimo nondeterminismo, massima concorrenza. A volte però è utile ridurre il nondeterminismo restringendo l'ordinamento dei messaggi possibile.
Dall'ordinamento FIFO (first-in, first-out) si passa all'ordinamento causale: dati due messaggi m1, m2 tali che send(m1) → send(m2), si richiede che rec(m1) → rec(m2). Non è consentito il «sorpasso causale»: se un messaggio è stato inviato prima (causalmente) di un altro, deve essere ricevuto prima.
L'algoritmo estende gli orologi vettoriali con una matrice m di interi, dove s.m[j,k] = numero di messaggi inviati da Pj a Pk conosciuti da Pi nello stato s. Quando un messaggio viene inviato, la matrice è trasmessa con il messaggio. Alla ricezione, il messaggio viene verificato per eleggibilità prima di essere consegnato. Se non eleggibile, viene bufferizzato fino a quando lo diventa.
Condizione di eleggibilità per un messaggio ricevuto da Pi da Pj con matrice m':
L'ordinamento totale è ancora più forte: richiede che tutti i messaggi siano ricevuti nello stesso ordine da tutti i processi. È utile nel multicast per garantire che tutti i destinatari vedano i messaggi nella stessa sequenza.
Catturare lo stato globale di un sistema distribuito da un singolo processo è una sfida. Lo stato globale è un insieme di stati locali concorrenti tra loro secondo il modello happened-before. Per molte applicazioni è sufficiente catturare uno stato globale che è esistito nel passato, non necessariamente lo stato «corrente».
Uno stato globale consistente richiede il concetto di taglio consistente (consistent cut): uno stato S dove ∀ e = receive(msg), se e' = send(msg) e e' → e, allora e' ∈ S. In parole povere, ogni messaggio ricevuto nel taglio deve anche essere stato inviato all'interno del taglio. Un taglio inconsistente catturerebbe un messaggio ricevuto ma il cui invio è fuori dal taglio, creando uno stato «impossibile».
L'algoritmo usa un meccanismo a marker e assume canali FIFO. Ogni processo ha una variabile color (bianco/rosso). Lo snapshot corrisponde allo stato del sistema appena prima che i processi diventino rossi.
flowchart LR
subgraph P["Processo P"]
p0["e0"] --> p1["e1"] --> p2["e2"]
p2 --> p3["e3"]
end
subgraph Q["Processo Q"]
q0["f0"] --> q1["f1"] --> q2["f2"]
end
p2 -.->|"messaggio m"| q1
p1 -.->|"messaggio m'"| q2
Grazie ai canali FIFO, nessun processo bianco riceve mai un messaggio inviato da un processo rosso, garantendo che gli stati locali siano mutualmente concorrenti. L'algoritmo è usato per rilevamento di deadlock, terminazione e osservazione di predicati globali.
Il consenso è il problema di far concordare processi distribuiti sul valore di una proprietà o su un'azione da compiere. È pervasivo: transazioni DB, elezione del leader, replicazione, broadcast atomico, blockchain.
Ogni Pi inizia undecided e propone un valore vi. I processi comunicano, scambiandosi valori. Ogni processo alla volta imposta di ed entra nello stato decided. Requisiti:
In una rete asincrona, in presenza di anche un singolo processo che si arresta senza preavviso, il problema del consenso è impossibile da risolvere. È il celebre risultato FLP, che ha profonde implicazioni pratiche.
L'impossibilità deriva dall'incertezza: non potendo distinguere un processo guasto da uno lento, un algoritmo che deve garantire terminazione non può aspettare indefinitamente, ma se decide troppo presto rischia di sbagliare. Le soluzioni pratiche introducono ipotesi aggiuntive: sincronia parziale, failure detector, o assunzioni probabilistiche. Il teorema non dice che il consenso è impossibile nella pratica: dice che è impossibile garantirne la soluzione in un modello puramente asincrono.
Per superare l'impossibilità FLP, la pratica introduce assunzioni di sincronia: un limite superiore noto al ritardo dei messaggi e alla durata delle azioni. Questo permette di usare timeout per rilevare guasti.
| Tipo | Descrizione |
|---|---|
| Crash | Il processore si arresta e smette di funzionare. |
| Crash+Link | Un processore crasha o un collegamento di rete si interrompe. |
| Omission | Il processo invia/riceve solo un sottoinsieme dei messaggi previsti. |
| Byzantine | Il processore si comporta in modo arbitrario, potenzialmente malevolo. |
Ogni processo mantiene V (insieme dei valori proposti noti). Inizialmente V = {vi}. L'algoritmo procede per f+1 round (f = max guasti). In ogni round, ogni processo invia a tutti i valori di V non ancora inviati, riceve dagli altri, aggiorna V. Alla fine, applica una funzione di decisione comune. Numero messaggi: O((f+1)N2).
Quando i guasti possono essere arbitrari (byzantine), il teorema stabilisce che non esiste un protocollo f-resiliente per N ≤ 3f. Serve N ≥ 3f+1 per tollerare f guasti bizantini. L'algoritmo procede per f+1 round con un coordinatore rotante (king) e due fasi: scambio di valori e decisione basata sulla molteplicità (se un valore ha più di N/2+f copie, viene scelto; altrimenti si usa il valore del king).
Il consenso è alla base di due algoritmi moderni fondamentali: Paxos e Raft, entrambi progettati per risolvere il consenso in presenza di guasti crash-stop (non bizantini).
Paxos è una famiglia di protocolli per il consenso in reti di processori inaffidabili. Offre un ventaglio di trade-off tra numero di processori, ritardi di messaggio, attività dei partecipanti, numero di messaggi e tipi di guasto. È usato dove la durabilità è critica, come per replicare un file o un database. La sua fama di algoritmo difficile da comprendere ha portato allo sviluppo di Raft.
Raft è progettato per essere comprensibile, pur essendo equivalente a Paxos in fault-tolerance e performance. Offre un modo generico per distribuire una macchina a stati su un cluster, garantendo che ogni nodo concordi sulla stessa serie di transizioni di stato. È implementato in Go, C++, Java e Scala, con implementazioni open-source di riferimento disponibili su raft.github.io.
Il consenso si presenta tipicamente nel contesto delle macchine a stati replicati, un approccio generale per costruire sistemi fault-tolerant. Ogni server ha una macchina a stati e un log. La macchina a stati è il componente che si vuole rendere fault-tolerant (es. una tabella hash). L'algoritmo di consenso gestisce un log replicato contenente i comandi provenienti dai client. Le macchine a stati processano sequenze identiche di comandi, producendo le stesse uscite.
flowchart LR client["Client"] -->|"comando: set x = 3"| SM1["Server 1
Macchina a Stati
Log: [set x=3, ...]"] client --> SM2["Server 2
Macchina a Stati
Log: [set x=3, ...]"] client --> SM3["Server 3
Macchina a Stati
Log: [set x=3, ...]"] SM1 <-->|"Consenso"| SM2 <-->|"Consenso"| SM3 SM1 <--> SM3
Se una macchina applica set x = 3 come n-esimo comando, nessun'altra macchina applicherà mai un comando diverso come n-esimo comando. Algoritmi come Paxos e Raft garantiscono questa proprietà anche in presenza di guasti di una minoranza dei server. Come risultato, il sistema appare ai client come un'unica macchina a stati affidabile.
La catena concettuale è: il consenso è il problema astratto, Paxos e Raft sono algoritmi concreti che lo risolvono sotto ipotesi di crash-stop, e le macchine a stati replicati sono l'architettura che usa il consenso per costruire servizi fault-tolerant. Questa gerarchia è fondamentale per comprendere i sistemi distribuiti moderni.
Assenza di un orologio condiviso, assenza di memoria condivisa, assenza di un rilevamento accurato dei guasti (failure detection).
Un sistema distribuito che condivide dati può offrire al massimo due delle tre proprietà: Consistency (C), Availability (A), Partition Tolerance (P). La scelta dipende dal contesto applicativo.
Perché chiamata locale e chiamata remota hanno differenze sostanziali (latenza, possibili guasti, serializzazione). Nasconderle porta a deadlock, race condition e perdita di controllo. Lo spiega l'articolo di Waldo et al. (1994) «A Note on Distributed Computing».
Interleaving (ordinamento totale), Happened-Before (ordinamento parziale, totale nello stesso processo), Causalità Potenziale (ordinamento parziale anche nello stesso processo). Ogni diagramma di causalità potenziale equivale a un insieme di diagrammi happened-before; ogni happened-before equivale a un insieme di sequenze interleaving.
Ogni processo ha un contatore C. Regola 1: incremento tra eventi. Regola 2: il timestamp C è incluso nei messaggi inviati (piggybacking). Regola 3: alla ricezione, C = max(C, Tm) + 1. Questo garantisce: se a → b, allora C(a) < C(b).
Gli orologi vettoriali permettono di determinare la relazione di causalità in entrambe le direzioni: a → b se e solo se VC(a) < VC(b). Permettono quindi di rilevare la concorrenza tra eventi, impossibile con i contatori scalari.
Ogni processo include il proprio vettore di clock nei messaggi di richiesta. Il coordinatore usa la condizione di eleggibilità per ritardare le richieste finché tutte quelle che le precedono causalmente non sono arrivate. w.v ≤ reqDone garantisce l'ordine causale.
In una rete asincrona, anche con un solo processo che può arrestarsi, il consenso è impossibile da risolvere. L'incapacità di distinguere un processo guasto da uno lento impedisce di garantire terminazione, accordo e integrità simultaneamente.
Non esiste un protocollo f-resiliente per N ≤ 3f (N processi, f guasti bizantini). Serve N ≥ 3f + 1 per tollerare f guasti con comportamento arbitrario.
È un'architettura fault-tolerant dove ogni server ha una macchina a stati e un log replicato. L'algoritmo di consenso (Paxos, Raft) gestisce il log: se un server applica «set x = 3» come n-esimo comando, nessun altro applicherà un comando diverso come n-esimo. Il sistema appare come un'unica macchina a stati affidabile.