Attori, Timer, Cluster e Algoritmi Distribuiti

1. Timer in Akka: Behaviors.withTimers

La lezione di oggi inizia con un argomento pratico: i timer in Akka. Nella lezione precedente avevamo introdotto il modello actor e l'API base di Akka Typed, ma non avevamo fatto in tempo a parlare di come un attore possa compiere azioni in modo proattivo, non solo reagendo a messaggi ricevuti. L'attore puramente reattivo resta in attesa di un messaggio; se nessuno gli scrive, rimane bloccato. I timer risolvono questo problema: permettono a un attore di "svegliarsi" periodicamente o dopo un certo intervallo per compiere un'azione.

Il costruttore fondamentale e Behaviors.withTimers. Questo factory method prende una funzione che riceve due parametri: il context dell'attore (come abbiamo visto nelle lezioni precedenti) e un oggetto timers di tipo TimerScheduler. Quest'ultimo e l'interfaccia attraverso cui programmiamo l'invio di messaggi futuri.

Ecco il codice mostrato a lezione: un attore che, una volta avviato, si autoschedula per ricevere un messaggio TIC ogni secondo.

L'idea centrale e che timerScheduler.startTimerAtFixedRate fa si che l'attore riceva automaticamente il messaggio TIC ogni intervallo specificato (nel caso del professore, 1 secondo). Il timer continua all'infinito fino a quando non viene cancellato esplicitamente o l'attore viene fermato.

Timer e contesto applicativo

Questo pattern e estremamente comune in molte applicazioni: heartbeats, polling periodico, timeout per richieste, refresh di cache, scheduling di job ricorrenti. Nel contesto dell'assignment del corso, il professore ha sottolineato che i timer saranno molto probabilmente necessari.

2. startSingleTimer, FixedRate e strategie di scheduling

Il TimerScheduler offre diverse varianti del metodo di scheduling, ciascuna pensata per un caso d'uso specifico:

Il parametro key: perche serve

Un aspetto importante emerso dalla lezione e il parametro key. La key e un Any: puo essere qualsiasi oggetto, e serve a disambiguare timer diversi. Se avete lo stesso identico messaggio da mandare ma volete due timer indipendenti, usate due chiavi diverse. In questo modo l'attore sa gestire piu timer concorrenti, ciascuno con la propria periodicita o scadenza. La key permette anche di cancellare selettivamente un timer: timers.cancel(chiave).

flowchart LR
    subgraph Attore
        SM[TimerScheduler]
        MB[Message Queue]
        BH[Behavior]
    end
    SM -->|"startSingleTimer(k,msg,d)"| T1[Timer k: scatta dopo d]
    SM -->|"startTimerAtFixedRate(k,msg,i)"| T2[Timer k: tic ogni i]
    T1 -->|scaduto| MB
    T2 -->|scaduto| MB
    MB --> BH

3. Stash e Timer: la combinazione vincente

Il professore ha dedicato un passaggio importante alla combinazione di stash e timer. Lo stash, introdotto nella lezione precedente, permette di accodare messaggi ricevuti mentre l'attore si trova in uno stato transitorio (ad esempio in attesa di una risposta), per poi riprocessarli in seguito con unstashAll.

La combinazione con i timer e particolarmente utile per gestire timeout nelle conversazioni. Supponiamo che un attore A invii una richiesta a un attore B e si metta in attesa della risposta. Durante l'attesa, A usa lo stash per accumulare gli altri messaggi. Con un timer singolo, A puo anche gestire il caso in cui B non risponda entro un certo tempo: allo scadere del timer, A puo decidere se riprovare, fallire, o tornare allo stato normale e processare i messaggi accumulati.

