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 questa lezione 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 |
Le categorie principali di algoritmi distribuiti includono: ordinamento eventi (clock logici, vector clock), osservazione dello stato (snapshot globali), coordinazione e accordo (mutua esclusione, elezione, multicast, consenso), transazioni distribuite e replica.
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
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]
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 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.
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).
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.
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.
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.
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.
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.
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 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]
Questa lezione fa riferimento anche ai modelli di computazione distribuita introdotti nel modulo 4.1. Sono il fondamento su cui poggiano tutti gli algoritmi distribuiti discussi.
| Modello | Relazione tra eventi | Utilizzo |
|---|---|---|
| Interleaving | Ordine totale globale | Verifica di proprieta |
| Happened-before (→) | Ordine parziale: processi totalmente ordinati, causalita tra messaggi | Osservazione del comportamento |
| Potential causality (→p) | Ordine parziale anche all'interno dello stesso processo | Debugging distribuito |
L'orologio logico assegna un numero crescente a ogni evento, soddisfacendo: se a → b, allora C(a) < C(b). Non vale il viceversa: C(a) < C(b) non implica a → b. Implementazione: ogni processo incrementa un contatore C tra due eventi consecutivi; sui messaggi si allega il timestamp corrente; al ricevimento si aggiorna C a max(C, Tm) e poi si incrementa.
Il limite degli orologi logici e che non permettono di determinare se due eventi sono concorrenti o in relazione causale. A questo serve il vector clock.
Il vector clock estende l'orologio logico usando un array di N contatori: VC(a) < VC(b) se e solo se a → b. Questo permette di determinare con precisione la relazione causale tra due eventi qualsiasi. La regola di aggiornamento e simile: incremento del componente proprio tra eventi successivi, piggyback del vettore sui messaggi, e componente-wise max al ricevimento.
/* Regole del vector clock */
Pi::
V[i] := V[i] + 1 /* tra eventi successivi */
/* send(m): piggyback V con il messaggio */
/* receive(m): */
for k in 1..N:
V[k] := max(V[k], msg.V[k])I vector clock sono usati dall'algoritmo centralizzato di mutua esclusione, e la loro generalizzazione (matrice di clock) e alla base dell'ordinamento causale.
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.