Progettare algoritmi per sistemi distribuiti significa operare senza clock condiviso, senza memoria condivisa e in presenza di guasti. Questi tre vincoli cambiano radicalmente l'approccio: non possiamo piu usare semafori o mutex come si fa nel caso concorrente classico, perche non esiste una risorsa centrale di sincronizzazione.
L'unico meccanismo di coordinazione disponibile in un sistema distribuito asincrono e lo scambio di messaggi. Ogni algoritmo distribuito si riduce a decidere cosa comunicare, quando comunicarlo e come interpretare cio che si riceve.
La maggior parte degli algoritmi discussi in questo capitolo assume un sistema asincrono senza guasti (tempo di consegna finito ma non noto a priori). Solo per il consenso si introduce l'ipotesi di sincronia con timeout per gestire i fallimenti.
| Sfida | Conseguenza | Soluzione negli algoritmi |
|---|---|---|
| Nessun clock condiviso | Impossibile ordinare eventi con tempo fisico | Clock logici e relazione happened-before |
| Nessuna memoria condivisa | Stato globale non osservabile direttamente | Snapshot algoritmi come Chandy-Lamport |
| Nessun failure detection accurato | Lento e guasto sono indistinguibili | Timeout e modelli a sincronia |
Piu in dettaglio, i sistemi distribuiti presentano tre assenze fondamentali che li rendono radicalmente diversi dai sistemi concorrenti tradizionali (basati su memoria condivisa):
Non esiste un limite superiore noto al tempo di consegna dei messaggi. Il ritardo puo essere arbitrario ma finito. La maggior parte degli algoritmi distribuiti assume reti asincrone in assenza di guasti. Il nondeterminismo e massimo, la concorrenza e massima. Ideali per ambienti non critici dove la probabilita di guasto e bassa.
Esiste un limite superiore noto al tempo di consegna dei messaggi e alla durata delle azioni dei processi. Si possono usare timeout per rilevare guasti. La progettazione degli algoritmi e piu semplice. Necessari quando si devono gestire guasti, ad esempio negli algoritmi di consensus o nei protocolli bizantini.
Il professore elenca le cinque macro-categorie che gli algoritmi distribuiti devono affrontare, tutte basate sugli orologi logici e sulla relazione happened before gia introdotta nel modulo precedente:
Tutti questi algoritmi si basano sugli orologi logici e sulla relazione happened before (→) per definire un ordinamento tra eventi correlati. Il concetto di tempo logico di Lamport (1978) e il fondamento su cui poggia l'intera architettura degli algoritmi distribuiti.
Il professore richiama i tre modelli principali per descrivere il comportamento di un programma distribuito:
Il problema e analogo a quello della sezione critica in ambito concorrente: un insieme di processi distribuiti ha nel proprio codice una porzione di programma che puo essere eseguita da un solo processo alla volta. Nel caso concorrente useremmo un semaforo o un mutex. Nel caso distribuito dobbiamo progettare un algoritmo basato esclusivamente sullo scambio di messaggi.
Le tre proprieta della sezione critica distribuita sono: safety (due processi non possono mai essere contemporaneamente in CS), liveness (ogni richiesta viene prima o poi concessa) e fairness (le richieste vengono servite secondo l'ordine della relazione happened-before).
Il professore sottolinea due approcci principali. Il primo e centralizzato: si assume un coordinatore che gestisce i permessi, soluzione piu semplice ma con un single point of failure. Il secondo e decentralizzato (Ricart-Agrawala), dove non esiste un coordinatore unico e tutti i processi collaborano in modo simmetrico.
Un processo coordinatore gestisce un token. I processi inviano richieste al coordinatore, che le accoda e assegna il token rispettando l'ordinamento causale. Piu semplice da implementare, ma il coordinatore e un collo di bottiglia e un punto unico di fallimento.
Ogni processo che vuole entrare in CS invia una richiesta timestampata a tutti gli altri processi. Un processo concede il permesso (OK) se non e interessato alla CS o se la propria richiesta ha un timestamp maggiore. Simmetrico, senza coordinatori, ma richiede O(N-1) messaggi per richiesta.
Nell'algoritmo centralizzato esiste un processo coordinatore P0 che detiene il token. I processi clients Pi (con i = 1..N) cooperano trasportando il proprio vector clock v in ogni messaggio (piggybacking), cosi che il coordinatore possa ricostruire l'ordinamento causale delle richieste.
Il punto fondamentale e la fairness: se due richieste arrivano, la richiesta che e accaduta prima nella relazione happened-before deve essere servita prima, anche se arriva al coordinatore dopo. Per fare questo, ogni processo allega il proprio vector clock v alla richiesta: v[j] rappresenta il numero di richieste fatte da Pj che precedono causalmente lo stato corrente.
Quando un processo invia una richiesta al coordinatore, include non solo la propria richiesta ma anche la conoscenza che ha delle richieste fatte dagli altri. Cosi il coordinatore puo ritardare una richiesta se sa che ce n'e un'altra in sospeso che la precede causalmente.
Il coordinatore mantiene due strutture:
reqList: lista delle richieste ricevute ma non ancora soddisfatte.reqDone: array tale che reqDone[i] = numero di richieste di Pi gia soddisfatte.Una richiesta w in reqList e eligible se per ogni j, w.v[j] == reqDone[j] (e per j == w.p, w.v[j] == reqDone[j] + 1). Cio significa: non ci sono richieste accadute prima di w che non sono state ancora soddisfatte.
Vediamo un esempio concreto. P1 invia una richiesta con vettore [1,0]. P2 invia una richiesta con vettore [1,1] (perche sa che P1 ha gia fatto richiesta). Il coordinatore, quando riceve [1,0] da P1, nota che non ci sono richieste pendenti da altri, quindi puo servire subito P1. Quando riceve [1,1] da P2, vede che P2 stesso dichiara che P1 ha una richiesta in sospeso — ma il coordinatore ha gia servito P1, quindi il suo reqDone[1] ora vale 1, e la richiesta di P2 diventa eligible.
sequenceDiagram
participant P1
participant P0 as Coordinatore
participant P2
P1->>P0: req(v=[1,0])
P0->>P0: reqDone=[0,0] serve P1
P0->>P1: token
P1->>P0: release(token)
P2->>P0: req(v=[1,1])
P0->>P0: reqDone=[1,0] w.v=[1,1] eligible
P0->>P2: token
In termini piu formali: 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. Sul lato coordinatore, una richiesta w e 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.
I processi piggybackano il proprio vector clock su tutti i messaggi in uscita. Quando un processo riceve un messaggio, aggiorna il proprio vector clock con il component-wise max. Cosi il vettore nella richiesta contiene la conoscenza causale del richiedente.
L'algoritmo centralizzato richiede 2 messaggi per richiesta (richiesta + token di risposta) piu i messaggi per propagare i vector clock. Il coordinatore e un single point of failure e puo diventare un collo di bottiglia.
Il flusso completo richiesta–token–rilascio, con la chiamata a checkReq sia alla ricezione di una richiesta sia al ritorno del token, e riassunto nel diagramma seguente.
sequenceDiagram
participant P1 as Pi (client)
participant C as P0 (coordinator)
participant P2 as Pj (client)
Note over P1: v[i]++, send(req, v)
P1->>C: (req, v = [1,0,0,...])
Note over C: append reqList
if haveToken: checkReq()
Note over C: w = first(eligible)
send token, incr reqDone
C->>P1: token
Note over P1: inCS = true
Note over P1: [sezione critica]
P1->>C: token (release)
Note over P1: inCS = false
Note over C: haveToken = true
checkReq() again
C->>P2: token (prossimo eligible)
Il processo client Pi, quando riceve un messaggio da un altro processo, aggiorna il proprio vettore v con il component-wise max del suo vecchio valore e del vettore ricevuto. Questo garantisce che la conoscenza causale si propaghi correttamente.
Il codice seguente mostra la struttura dell'algoritmo: ogni client tiene un vector clock v, incrementa la propria componente per ogni richiesta, e invia il vettore al coordinatore. Il coordinatore, ricevuta la richiesta, verifica l'eligibility prima di assegnare il token.
Aziona il simulatore per vedere come il coordinatore gestisce le richieste concorrenti di due processi. Clicca "Passo P1" o "Passo P2" per far avanzare ogni processo, oppure "Reset" per ricominciare. Il coordinatore decide automaticamente se assegnare il token.
Presentato da Glenn Ricart e Ashok Agrawala nel 1981, questo algoritmo e completamente decentralizzato e non richiede un coordinatore. L'idea e semplice: ogni processo che vuole entrare in sezione critica invia un messaggio con timestamp a tutti gli altri processi. Un processo ricevente risponde con un OK se non e interessato a entrare in CS o se la propria richiesta ha un timestamp maggiore (cioe e avvenuta dopo secondo l'ordine logico). Altrimenti, accoda la richiesta in attesa.
Un processo ottiene il permesso di entrare in CS quando ha ricevuto OK da tutti gli N-1 processi. Quando esce dalla CS, invia OK a tutti i processi nella propria coda di attesa.
Il numero di messaggi per richiesta e 2(N-1): (N-1) richieste inviate + (N-1) OK ricevuti. L'algoritmo funziona anche con canali non FIFO.
Ricart-Agrawala e considerato ottimale per il numero di messaggi: ogni entrata in CS richiede esattamente 2(N-1) messaggi, e nessun messaggio superfluo viene generato.
flowchart TD
A[Pi vuole entrare in CS] --> B[myts = logical_clock]
B --> C[Invia req(myts) a tutti]
C --> D{Attesa OK da tutti}
D -->|Riceve OK da Pj| E[numOK++]
E --> F{numOK == N-1?}
F -->|Si| G[Entra in CS]
F -->|No| D
G --> H[myts = infinity]
H --> I[Invia OK a pending queue]
I --> J[Svuota pending queue]
req(myts) a tutti gli altri processi, azzera numOK.È 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).
Ogni processo Pi mantiene una coda di richieste pendenti (pendingQ), un timestamp myts (inizializzato a infinito, segnalando che non si e interessati alla CS), e un contatore numOK.
Il primo simulatore ripercorre l'algoritmo su 3 processi, evidenziando le condizioni di risposta:
Pi imposta myts al proprio clock logico e invia un messaggio (req, myts) a tutti gli altri processi.Pj, un processo Pi risponde con OK se:
myts == infinity), oppurePj nella propria pendingQ.OK da tutti gli altri processi.OK a tutti i processi in pendingQ e resetta myts a infinity.La fairness e assicurata dalla relazione d'ordine sui timestamp (a parita di timestamp, vince il PID piu basso).
Il secondo simulatore, con avanzamento manuale dei singoli processi, mostra il caso in cui due processi competono per la sezione critica: chi ha il timestamp piu alto accoda l'altro in pendingQ e concede l'OK solo al rilascio.
Il problema della leader election (elezione del leader) sorge naturalmente quando si usa un approccio centralizzato: se il coordinatore fallisce, chi diventa il nuovo coordinatore? L'algoritmo di Chang-Roberts risolve questo problema superimponendo una topologia logica ad anello sulla rete fisica e usando un criterio semplice: viene eletto il processo con il PID piu alto.
Il funzionamento e il seguente:
election con il proprio ID al vicino sinistro sull'anello.election(j) controlla: se j > myid, inoltra il messaggio con l'ID corrente; se j == myid, significa che il messaggio ha fatto tutto il giro e il mittente originale e il leader: invia un messaggio leader(myid); se j < myid e il processo non e ancora sveglio, scarta il messaggio e si candida lui stesso.leader viene propagato a tutto l'anello per notificare chi e il nuovo leader.Il numero di messaggi nel caso peggiore e 2N-1 election + N leader.
L'anello logico non esiste nella rete fisica: e una sovrapposizione (superimposing) creata dall'algoritmo per organizzare il flusso dei messaggi. Questo e un pattern comune negli algoritmi distribuiti.
L'algoritmo di Chang-Roberts (1979) è elegante nella sua semplicità. Alla ricezione di (leader, j), un processo registra j come leader e inoltra il messaggio (se non è il leader stesso). È 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.
Un dettaglio importante riguarda i messaggi con ID minore del proprio: se il processo e gia awake, il messaggio viene semplicemente inghiottito (scartato), senza avviare una nuova candidatura.
flowchart LR
subgraph Anello PID
P1[P1] --> P2[P2]
P2 --> P3[P3]
P3 --> P4[P4]
P4 --> P1
end
P1 -.->|"election(1)"| P2
P2 -.->|"election(2)"| P3
P3 -.->|"election(3)"| P4
P4 -.->|"election(4) → leader(4)"| P1
Un esempio con PID non ordinati sull'anello: P2 avvia l'elezione, il suo messaggio viene rimpiazzato da quello di P7 (l'ID massimo), che fa il giro completo e torna al mittente.
graph LR
A[P2
id=2] -->|election,2| B[P7
id=7]
B -->|election,7| C[P3
id=3]
C -->|election,7| D[P1
id=1]
D -->|election,7| E[P5
id=5]
E -->|election,7| F[P4
id=4]
F -->|election,7| A
A -->|leader,7| B
B -->|leader,7| C
C -->|leader,7| D
D -->|leader,7| E
E -->|leader,7| F
F -->|leader,7| A
L'algoritmo usa l'anello logico solo per il controllo dell'elezione, non per il flusso dei dati applicativi. E un esempio classico di superimposing: sovrapporre un protocollo di coordinamento a una topologia fisica arbitraria. Questo pattern si ritrova in molti algoritmi distribuiti.
Esplora i possibili stati di un processo durante l'esecuzione dell'algoritmo di Chang-Roberts. Clicca sugli stati per vedere le transizioni possibili e la descrizione di ciascuno stato.
Lo pseudocodice dell'algoritmo e mostrato qui sotto. Ogni processo mantiene awake (se ha gia partecipato all'elezione) e leaderId (una volta eletto).
Nella computazione asincrona classica non ci sono restrizioni sull'ordine di ricezione dei messaggi. L'ordinamento causale e una restrizione utile: se send(m1) → send(m2) (l'invio di m1 precede causalmente l'invio di m2), allora vogliamo che rec(m1) → rec(m2) (la ricezione di m1 deve precedere la ricezione di m2). Nessun overtaking causale.
L'ordinamento FIFO e piu debole: garantisce solo che se lo stesso processo invia m1 prima di m2, allora m1 viene ricevuto prima di m2. L'ordinamento causale e piu forte: considera anche la causalita che attraversa processi diversi.
Immaginiamo tre processi P1, P2, P3. P1 invia un messaggio a P3, poi P1 invia un messaggio a P2. P2, dopo aver ricevuto il messaggio da P1, invia un messaggio a P3. Senza ordinamento causale, P3 potrebbe ricevere prima il messaggio di P2 e poi quello di P1, violando la causalita: l'invio di P1 a P3 e avvenuto prima dell'invio di P2 a P3, quindi dovrebbe essere ricevuto prima.
flowchart LR
subgraph P1
a1[send m1 to P3] --> a2[send m2 to P2]
end
subgraph P2
a2 --> b1[rec m2 from P1]
b1 --> b2[send m3 to P3]
end
subgraph P3
a1 -.-> c1[rec m1]
b2 -.-> c2[rec m3]
end
a1 --> c1
b2 --> c2
a2 --> b1
Nell'esempio: send(m1) → send(m3) perche send(m1) → rec(m2) → send(m3). Quindi vogliamo rec(m1) → rec(m3).
In un sistema completamente asincrono non ci sono restrizioni sull'ordinamento dei messaggi. Questo massimizza il nondeterminismo e la concorrenza, ma a volte e utile ridurre il nondeterminismo imponendo vincoli sull'ordinamento per semplificare la programmazione. Dal punto di vista del middleware, la verifica di eligibility avviene nel sistema di comunicazione: un messaggio non eligible viene messo in una coda di buffer e consegnato al processo solo quando lo diventa (perche altri messaggi sono arrivati e hanno aggiornato la matrice).
sequenceDiagram
participant A as P1
participant B as P2
participant C as P3
Note over A: m[1,2]++, send to P2
A->>B: msg1 (con matrice m)
Note over B: check eligibility:
m'[1,2] == m[1,2]+1?
se si: update, receive
Note over A: m[1,3]++, send to P3
A->>C: msg2 (con matrice m)
Note over B: P2 invia a P3
B->>C: msg3 (con matrice m')
Note over C: msg3 arriva prima di msg2?
Se send(msg2) -> send(msg3)
allora rec(msg2) -> rec(msg3)
Se msg3 arriva prima, buffer
C->>C: buffer msg3
aspetta msg2
A->>C: msg2 arriva (dopo)
Note over C: msg2 eligible? si
aggiorna matrice
controlla msg3 bufferizzato
ora msg3 eligible
C->>C: deliver msg3
L'algoritmo per garantire l'ordinamento causale estende il vector clock in una matrice di clock m di dimensione N×N, dove m[j,k] rappresenta il numero di messaggi inviati da Pj a Pk conosciuti da Pi nello stato corrente.
Quando un processo Pi invia un messaggio a Pj:
m[i,j] di 1m al messaggio (piggyback)Quando un processo Pi riceve un messaggio da Pj con matrice m':
m'[k,i] == m[k,i] (nessun messaggio da altri processi a Pi che il mittente conosce ma Pi non ha ancora ricevuto) e per k = j: m'[j,i] == m[j,i] + 1 (il messaggio corrente e l'unico atteso da Pj).m con m' (component-wise max) e procede con la ricezione.Il professore osserva che, nonostante la complessita della matrice, il principio e semplice: ogni processo guarda solo la propria colonna nella matrice ricevuta per decidere se ci sono messaggi pendenti da altri processi che devono essere ricevuti prima.
Il professore nota anche che se non ci fosse stato lo scambio di messaggi tra P1 e P2, gli eventi sarebbero stati concorrenti e non si sarebbe potuta ricostruire la catena causale. Tutto dipende dagli scambi di messaggi effettivi tra i processi.
Riassumendo la condizione di eleggibilità per un messaggio ricevuto da Pi da Pj con matrice m':
Non è consentito il «sorpasso causale»: se un messaggio è stato inviato prima (causalmente) di un altro, deve essere ricevuto prima.
Oltre all'ordinamento causale, esistono forme piu forti. L'ordinamento totale (sincrono) e piu restrittivo dell'ordinamento causale: richiede che tutti i messaggi possano essere trattati come logicamente istantanei. Nel caso di messaggi multicast, significa che tutti i messaggi vengono consegnati nello stesso ordine a tutti i processi. Per ogni coppia di messaggi x, y e per ogni coppia di processi P, Q: se x viene ricevuto da P prima di y, allora y non viene ricevuto da Q prima di x.
Progettare algoritmi distribuiti e piu facile assumendo una rete sincrona. I sincronizzatori permettono di simulare una rete sincrona su una asincrona, usando il meccanismo dei pulse (colpi): ogni processo ha un contatore pulse, e in ogni round i invia esattamente un messaggio a tutti i vicini con pulse = i, e attende un messaggio da ogni vicino con lo stesso pulse prima di avanzare al round successivo.
Pj::
var
pulse: integer := 0
round i:
pulse := pulse + 1
/* simula round i dell'algoritmo sincrono */
send msg to all neighbors with pulse
wait for exactly one msg from each neighbor with (pulse = i)Il costo di un sincronizzatore si misura in termini di messaggi aggiuntivi (message complexity) e di tempo aggiuntivo (time complexity) necessari per simulare un singolo pulse.
Il quadro completo delle garanzie di ordinamento comprende tre livelli. L'ordinamento FIFO e la forma piu debole: i messaggi inviati da uno stesso mittente a uno stesso destinatario vengono ricevuti nell'ordine di invio; molti middleware di messaggistica lo garantiscono per default. L'ordine totale richiede un coordinamento aggiuntivo e si basa su algoritmi come ISIS o su un sequencer centralizzato: e la base per i sistemi di replicated state machine.
Garanzia: i messaggi tra coppia (mittente, destinatario) arrivano in ordine di invio.
Costo: basso, spesso fornito dal protocollo di trasporto (TCP).
Limitazione: non dice nulla su messaggi da mittenti diversi o a destinatari diversi.
Garanzia: se invio di m1 precede causalmente invio di m2, allora m1 viene ricevuto prima di m2 ovunque.
Costo: matrice NxN di interi per processo. Buffer per messaggi non ancora eligible.
Utile per: applicazioni dove l'ordine causale e importante (es. aggiornamenti a un documento condiviso).
Garanzia: tutti i processi vedono tutti i messaggi multicast nello stesso ordine globale.
Costo: richiede un sequencer o un consenso distribuito.
Utile per: replicated state machine, database distribuiti, sistemi di consensus.
Catturare lo stato globale di un sistema distribuito e una sfida perche non esiste memoria condivisa. Uno stato globale e un insieme di stati locali che sono tutti concorrenti tra loro secondo la relazione happened-before. Per molte applicazioni e sufficiente catturare uno stato globale che e esistito nel passato, non necessariamente quello corrente.
Uno stato globale consistente non e semplicemente il prodotto cartesiano degli stati locali. Serve garantire che se un evento e = receive(msg) e e' = send(msg), allora se e' → e, deve valere che e' appartiene allo stato globale. Questa e la definizione di consistent cut.
Un taglio inconsistente si verifica quando registriamo la ricezione di un messaggio senza aver registrato anche il suo invio. Per esempio, se P1 invia un messaggio a P2, e nella nostra istantanea vediamo P2 che lo ha ricevuto ma P1 che non lo ha ancora inviato, la istantanea e inconsistente.
flowchart LR
subgraph P1
a1[e1] --> a2[e2]
a2 --> a3[e3]
end
subgraph P2
b1[e4] --> b2[e5]
b2 --> b3[e6]
end
a2 -. msg .-> b2
G1 (inconsistente): include e2, e3, e5, e6. G2 (consistente): include e1, e2, e4, e5. In G1, e5 (ricezione del messaggio) e incluso ma non e2 (invio). In G2, se il messaggio e inviato ma non ancora ricevuto, va considerato come "in transito" e incluso nello stato del canale.
Proposto da K. Mani Chandy e Leslie Lamport nel 1985, questo algoritmo permette di catturare uno snapshot globale consistente senza bloccare i processi, utilizzando un meccanismo a marker.
Assunzioni: tutti i canali sono unidirezionali e FIFO. Ogni processo ha un colore (bianco/rosso).
L'algoritmo funziona cosi:
Pi decide di avviare lo snapshot: salva il proprio stato locale, diventa rosso e invia un messaggio di marker su tutti i canali in uscita prima di inviare qualsiasi altro messaggio.chan[j].Grazie ai canali FIFO, nessun processo bianco riceve mai un messaggio inviato da un processo rosso. Questo garantisce che gli stati locali salvati siano mutuamente concorrenti (consistent cut).
Applicazioni degli snapshot includono: rilevamento deadlock, rilevamento terminazione, debug distribuito, checkpoint e recovery.
Un punto sottile: lo snapshot catturato corrisponde allo stato del sistema appena prima che i processi diventino rossi. Lo stato dei canali è dato dai messaggi inviati da processi bianchi e ricevuti da processi rossi: sono i messaggi in transito al momento dello snapshot.
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
L'algoritmo è usato per rilevamento di deadlock, terminazione e osservazione di predicati globali.
Chandy-Lamport e uno dei risultati piu importanti e influenti nel campo dei sistemi distribuiti, alla base di molte tecniche di debugging e checkpointing. Il primo esploratore segue il ciclo di vita del protocollo dal punto di vista dell'intero snapshot.
I canali FIFO garantiscono che nessun messaggio inviato da un processo white possa arrivare dopo il marker a un processo red. Questo assicura che gli stati locali catturati siano mutuamente concorrenti.
Il risultato e un'istantanea globale che corrisponde allo stato del sistema "subito prima che i processi diventassero rossi". Questa istantanea e consistente e puo essere usata per rilevare deadlock, terminare computazioni, o come checkpoint per il recovery.
Uno stato globale non e semplicemente il prodotto degli stati locali. Un taglio inconsistente (inconsistent cut) si verifica quando viene registrata la ricezione di un messaggio ma non la sua spedizione. Formalmente, un global state S e consistente se per ogni evento e = receive(msg), l'evento e' = send(msg) (dove e' → e) appartiene a S.
Il secondo esploratore segue invece il singolo processo, canale per canale:
Il consenso e uno dei problemi fondamentali del distributed computing: trovare un accordo tra processi distribuiti sul valore di una proprieta o su un'azione da compiere. E pervasivo nei sistemi reali: transazioni in DB (commit/abort), leader election, replicazione di state machine, atomic broadcast, clock synchronization, blockchain.
La definizione formale del problema richiede:
Pi parte in stato undecided e propone un valore vi.di ed entra in stato decided, senza piu poter cambiare idea.Le tre proprieta del consenso sono: termination (ogni processo corretto deve prima o poi settare la propria decision variable), agreement (tutti i processi corretti decidono lo stesso valore) e integrity (se tutti i processi corretti propongono lo stesso valore, quel valore deve essere la decisione; non si puo cambiare idea una volta deciso).
Molti problemi distribuiti sono riconducibili al consenso. Perfino la mutua esclusione puo essere vista come un problema di consenso: dobbiamo trovare un accordo su chi entra in sezione critica. I criteri possono essere diversi (primo che ha fatto richiesta, PID piu alto), ma il meccanismo di accordo e lo stesso.
In forma piu formale, i tre requisiti si esprimono cosi:
FLP (Fischer, Lynch, Patterson, 1985): in una rete asincrona, anche con un singolo processo che puo morire (crash non annunciato), il problema del consensus e impossibile da risolvere. Questo teorema di impossibilita ha profonde implicazioni pratiche: tutti i protocolli di consensus reali devono rilassare qualche assunzione, tipicamente introducendo sincronia o randomizzazione.
Per aggirare FLP, si assume un sistema sincrono (bound superiore sul ritardo dei messaggi e sulla durata delle azioni) e si definiscono modelli di guasto specifici. I modelli principali sono:
| Modello | Descrizione |
|---|---|
| Crash | Un processore si arresta (halt). Il guasto piu semplice da modellare |
| Crash+link | Un processore crasha oppure un link di rete cade e resta giu permanentemente |
| Omission | Un processo invia solo un sottoinsieme dei messaggi che dovrebbe inviare, o ne riceve solo un sottoinsieme |
| Byzantine | Un processore ha comportamento arbitrario: puo inviare messaggi contraddittori, valori falsi, o agire in modo malevolo. Il caso piu generale e difficile |
Il celebre risultato FLP (Fischer, Lynch, Patterson, 1985) dimostra che in una rete asincrona, in presenza anche di un solo processo che crasha in modo non annunciato, il problema del consenso e impossibile da risolvere. Questo perche non e possibile distinguere un processo lento da uno crashato.
Per risolvere il consenso si assume quindi un sistema sincrono, con un bound superiore sul ritardo dei messaggi e sulla durata delle azioni. L'algoritmo base procede a round:
f + 1 round, dove f e il numero massimo di processori che possono fallire.V.Numero di messaggi: O((f+1)N^2).
L'algoritmo base funziona solo in assenza di comportamenti byzantine. Se un processo puo inviare valori arbitrari o mentire, serve un algoritmo piu robusto.
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. Quando i guasti possono essere arbitrari (byzantine), serve N ≥ 3f+1 per tollerare f guasti bizantini.
Nel caso byzantine faults, i processi guasti possono avere comportamenti arbitrari: inviare valori sbagliati, contraddirsi, mentire deliberatamente. Il problema e noto come Byzantine General Agreement (BGA): generali leali (processi corretti) devono coordinarsi (decidere se attaccare o ritirarsi) nonostante la presenza di traditori (processi faulty).
Il teorema fondamentale: non esiste protocollo f-resiliente per BGA se N ≤ 3f, dove N = numero totale di processi, f = numero di processi faulty. In altre parole, serve almeno il 66.7% di processi corretti per tollerare guasti bizantini.
L'algoritmo opera in f + 1 round, con un coordinatore rotante (chiamato king) in ogni round. Almeno un round avra un king non faulty:
myvalue come maggioranza nel vettore V (o "non definito" se non c'e maggioranza).myvalue a tutti. Ogni processo, se il proprio vettore V ha piu di N/2 + f copie del proprio valore, mantiene il proprio valore; altrimenti adotta il valore del king.Questo garantisce che tutti i processi corretti convergano allo stesso valore finale nonostante la presenza di faulty processes.
Il diagramma seguente illustra la struttura a round dell'algoritmo base (crash-stop) con f = 1, quindi 2 round: dopo lo scambio completo, tutti i processi corretti hanno lo stesso insieme V e applicano la stessa funzione di decisione.
graph TD
subgraph "Round 1"
P1a[P1: V={v1}] -->|send v1| P2a[P2]
P1a -->|send v1| P3a[P3]
P2a[P2: V={v2}] -->|send v2| P1a
P2a -->|send v2| P3a
P3a[P3: V={v3}] -->|send v3| P1a
P3a -->|send v3| P2a
end
subgraph "Round 2 (f=1, rounds=2)"
P1b[P1: V={v1,v2,v3}] -->|send nuovi| P2b[P2]
P1b -->|send nuovi| P3b[P3]
P2b[P2: V={v1,v2,v3}] -->|send nuovi| P1b
P2b -->|send nuovi| P3b
P3b[P3: V={v1,v2,v3}] -->|send nuovi| P1b
P3b -->|send nuovi| P2b
end
subgraph "Decisione"
P1c[P1: decide(V)]
P2c[P2: decide(V)]
P3c[P3: decide(V)]
end
Il problema dei generali bizantini (Lamport, Shostak, Pease, 1982) e un classico: i generali leali devono decidere all'unisono se attaccare o ritirarsi nonostante la presenza di traditori che possono inviare messaggi contraddittori a destinatari diversi, o non inviare nulla.
Teorema BGA: non esiste un protocollo f-resilient per il Byzantine General Agreement se N ≤ 3f (N = numero totale di processi, f = guasti). Serve almeno 3f+1 processi per tollerare f guasti bizantini. Ad esempio, con 1 traditore servono almeno 4 generali; con 2 traditori almeno 7.
Il professore accenna a due famiglie di protocolli di consenso piu avanzati, che tipicamente vengono approfonditi in corsi successivi.
Paxos (Lamport, 1998) e una famiglia di protocolli per il consenso in reti con processori non affidabili, pensata per ambienti crash-stop (non bizantini). Offre vari trade-off tra numero di processori, ritardi di messaggio, livello di attivita dei partecipanti e tipi di fallimento tollerati. Ampiamente usato per la replica di file e database dove serve durabilita.
Raft (Ongaro e Ousterhout, 2013) e un algoritmo di consenso progettato per essere facile da capire rispetto a Paxos, pur essendo equivalente in termini di fault-tolerance e performance. Offre un modo generico per distribuire una state machine su un cluster di nodi. Il sito raft.github.io contiene implementazioni open-source in Go, C++, Java e Scala.
Il consenso emerge tipicamente nel contesto delle replicated state machine: ogni server ha una state machine e un log. La state machine e il componente che vogliamo rendere fault-tolerant (es. una hash table). L'algoritmo di consenso gestisce un log replicato contenente i comandi dei client. Le state machine processano sequenze identiche di comandi, producendo cosi le stesse uscite. Se una state machine applica il comando "set x to 3" come n-esimo comando, nessun'altra state machine applichera un n-esimo comando diverso.
flowchart LR
Client -->|"set x=3"| S1[Server 1]
Client -->|"set x=3"| S2[Server 2]
Client -->|"set x=3"| S3[Server 3]
subgraph Consensus
S1 --> L1[Log: set x=3]
S2 --> L2[Log: set x=3]
S3 --> L3[Log: set x=3]
end
L1 --> M1[State Machine: x=3]
L2 --> M2[State Machine: x=3]
L3 --> M3[State Machine: x=3]
Il nome deriva dall'articolo "The Part-Time Parliament" (Lamport, 1998), che presenta il consenso come un parlamento che legifera anche quando alcuni parlamentari sono assenti. Paxos bilancia diversi aspetti: numero di processori, ritardi di messaggio prima di apprendere il valore concordato, livello di attivita dei partecipanti, numero di messaggi scambiati, e tipi di guasto tollerati. E usato in tutti i contesti dove serve durabilita, come la replicazione di file o database.
Raft (Reliable, Replicated, Redundant, And Fault-Tolerant) e un algoritmo di consensus progettato per essere facile da capire. Equivalente a Paxos in fault-tolerance e performance, ma significativamente piu semplice da implementare. E utilizzato in progetti come etcd e Consul.
Proposto da Leslie Lamport nel 1998. Famiglia di protocolli, non un singolo algoritmo monolitico. Considerato storicamente il riferimento per il consensus in produzione, ma notoriamente difficile da comprendere e implementare correttamente. Il nome e la metafora del parlamento riflettono la complessita della presentazione originale.
Proposto da Diego Ongaro e John Ousterhout nel 2013. Progettato esplicitamente per l'insegnamento e la comprensione. Usa un leader forte, elezione del leader con timeout randomizzati, e una struttura a log piu chiara. E lo standard de facto per nuovi progetti che necessitano di consensus.
L'algoritmo di consensus coordina il log replicato: garantisce che se una state machine applica "set x to 3" come n-esimo comando, nessun'altra state machine nello stesso cluster applichera mai un comando diverso come n-esimo. Tutte eseguono la stessa identica sequenza di comandi, producendo gli stessi risultati e arrivando agli stessi stati.
graph LR
Client -->|"set x=3, get y, ..."| LB[Load Balancer]
LB --> SM1[Server 1
State Machine
Log: [set x=3,...]]
LB --> SM2[Server 2
State Machine
Log: [set x=3,...]]
LB --> SM3[Server 3
State Machine
Log: [set x=3,...]]
Consensus[Consensus Module
Raft / Paxos] -.-> SM1
Consensus -.-> SM2
Consensus -.-> SM3
SM1 -.->|replica log| Consensus
SM2 -.->|replica log| Consensus
SM3 -.->|replica log| Consensus
Il sistema appare ai client come un'unica state machine affidabile, anche se una minoranza dei server nel cluster fallisce. Questo pattern e alla base di sistemi come Google File System (GFS), HDFS, RAMCloud, e innumerevoli database distribuiti.
FLP dimostra che non esiste un algoritmo di consenso deterministico che sia contemporaneamente: tollerante a un singolo crash, funzionante in rete asincrona, e garantito terminare sempre. Almeno una di queste tre condizioni va rilassata — ed e esattamente cio che fanno Paxos e Raft con le loro assunzioni di sincronia parziale.
In Raft il flusso e guidato da un leader forte: il client invia il comando al leader, che lo replica ai follower tramite AppendEntries e conferma il commit una volta raggiunta la maggioranza.
flowchart TD
Client -->|"set x=3"| Leader[Leader]
subgraph Raft Cluster
Leader -->|"AppendEntries"| F1[Follower]
Leader -->|"AppendEntries"| F2[Follower]
Leader -->|"AppendEntries"| F3[Follower]
end
F1 -->|"ACK"| Leader
F2 -->|"ACK"| Leader
F3 -->|"ACK"| Leader
Leader -->|"commit x=3"| Client
Se un server fallisce, la macchina a stati continua a funzionare sugli altri. Questa architettura e alla base di molti sistemi fault-tolerant: GFS, HDFS, RAMCloud, Chubby, ZooKeeper, etcd.
Il professore ha menzionato Paxos e Raft come "further explorations". Il risultato di FLP, le proprieta del consenso e la differenza tra crash-stop e byzantine sono argomenti chiave per l'esame.
La fama di Paxos come algoritmo difficile da comprendere ha portato allo sviluppo di Raft.
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.
Testa la tua comprensione degli algoritmi distribuiti con queste domande. Clicca su ogni domanda per vedere la risposta.
Safety: mai due processi contemporaneamente in CS. Liveness: ogni richiesta prima o poi viene concessa. Fairness: le richieste vengono servite nell'ordine della relazione happened-before.
Usando i vector clock trasportati dalle richieste (piggyback vector). Il coordinatore valuta l'eligibility di una richiesta w confrontando w.v con il proprio reqDone: una richiesta e eligible solo se non ci sono richieste accadute prima di w che non sono state ancora soddisfatte. Se una richiesta arriva in ritardo, il coordinatore la ritarda fintanto che non arrivano tutte quelle che la precedono causalmente.
2(N-1) messaggi: (N-1) richieste inviate a tutti gli altri processi + (N-1) OK ricevuti. Non ci sono messaggi superflui.
Quando riceve un messaggio election con ID uguale al proprio (j == myid), significa che il suo messaggio iniziale ha fatto tutto il giro dell'anello ed e tornato indietro perche nessun altro aveva un ID piu alto. A quel punto si autoproclama leader e propaga un messaggio leader.
In una rete asincrona, anche con un singolo processo che crasha in modo non annunciato, il consenso e impossibile da risolvere. Questo perche non si puo distinguere un processo lento da uno crashato. Per risolvere il consenso serve un'ipotesi di sincronia (con timeout).
Il teorema BGA dice che N deve essere maggiore di 3f (quindi almeno 3f + 1). In altre parole, servono almeno il 66.7% di processi corretti per tollerare guasti bizantini.
Un consistent cut e un insieme di stati locali dove per ogni evento receive(m) incluso, anche l'evento send(m) corrispondente e incluso (a meno che accada dopo il taglio e il messaggio sia considerato in transito). E importante perche garantisce che lo snapshot globale rappresenti uno stato che e effettivamente esistito nel sistema, senza paradossi temporali come messaggi ricevuti ma mai inviati.
Garantiscono che nessun processo bianco riceva mai un messaggio inviato da un processo rosso. Questo e fondamentale per assicurare che gli stati locali salvati siano mutuamente concorrenti (consistent cut): quando un processo diventa rosso dopo aver ricevuto un marker, tutti i messaggi successivi che ricevera saranno da mittenti rossi.
L'orologio logico (Lamport) assegna un singolo numero a ogni evento e soddisfa: se a → b allora C(a) < C(b), ma non viceversa. Il vector clock usa un array di N contatori e soddisfa: a → b se e solo se VC(a) < VC(b), permettendo cosi di determinare con precisione se due eventi sono in relazione causale o concorrenti.
Perche molti problemi si riconducono a un problema di consenso: mutua esclusione (chi entra in CS?), leader election (chi e il leader?), atomic broadcast, transazioni distribuite, blockchain, clock synchronization. Una volta risolto il consenso, si ha uno strumento generale per risolvere un'intera classe di problemi di coordinazione distribuita.
Assenza di clock condiviso (non si possono sincronizzare orologi fisici), assenza di memoria condivisa (nessun processo conosce lo stato globale), assenza di rilevamento accurato dei guasti (in un sistema asincrono non si distingue tra processo lento e processo caduto).
w e eleggibile se w.v e "al massimo" uguale a reqDone: per ogni j diverso da w.p si ha w.v[j] == reqDone[j], e per j == w.p si ha w.v[j] == reqDone[j] + 1. Questo significa che non esistono richieste accadute prima di w che non sono ancora state soddisfatte.
N > 3f, dove N e il numero totale di processi e f e il numero di processi guasti con comportamento arbitrario. Se N ≤ 3f, non esiste alcun protocollo f-resilient. Ad esempio, per tollerare 1 guasto bizantino servono almeno 4 processi.
L'ordinamento causale e piu forte del FIFO: dati due messaggi m1, m2 tali che send(m1) → send(m2), allora rec(m1) → rec(m2). Il FIFO garantisce solo l'ordine all'interno dello stesso processo mittente, mentre l'ordinamento causale vieta i sorpassi (overtaking) anche tra processi diversi.
Un sistema distribuito con dati condivisi puo garantire al massimo due delle tre proprieta: Consistency (tutti vedono gli stessi dati), Availability (ogni richiesta riceve risposta), Partition tolerance (funziona nonostante partizioni di rete). La scelta dipende dai requisiti applicativi.
RMI e basato su distributed object computing: chiamate a metodo sincrone, proxy/stub, trasparenza oggettuale, invocazione di metodi su oggetti remoti. Un MOM (es. RabbitMQ) e basato su messaggi asincroni, code, pubblicazione/sottoscrizione, disaccoppiamento temporale e spaziale. RMI e orientato agli oggetti; i MOM sono orientati ai messaggi.
Ogni processo ha un colore (bianco/rosso). Tutti iniziano bianchi. Quando un processo decide di fare lo snapshot (o riceve un marker), salva lo stato locale, diventa rosso, e invia marker su tutti i canali in uscita. I messaggi inviati da processi bianchi e ricevuti da processi rossi costituiscono lo stato dei canali. Canali FIFO garantiscono che nessun processo bianco riceva messaggi da processi rossi, assicurando che gli stati locali siano mutuamente concorrenti (consistent cut).