// Pattern: attore che attende una risposta con timeout e stash
Behaviors.withTimers { (ctx, timers) =>
  Behaviors.withStash(100) { stash =>
    Behaviors.receiveMessage {
      case Richiesta(destinatario, payload) =>
        destinatario ! Esegui(payload, ctx.self)
        timers.startSingleTimer("timeout", TimeoutScattato, 5.second)
        Behaviors.receiveMessage {
          case RisultatoOk(data) =>
            timers.cancel("timeout")
            stash.unstashAll(comportamentoNormale(data))
          case TimeoutScattato =>
            stash.unstashAll(comportamentoFallito)
          case altro =>
            stash.stash(altro)
            Behaviors.same
        }
    }
  }
}

Nel pattern qui sopra, l'attore cambia behavior in attesa della risposta. Tutti i messaggi che arrivano durante l'attesa vengono stashati. Se arriva RisultatoOk, il timer viene cancellato e i messaggi accumulati vengono riprocessati. Se scatta il timeout, si passa a un behavior di fallimento e anch'esso processa i messaggi accumulati.

4. Dal singolo nodo al cluster: membership e gossip

Dopo la parte introduttiva sui timer, il professore ha dedicato il nucleo centrale della lezione agli aspetti distribuiti di Akka. Passare da un singolo actor system locale a un cluster di piu nodi introduce complessita sostanziali: i nodi possono unirsi o lasciare il cluster, possono fallire senza preavviso, la rete puo partizionarsi. Akka gestisce tutto questo con un meccanismo di membership basato su gossip protocol.

Seed nodes e bootstrap

Quando un nuovo nodo vuole unirsi al cluster, deve contattare uno o piu seed nodes. I seed sono nodi noti (tipicamente configurati tramite DNS o file di configurazione) che fungono da punti di contatto iniziali. Il professore ha mostrato due modalita:

• Manual join: il nodo invia un messaggio esplicito di Join al seed node, che lo inserisce nel cluster.
• Join with seed nodes: una configurazione piu robusta in cui il nodo contatta automaticamente i seed.

I seed node sono consapevoli l'uno dell'altro: quando un seed si avvia, fa join del cluster da solo (oppure si mette in ascolto). In un setup Docker Compose (come quello preparato dal professore), i seed vengono referenziati tramite nome del servizio DNS interno.

Gossip protocol

Una volta che il cluster e formato, i nodi comunicano tra loro usando un gossip protocol per scambiarsi informazioni sullo stato del cluster: quali nodi sono vivi, quali sono morti, qual e lo stato corrente della membership. Il gossip e un protocollo epidemico: ogni nodo periodicamente condivide con un sottoinsieme di altri nodi tutto cio che sa. Con il tempo, l'informazione si propaga a tutto il cluster. Questo meccanismo e alla base del failure detection: se un nodo smette di fare gossip, gli altri lo marcano come unreachable.

flowchart TD
    subgraph Cluster Akka
        N1[Nodo 1] --- N2[Nodo 2]
        N2 --- N3[Nodo 3]
        N3 --- N4[Nodo 4]
        N1 -.- N4
    end
    S1[Seed 1:2552] --> N1
    S2[Seed 2:2553] --> N2
    SN[Nuovo Nodo] -->|join| S1
    SN -->|gossip| N2
    SN -->|gossip| N3

5. Split-brain resilience e partizionamento

Uno dei problemi piu insidiosi nei cluster distribuiti e lo split-brain: quando un nodo o un gruppo di nodi non riesce piu a comunicare con un'altra parte del cluster a causa di un guasto di rete, si creano due (o piu) partizioni che non si parlano. Dal punto di vista di ciascuna partizione, l'altra sembra "morta".

Il problema della consistenza

Se entrambe le partizioni continuano a operare indipendentemente, e poi la rete viene ripristinata, ci si trova con due stati divergenti dello stesso sistema. Questo e particolarmente grave se ci sono attori persistenti con stato: quale dei due stati va mantenuto? Non e banale, anzi a volte non si saprebbe neppure come scegliere.

Strategie di risoluzione

Akka implementa la strategia della partizione piu numerosa: il sottocluster con il maggior numero di nodi sopravvive, mentre l'altro viene spento. Ma cosa succede in caso di parita (es. 2-2 su 4 nodi)? Il professore ha spiegato che esiste un meccanismo di tie-breaking che rompe la simmetria, basato su un ordinamento deterministico (es. indirizzi dei nodi). In questo modo solo una delle due partizioni sopravvive.

Il detection della partizione funziona perche il gossip protocol mantiene in ogni nodo la consapevolezza di quanti nodi ci sono nel cluster totale. Quando un nodo si accorge di poter comunicare solo con un sottoinsieme, capisce di essere in una partizione e applica la strategia di downing.

6. Comunicazione remota: ActorRef, path e serializzazione

In un contesto distribuito, gli attori comunicano sempre attraverso ActorRef, esattamente come in un contesto locale. La differenza e che l'ActorRef puo referenziare un attore che vive su un nodo diverso: quando inviamo un messaggio a quel ref, il sistema si occupa di serializzare il messaggio e spedirlo sulla rete al nodo giusto.

Come ottenere un ActorRef remoto

Il professore ha elencato tre modi per ottenere un ActorRef di un attore su un nodo remoto:

1. Incluso in un messaggio: un attore puo inviare il proprio ctx.self a un attore remoto, che cosi ottiene un ref per rispondere. Questo e il modo piu comune.
2. Tramite path: se si conosce il path assoluto dell'attore (es. akka://system@host:port/user/actorName), si puo chiedere al sistema di risolverlo. Tuttavia questo approccio e fragile perche il path puo cambiare.
3. Tramite receptionist: il meccanismo consigliato per il bootstrap, che vedremo nella prossima sezione.

Serializzazione

Quando si invia un messaggio attraverso la rete, e necessario serializzarlo. Akka utilizza di default Jackson JSON per la serializzazione. Questo significa che tutti i messaggi scambiati tra attori in contesto distribuito devono essere (direttamente o indirettamente) serializzabili in JSON. Il professore ha accennato che non c'e molto altro da sapere se non che i messaggi custom vanno annotati o configurati per essere serializzabili correttamente.

7. Receptionist: service discovery nel cluster

Il receptionist e un attore di sistema che funge da registry distribuito: permette agli attori di registrarsi sotto una service key e ad altri attori di scoprirli. E la soluzione consigliata per il bootstrapping della comunicazione in un cluster Akka.

register, find e subscribe

Il receptionist offre tre operazioni fondamentali:

• Register: un attore si registra con una chiave. Il receptionist associa l'ActorRef dell'attore a quella chiave.
• Find: richiede una istantanea (snapshot) degli attori attualmente registrati per una data chiave. Utile quando il set degli attori e stabile.
• Subscribe: si sottoscrive per ricevere notifiche ogni volta che un attore si registra o si deregistra per quella chiave. Utile quando il set e dinamico.

Il professore ha enfatizzato la differenza tra find e subscribe: la find da una risposta una tantum, mentre la subscribe continua a notificare l'attore ogni volta che ci sono cambiamenti. La scelta dipende dal caso d'uso. Nell'esempio mostrato a lezione, un attore manager usa subscribe per ricevere notifiche man mano che i worker si registrano (visto che i worker potrebbero non essere ancora partiti al momento della subscribe).

Ecco il pattern mostrato dal professore:

// Registrazione (lato worker)
ctx.system.receptionist ! Receptionist.Register(WorkerServiceKey, ctx.self)

// Sottoscrizione (lato manager)
ctx.system.receptionist ! Receptionist.Subscribe(WorkerServiceKey, ctx.self)

// L'attore manager gestisce Listing per ottenere i worker
Behaviors.receiveMessage {
  case WorkerServiceKey.Listing(actors) =>
    // actors contiene la lista aggiornata dei worker
    comportamentoAttivo(actors)
  // ...
}

8. Cluster sharding: distribuire attori su piu nodi

Il cluster sharding e il meccanismo che permette di distribuire un insieme di attori (detti entities) attraverso i nodi del cluster in modo trasparente. E ideale per attori con identita univoca (es. un attore per ogni utente, per ogni sessione, per ogni conto corrente) dove non ci interessa su quale nodo l'attore vive, ma vogliamo che ci sia una distribuzione bilanciata.

L'esempio del contatore

Il professore ha mostrato un esempio semplice: un attore Counter che mantiene un contatore interno e risponde a messaggi Increment e GetValue. Lo scopo e creare piu istanze di Counter distribuite automaticamente nel cluster.

Per usare lo sharding:

1. Si definisce una Sharding con una EntityTypeKey che identifica il protocollo (i messaggi che l'attore sa gestire).
2. Si inizializza il ClusterSharding con l'entity factory (come creare l'attore quando serve).
3. Per parlare con un attore shardato, si usa una EntityRef ottenuta con sharding.entityRefFor(typeKey, entityId).
4. L'entityId determina su quale shard (e quindi su quale nodo) l'attore viene creato.

// Inizializzazione dello sharding
val sharding = ClusterSharding(system)
val counterTypeKey = EntityTypeKey[Counter.Command]("counter")

val shard = sharding.init(
  Entity(counterTypeKey, createBehavior = ctx => Counter())
)

// Ottenere un EntityRef e inviare un messaggio
val counter = sharding.entityRefFor(counterTypeKey, entityId = Random.nextInt(3).toString)
counter ! Counter.Increment

In questo esempio, l'entityId e un numero casuale tra 1 e 3: questo fa si che gli attori counter vengano distribuiti su diversi nodi del cluster (in base alla funzione di hash dell'entityId). Il professore ha mostrato in diretta i log che evidenziano come i vari counter vengono creati su nodi diversi.

9. Il modello Actor: fondamenti teorici

Dopo la parte pratica su Akka Cluster, il professore ha spostato l'attenzione sulle basi teoriche del modello Actor, attingendo al modulo 3.2 del corso. Il modello Actor e stato originariamente introdotto da Carl Hewitt e colleghi al MIT negli anni '70, in un contesto di ricerca sull'Intelligenza Artificiale. Successivamente, Gul Agha e Akinori Yonezawa negli anni '80 e '90 lo hanno sviluppato come unificazione tra OOP e concorrenza (Concurrent Object-Oriented Programming).

L'idea fondante

Il modello Actor e una teoria matematica che tratta gli attori come i primitivi universali della computazione concorrente digitale. L'idea centrale e che tutto e un attore: ogni entita computazionale e un attore con un identificatore univoco e una mailbox (coda di messaggi). Ogni interazione avviene esclusivamente tramite scambio asincrono di messaggi. Questo e fortemente legato all'idea originale di OOP di Alan Kay, dove il punto fondamentale era il message passing.

Attori nel mainstream moderno

Nonostante le origini accademiche, il modello Actor ha trovato ampia adozione industriale: Erlang (telecomunicazioni), Akka/Scala (JVM), HTML5 Web Workers, Dart isolates. E considerato un'alternativa valida al multithreading tradizionale per costruire sistemi concorrenti scalabili.

flowchart LR
    A1[Attore 1] -->|send msg| A2[Attore 2]
    A2 -->|send reply| A1
    A1 -->|create| A3[Attore 3]
    A3 -->|become| A3'

1. 1973 Hewitt introduce il modello Actor in "A Universal Modular ACTOR Formalism"
2. 1977 "Viewing Control Structures as Patterns of Passing Messages"
3. 1986 Agha formalizza il modello nel libro "Actors: A Model of Concurrent Computation in Distributed Systems"
4. 1987 Nasce Erlang in Ericsson per applicazioni di telecomunicazione
5. 1990 "Concurrent Object-Oriented Programming" di Agha e Yonezawa
6. 2009 Akka: framework actor industrial-grade per JVM
7. 2010s Actor model adottato in Web Workers, Dart, e sistemi cloud-native

10. Primitive e semantica: send, create, become, macro-step

Le tre primitive fondamentali

Il comportamento di un attore si compone utilizzando solo tre primitive (azioni):

Send e per la programmazione concorrente cio che l'invocazione di procedura e per la programmazione sequenziale: il mattoncino fondamentale. Create e l'analogo dell'astrazione di procedura: permette di definire nuovi attori. Become permette all'attore di cambiare il proprio comportamento (e quindi il proprio stato locale) per il messaggio successivo, dando agli attori una history-sensitive behaviour necessaria per oggetti mutabili condivisi.

Semantica macro-step (run-to-completion)

Uno degli aspetti piu importanti del modello Actor e la semantica macro-step o run-to-completion: un attore, quando riceve un messaggio, esegue il corrispondente handler nella sua interezza prima di passare al messaggio successivo. Questo evita race condition e semplifica il ragionamento sui programmi. Tuttavia, il professore ha sottolineato che questo complica la programmazione: nasce il problema dell'asynchronous spaghetti che vedremo piu avanti.

Altre proprieta chiave

• State encapsulation: un attore non puo accedere direttamente allo stato interno di un altro attore.
• Fairness: un messaggio inviato a un attore viene prima o poi recapitato e processato.
• Location transparency: per inviare un messaggio a un attore non serve sapere dove si trova fisicamente, basta la sua identita.
• No ordering guarantees: non si puo assumere alcun ordinamento tra messaggi ricevuti, neppure se inviati dallo stesso mittente in sequenza.

11. Attori in pratica: Erlang, Akka, ActorFoundry

Il modello Actor e stato implementato in molti linguaggi e framework. Le slides del professore confrontano tre implementazioni significative: Erlang (linguaggio nativo), Akka (framework JVM), e ActorFoundry (framework accademico Java).

counter(Sum) ->
    receive
        {inc} ->
            counter(Sum + 1);
        {getValue, Pid} ->
            Pid ! {count_value, Sum},
            counter(Sum)
    end.

public class MyUntypedActor extends UntypedActor {
    LoggingAdapter log = Logging.getLogger(getContext().system(), this);
    public void onReceive(Object message) throws Exception {
        if (message instanceof String) {
            log.info("Received String message: {}", message);
            getSender().tell("received");
        } else unhandled(message);
    }
}

public class PingActor extends Actor {
    ActorName otherPinger;
    @message
    public void start(ActorName other) {
        otherPinger = other;
        send(otherPinger, "ping", self(), "...");
    }
}

Explicit vs Implicit receive

Una differenza fondamentale tra i framework e come gestiscono il message loop:

• Implicit receive (Akka, ActorFoundry): il loop di ricezione dei messaggi e nascosto all'interno del framework. Il programmatore definisce solo gli handler. Cio e semplice ma porta all'async spaghetti.
• Explicit receive (Erlang): il programmatore scrive esplicitamente il loop receive ... end. Piu flessibile ma anche piu verboso. Supporta la selective receive con guardie.

12. Asynchronous spaghetti, stashing e pattern di messaggistica

Il problema dell'asynchronous spaghetti

Con la semantica macro-step (un messaggio alla volta, run-to-completion), la logica applicativa viene spezzata in una serie di handler (o callback) non strutturati, ciascuno dei quali reagisce a un evento diverso. Questo e il problema dell'asynchronous spaghetti citato dal professore rifacendosi a [RS-12].

Esempio dalle slide: un attore deve valutare l'espressione sin(x)*cos(y) delegando i calcoli a due attori specializzati (sinActor e cosActor). Con la semantica macro-step, l'attore principale deve:

1. Inviare x a sinActor e y a cosActor.
2. Ricevere il risultato da sinActor (handler 1).
3. Ricevere il risultato da cosActor (handler 2).
4. Moltiplicare i due risultati (handler 3).

La logica e spezzata in tre handler separati, senza una struttura sequenziale evidente. La soluzione moderna sono i Future/Promise pipelines.

Stashing come soluzione Akka

Akka introduce lo stash come meccanismo per gestire messaggi che arrivano in momenti inappropriati. Lo stash e una coda implicita separata dalla mailbox principale:

• stash(): accoda il messaggio corrente nello stash.
• unstashAll(): re-inserisce tutti i messaggi stashati nella mailbox principale.

Il pattern classico e: in uno stato transitorio, i messaggi non gestibili vengono stashati; quando si arriva allo stato giusto (o scade un timer), si fa unstashAll() e si riprocessano.

// Pattern Akka: stash per gestire un protocollo a stati
Behaviors.receive { (ctx, msg) =>
  msg match {
    case "open" =>
      unstashAll()
      Behaviors.receiveMessage {
        case "write" => // scrivi...
        case "close" =>
          unstashAll()
          context.unbecome()
        case _ => stash()
      }
    case _ => stash()
  }
}

Futures e messaggistica RPC-like

Il pattern Future e un idioms ricorrente: un attore-future fa da proxy per un risultato non ancora disponibile. Quando il valore viene calcolato, il future notifica tutti gli attori in attesa. Questo pattern e alla base della comunicazione RPC-like nel modello actor.

Altri pattern importanti menzionati nelle slide: Serializer, Fork-Join, e i vari Messaging Patterns da [VER16] (Message Channel, Publish-Subscribe, Command Message, Message Router, Content-based Filter, ecc.).

13. Mutua esclusione centralizzata con coordinator

Il professore apre la seconda parte della lezione (modulo 4.2) introducendo i principali algoritmi distribuiti. Il primo problema affrontato e la mutua esclusione in ambiente distribuito, analogo al problema concorrente classico ma con processi che non condividono memoria ne clock.

Proprieta della sezione critica distribuita

• Safety: due processi non devono mai avere il permesso di entrare in CS contemporaneamente.
• Liveness: ogni richiesta di CS viene prima o poi concessa.
• Fairness: le richieste devono essere servite nell'ordine in cui sono state fatte (secondo la relazione happened-before).

Algoritmo centralizzato

Esiste un coordinatore (P0) che detiene il token. I processi client inviano richieste al coordinatore, che concede il token quando la richiesta e eligible.

La parte complessa e garantire la fairness. Poiche le richieste possono arrivare in ordine diverso dall'ordine causale, ogni processo include il proprio vector clock v nella richiesta. Il coordinatore mantiene due strutture dati:

• reqList: lista delle richieste ricevute ma non ancora soddisfatte.
• reqDone: array che conta quante richieste di ogni processo sono state soddisfatte.

Una richiesta w e eligible se per ogni processo j, il valore w.v[j] e uguale a reqDone[j] (oppure reqDone[j] + 1 se j == w.p). In pratica: non ci sono richieste accadute prima di w che non sono state ancora soddisfatte.

14. Ricart-Agrawala: mutua esclusione decentralizzata

L'algoritmo di Ricart-Agrawala (1981) e una soluzione decentralizzata: non esiste un coordinatore centrale. Ogni processo partecipa alla decisione scambiando messaggi timestampati. L'algoritmo richiede 2(N-1) messaggi per ogni accesso alla CS.

L'idea

1. Per richiedere la CS, un processo Pi imposta myts al proprio clock logico e invia un messaggio (req, myts) a tutti gli altri processi.
2. Alla ricezione di una richiesta da Pj, un processo Pi risponde con OK se:
   • non e interessato a entrare in CS (myts == infinity), oppure
   • la propria richiesta ha timestamp maggiore (quindi e successiva).
   Altrimenti, accoda Pj nella propria pendingQ.
3. Un processo ottiene la CS quando ha ricevuto OK da tutti gli altri processi.
4. Nel rilasciare la CS, invia OK a tutti i processi in pendingQ e resetta myts a infinity.

L'algoritmo funziona anche con canali non FIFO, perche l'ordinamento e garantito dai timestamp. La fairness e assicurata dalla relazione d'ordine sui timestamp (a parita di timestamp, vince il PID piu basso).

15. Leader election: Chang-Roberts

Il problema dell'elezione del leader si pone quando un gruppo di processi distribuiti deve scegliere un coordinatore comune. L'algoritmo di Chang-Roberts assume che i processi siano disposti su un anello logico (sovrapposto alla rete fisica) e che ogni processo abbia un PID univoco.

Funzionamento

L'idea e semplice: il processo con il PID piu alto viene eletto leader. L'algoritmo funziona cosi:

1. Uno o piu processi possono svegliarsi spontaneamente e iniziare un'elezione.
2. Un processo che si sveglia invia un messaggio (election, myId) al vicino sinistro sull'anello e si marca come awake.
3. Alla ricezione di un messaggio di elezione:
   • Se j > myid: inoltra il messaggio (il candidato e piu forte).
   • Se j == myid: il messaggio ha fatto tutto il giro e sono io il leader: invio (leader, myid).
   • Se j < myid e non sono ancora awake: inizio una nuova elezione con il mio ID.
   • Se j < myid e sono gia awake: inghiotto il messaggio (lo scarto).
4. Alla ricezione di (leader, j): salvo il leader e inoltro il messaggio (se non sono io il leader).

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

Complessita: nel caso peggiore, l'elezione richiede 2N-1 messaggi di elezione e N messaggi di leader propagation. L'algoritmo e utilizzato in pratica per eleggere coordinatori in algoritmi centralizzati (il coordinatore della mutua esclusione, ad esempio).

16. Chandy-Lamport: global snapshot

L'algoritmo di Chandy-Lamport (1985) permette di catturare una istantanea globale consistente di un sistema distribuito, senza fermare i processi e senza perdere messaggi in transito. E uno dei risultati piu importanti e influenti nel campo dei sistemi distribuiti, alla base di molte tecniche di debugging e checkpointing.

Consistent cut

Un taglio consistente (consistent cut) e un insieme di eventi che rispetta la relazione di causalita: se un evento e' (send) precede causalmente e (receive), e e e nel taglio, allora anche e' deve essere nel taglio. In altre parole, non si puo includere la ricezione di un messaggio senza includerne anche l'invio. Uno snapshot globale consistente e un taglio consistente degli stati locali di tutti i processi, piu lo stato dei canali di comunicazione.

Meccanismo dei marker

L'algoritmo usa un meccanismo di marker per coordinare la cattura dello snapshot:

1. Tutti i processi sono inizialmente white. Un processo puo avviare lo snapshot in qualsiasi momento.
2. Quando un processo diventa red:
   1. Salva il proprio stato locale.
   2. Invia un marker su tutti i canali in uscita (prima di qualsiasi altro messaggio).
3. Alla ricezione di un marker su un canale j:
   • Se sono ancora white: divento red (salvo stato, invio marker).
   • Segno il canale j come chiuso (ho ricevuto il marker).
4. I messaggi ricevuti su un canale dopo aver ricevuto il marker (ma prima di chiuderlo) vengono registrati come "in transito" e fanno parte dello stato del canale.

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.

17. Message ordering: causale e totale

In un sistema completamente asincrono, non c'e alcuna restrizione sull'ordinamento dei messaggi: massimo non-determinismo, massima concorrenza. Tuttavia, in molte applicazioni, e utile ridurre il non-determinismo imponendo delle garanzie di ordinamento.

FIFO ordering

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 garantiscono questo per default.

Causal ordering

Un passo oltre: se send(m1) → send(m2) (m1 precede causalmente m2), allora rec(m1) → rec(m2) (m1 deve essere ricevuto prima di m2). Non ci sono sorpassi causali.

L'algoritmo per garantire l'ordinamento causale usa matrici di clock (estensione dei vector clock):

• Ogni processo Pi mantiene una matrice m[1..N][1..N] dove m[j,k] conta i messaggi inviati da Pj a Pk noti a Pi.
• Quando Pi invia a Pj, incrementa m[i,j] e allega la matrice al messaggio.
• Alla ricezione, il messaggio e eligible solo se tutti i conteggi nella matrice arrivata sono minori o uguali alla matrice locale (con l'eccezione del canale di provenienza che deve essere esattamente +1).
• Se non e eligible, il messaggio viene bufferizzato.

Total order

L'ordine totale e ancora piu forte: per messaggi multicast, tutti i processi vedono i messaggi nello stesso ordine. Questo richiede un coordinamento aggiuntivo e si basa su algoritmi come ISIS o sequencer centralizzato. E la base per i sistemi di replicated state machine.

18. Consensus: FLP, Byzantine, Paxos e Raft

Il problema del consenso

Il consenso e il problema fondamentale del distributed computing: un insieme di processi deve accordarsi su un valore, nonostante possibili fallimenti. E pervasivo nei sistemi reali: transazioni DB, leader election, state machine replication, atomic broadcast, clock synchronization, blockchain.

Le proprieta che un algoritmo di consenso deve soddisfare sono tre:

• Termination: ogni processo corretto prima o poi decide un valore.
• Agreement: tutti i processi corretti decidono lo stesso valore.
• Integrity: se tutti i processi corretti propongono lo stesso valore, allora qualsiasi processo corretto decide quel valore.

FLP Impossibility

Il risultato piu sorprendente e importante: in un sistema asincrono, anche con un singolo processo che puo crashare, il consenso e impossibile da risolvere (Fischer, Lynch, Patterson, 1985). Non esiste alcun algoritmo deterministico che garantisca termination in queste condizioni. Questo risultato ha profonde implicazioni pratiche: tutti i sistemi reali fanno assunzioni di sincronia (timeout, failure detector) per aggirare l'impossibilita.

Algoritmo base in sistema sincrono

Se assumiamo un sistema sincrono (limite superiore noto per ritardo messaggi e durata azioni), il consenso e possibile con un semplice algoritmo a round:

• Ogni processo mantiene V, l'insieme dei valori conosciuti.
• Per f+1 round (dove f e il massimo numero di fallimenti tollerati):
  1. Invia a tutti i valori di V non ancora inviati.
  2. Riceve valori dagli altri (aspetta un tempo prefissato, poi assume crash).
  3. Aggiorna V con i valori ricevuti.
• Alla fine, decide usando una funzione decide(V) comune a tutti.

Numero di messaggi: O((f+1)N^2).

Byzantine faults

Il caso piu estremo: i processi faulty possono avere comportamento arbitrario (byzantine), inviando valori sbagliati o contraddittori. Il problema e noto come Byzantine General Agreement (BGA).

Il risultato principale: non esiste un protocollo f-resiliente per BGA se N <= 3f. In pratica, servono almeno 3f+1 processi per tollerare f guasti byzantini. L'algoritmo procede per round con un coordinatore rotante (re).

Paxos e Raft

Paxos (Lamport, 1998) e una famiglia di protocolli per il consenso in presenza di crash-stop. E il protocollo piu citato in letteratura, ma notoriamente difficile da comprendere. Raft (Ongaro & Ousterhout, 2013) e un'alternativa progettata per essere understandable: stessa tolleranza ai guasti di Paxos, ma con una struttura piu chiara basata su leader election, log replication e safety.

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

Replicated State Machines

Il consenso e tipicamente usato per implementare macchine a stati replicate: ogni server ha una copia della macchina a stati e un log. Il consensus algorithm garantisce che tutti i server applichino gli stessi comandi nello stesso ordine. 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.

Verifica le tue conoscenze