💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

Hermes è un protocollo BFT a due round con leader rotante per $n=5f+1$ processi che elimina i ritardi di latenza (tail-latency stalls) causati da leader lenti o crashati utilizzando il consenso sul prefisso per finalizzare il prefisso comune più pesante da qualsiasi $n-f$ voti, garantendo così il progresso anche quando le view scadono.

Autori originali: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

Pubblicato 2026-07-29

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate un gruppo di amici che cerca di decidere quale film guardare, ma sono sparsi per il mondo, alcuni hanno una connessione internet instabile e alcuni amici dispettosi stanno cercando di sabotare la decisione inviando link falsi o fingendo di essere offline. Questo è il mondo del consenso Byzantine Fault Tolerant (BFT). In informatica, questo è il modo in cui una rete di computer concorda su un'unica verità — come l'ordine delle transazioni in una blockchain — senza fidarsi di un singolo capo centrale. L'obiettivo è raggiungere un accordo rapidamente (bassa latenza) anche quando alcuni computer si guastano o agiscono in modo malevolo.

Per anni, questi sistemi si sono affidati a un "leader" per proporre il passo successivo. Se il leader è veloce ed onesto, tutti concordano rapidamente. Ma se il leader è lento o si guasta, l'intero gruppo deve aspettare che un timer scada, rinunci a quel leader e ne scelga uno nuovo. Questo crea un doloroso compromesso: imposta il timer lungo e aspetterai all'infinito un leader guasto; impostalo breve e sprecherai tempo abbandonando leader che erano solo un po' lenti. Questo "dilemma del timeout" è il collo di bottiglia che rallenta la coda del sistema, rendendo le richieste più lente estremamente lunghe da completare.

Questo articolo presenta Hermes, un nuovo protocollo progettato per risolvere questo specifico mal di testa. Invece di arrendersi quando un leader è lento, Hermes permette al gruppo di completare il lavoro su cui possono già concordare, anche se il leader fallisce. Trasforma un timeout sprecato in una decisione produttiva, assicurando che, qualunque cosa accada, il sistema continui a procedere senza perdere i progressi già compiuti.

Il Problema: La "Trappola del Timeout"

Immaginate una staffetta dove il capitano della squadra (il leader) deve consegnare il testimone al corridore successivo. Se il capitano è veloce, la gara procede senza intoppi. Ma se il capitano inciampa o perde il testimone, l'intera squadra deve fermarsi e aspettare il fischio di un arbitro (il timeout) prima di poter scegliere un nuovo capitano e ricominciare.

Nei sistemi tradizionali, questo fischio è una scommessa. Se l'arbitro fischia troppo presto, potrebbe fermare un capitano che era solo un po' lento ma che avrebbe completato la corsa. Se aspettano troppo a lungo, la squadra resta inattiva per un tempo infinito mentre un capitano guasto cerca di riprendersi. In entrambi i casi, il tempo trascorso è "tempo morto": non viene fatto alcun progresso e la gara è bloccata. Questo è il problema della "latenza della coda" (tail latency): gli scenari peggiori trascinano verso il basso l'intero sistema.

La Soluzione: Hermes e il "Terreno Comune"

Hermes cambia le regole del gioco. Invece di trattare un leader lento come un fallimento totale, Hermes considera l'accordo parziale del gruppo come una vittoria.

Ecco come funziona con un'analogia creativa: Immaginate che la squadra stia cercando di costruire una lunga torre di blocchi.

Il Vecchio Modo: Il leader posiziona un blocco. Tutti aspettano. Se il leader si ferma, la squadra aspetta il timeout, poi getta via l'intera torre e ricomincia a costruire una nuova torre con un nuovo leader.
Il Modo Hermes: Il leader inizia a posizionare i blocchi, ma tutti iniziano anche a posizionare i propri blocchi simultaneamente. Se il leader è veloce, la squadra costruisce la torre del leader perfettamente. Se il leader si blocca, la squadra non getta via la torre. Invece, guardano tutti i blocchi che ognuno ha posizionato, trovano la sezione più lunga in cui tutti concordano sull'ordine dei blocchi e dichiarano quella sezione come "completata".

Questa è l'innovazione centrale: Consenso del Prefisso (Prefix Consensus). Nei tempi passati, se due persone votavano per torri leggermente diverse, i loro voti erano considerati un disaccordo e venivano scartati. Hermes dice: "Aspetta, concordano sul 90% inferiore della torre! Blocchiamo quella parte e procediamo".

Come Funziona Hermes: La Danza in Due Round

Hermes opera in "view" (round), ognuno con un leader designato. Utilizza una sapiente danza in due fasi:

Round 1 (La Proposta): Tutti trasmettono la propria idea di come dovrebbe apparire la parte successiva della torre. L'idea del leader è solo una delle tante.
Round 2 (Il Voto):
- Se il leader è veloce: Tutti vedono la proposta del leader, concordano e votano per essa. La torre cresce con l'intero blocco del leader in soli due ritardi di messaggistica (2δ).
- Se il leader è lento o si guasta: Il timer scade. Inveve di votare per "annullare" il round, tutti votano per il miglior accordo possibile che riescano a trovare tra le proposte ricevute. Cercano il "Prefisso Comune più Pesante" (Heaviest Common Prefix - HCP): la sequenza più lunga di blocchi su cui tutti concordano, anche se le loro proposte divergono alla fine.

Ciò significa che anche se il leader fallisce, il gruppo non perde la "view". Finalizzano la parte comune della torre e iniziano immediatamente il round successivo. Il "timeout", che prima era un vicolo cieco, ora produce un risultato.

La Magia dei "Prefissi" e degli "Skip"

Per far sì che questo funzioni con più corsie di dati (come un'autostrada con molte corsie di traffico), Hermes utilizza una codifica speciale chiamata parent-relative delta tipcuts.

Pensatelo come a un libro "Scegli la tua avventura" dove ogni pagina fa riferimento alla precedente. Se una corsia di traffico manca di un'auto (un blocco), Hermes non dice "errore". Segna esplicitamente quel punto come "saltato" (skipped) e passa all'auto successiva. Ciò consente al sistema di confrontare diverse proposte anche se mancano parti differenti. È come confrontare due storie: anche se una storia salta un paragrafo e l'altra lo include, possono comunque concordare sull'inizio e sulla fine, e il sistema blocca quell'accordo.

I Risultati: Velocità e Sicurezza

L'articolo dimostra matematicamente che Hermes è sicuro (nessuna due persone oneste concorderanno mai su parti diverse della parte finalizzata) e vitale (il sistema continuerà sempre a muoversi).

Il Caso Positivo: Se il leader è onesto e veloce, Hermes è veloce quanto i migliori sistemi esistenti, finalizzando in 2δ (due ritardi di messaggistica).
Il Caso Negativo: Se il leader è lento o si guasta, Hermes finalizza l'accordo comune in 2∆ + δ (dove ∆ è il timeout e δ è il ritardo di rete). Fondamentalmente, questo è più veloce del vecchio metodo di attendere un intero cambio di view, perché evita il tempo "sprecato" di scartare la view.

Gli autori dimostrano che, utilizzando la codifica di cancellazione (erasure coding) (un modo per scomporre i dati in pezzi in modo che possano essere ricostruiti anche se alcuni pezzi vanno persi), Hermes mantiene bassi i costi di comunicazione, anche quando si gestiscono molte corsie di dati.

Perché Questo è Importante

Hermes risolve il "dilemma del timeout" rendendo il timeout stesso produttivo. Trasforma un momento di fallimento in un momento di progresso. Inveve di chiedere: "Il leader ce l'ha fatta?" e aspettare di vedere, Hermes chiede: "Su cosa siamo tutti d'accordo?" e va avanti.

Per un adolescente curioso, pensate a una chat di gruppo dove tutti cercano di mettersi d'accordo su un piano. Se la persona che di solito suggerisce il piano si blocca, il vecchio modo è aspettare che risponda o iniziare una nuova chat con un nuovo leader. Hermes è come dire: "Ok, non ha risposto, ma guardate tutte le idee che abbiamo inviato. Siamo tutti d'accordo sui primi tre passi. Blocchiamoli e iniziamo a pianificare il quarto". È un modo più intelligente e resiliente per mantenere il gruppo in movimento, indipendentemente da chi faccia cadere la palla.

Sintesi Tecnica: Hermes: Bassa Latenza di Coda Tramite Consenso di Prefisso

1. Definizione del Problema

I protocolli BFT (Byzantine Fault Tolerant) basati su un leader tipicamente finalizzano le transazioni solo quando un leader designato è tempestivo. Se un leader fallisce o è lento, la vista deve essere terminata tramite un timeout, risultando in una vista "sprecata" in cui non viene compiuto alcun progresso. Ciò crea un compromesso fondamentale nella configurazione dei timeout:

Timeout conservativi: Tollerano leader lenti ma trasformano ogni crash del leader in un lungo blocco.
Timeout aggressivi: Saltano rapidamente i leader crashati ma invalidano le viste di leader che sono semplicemente lenti (un evento comune nei sistemi geo-distribuiti).

In entrambi i casi, la vista scaduta è sprecata e la richiesta deve attendere un cambio di vista e il successivo giro di andata e ritorno (round trip) del prossimo leader per la finalizzazione. Questo compromesso, piuttosto che le prestazioni nel "caso ideale", governa la latenza di coda del sistema. Inoltre, le architetture moderne spesso separano la disseminazione dei dati (ad esempio, DAG, design a corsie/lane) dall'ordinamento del consenso. In questi contesti, le proposte sono prefissi di un flusso e le proposte oneste all'interno di una vista spesso differiscono solo nel suffisso a causa del jitter di rete. I protocolli esistenti scartano questi voti non corrispondenti come disaccordi, non riuscendo a sfruttare il prefisso comune che condividono.

2. Metodologia

Hermes è un protocollo a due round con leader rotante progettato per $n = 5f + 1$ processi sotto parziale sincronia. Introduce il Consenso di Prefisso, un meccanimento in cui i voti trasportano valori ordinati da una relazione di prefisso ( $\preceq$ ), e i quorum richiedono la comparabilità piuttosto che l'uguaglianza.

Meccanismi Core

Struttura a due round:
1. Round 1 (Proposta): Ogni processo trasmette una proposta giustificata. La proposta del leader round-robin è una tra $n$ .
2. Round 2 (Voto): Ogni processo emette un singolo voto.
  - Se la proposta del leader viene consegnata tempestivamente, i processi votano per essa.
  - Se un timeout ( $2\Delta$ ) scade e vengono ricevute $n-f$ proposte valide, i processi votano per una proposta di fallback selezionata dall'insieme disponibile.
- Crucialmente, non esistono voti di nullificazione.
Definizioni di Quorum:
- M-notarizzazione: Un set di $2f+1$ voti a coppie comparabili. Ciò consente alla vista di avanzare alla vista successiva.
- L-notarizzazione: Un set di $n-f = 4f+1$ voti validi (che non devono essere identici). Questo set finalizza il Massimo Prefisso Comune (HCP - Heaviest Common Prefix) dei voti.
Gestione dei Timeout:
Inve แทน di invalidare una vista quando il leader è lento, Hermes utilizza il percorso di timeout per finalizzare l'HCP dei $n-f$ voti raccolti. Un timeout aggressivo costa ora solo il suffisso in cui i voti divergono, non l'intera vista. L'HCP viene finalizzato a $2\Delta + \delta$ .
Istanziazioni dello Spazio dei Valori:
Il protocollo è istanziato su uno spazio astratto ordinato per prefisso ed applicato a due scenari specifici:
1. Single-Lane (Gadget di Finalità): Su una catena dinamicamente disponibile (ad es. Ethereum). I valori sono i tip della catena; la relazione di prefisso è l'ancestralità.
2. Multi-Lane (stile Autobahn): Ordina corsie (lane) di dati concorrenti. Ciò introduce tre sfide specifiche affrontate da:
  - Interleaving Deterministico: Un ordine globale per le posizioni delle corsie.
  - Delta Tipcut Relativo al Genitore: Una rappresentazione compatta utilizzando identificatori del genitore e marcatori di salto espliciti per gestire velocità eterogenee delle corsie senza trasmettere i valori completi.
  - Amplificazione tramite Erasure Coding Indicizzata al Mittente: Per garantire la disponibilità senza gonfiare la complessità di comunicazione a $O(n^3 \hat{m})$ , le proposte sono amplificate tramite codici di cancellazione (erasure codes). Le giustificazioni trasportano identificatori e i frammenti vengono ricostruiti su richiesta.

3. Contributi Chiave

Protocollo Hermes: Un protocollo a due round con leader rotante a $n=5f+1$ $n = 5 f + 1$ senza percorso di nullificazione.
- Caso Buono: Finalizzazione in $2\delta$ con un leader onesto tempestivo.
- Caso Cattivo: Finalizzazione dell'HCP di qualsiasi $n-f$ voti a $2\Delta + \delta$ .
- Sicurezza e Liveness: Dimostrate su uno spazio di valori a prefisso astratto.
Istanziazione Single-Lane: Un gadget di finalità per catene disponibili dove i valori sono i tip della catena.
Istanziazione Multi-Lane: Un design per corsie in stile Autobahn caratterizzato da:
- Interleaving deterministico.
- Delta tipcut relativi al genitore con certificazione di salto esplicita.
- Amplificazione tramite erasure coding indicizzata al mittente.
- Complessità: $O(n^2 \hat{m} + \lambda n^3)$ bit e $O(n^2)$ messaggi per vista (dove $\hat{m}$ è il numero di corsie e $\lambda$ è il parametro di sicurezza).
Implementazione e Valutazione: Il documento include un'implementazione e una valutazione (Sezione 8), sebbene i risultati numerici specifici siano contrassegnati come "Aggiungere risultati" nel testo fornito.

4. Risultati e Prestazioni

Latenza:
- Leader Tempestivo: Finalizza in $2\delta$ .
- Leader Lento/Crashato: Finalizza l'HCP in $2\Delta + \delta$ . Questo è un miglioramento significativo rispetto ai protocolli tradizionali dove un leader lento risulta in un intero cambio di vista e un successivo round di $2\delta$ , totalizzando $2\Delta + 3\delta$ o più prima della prima finalizzazione.
Comunicazione:
- Nell'ambiente multi-lane con amplificazione, il protocollo evita la complessità quartica ( $O(n^3 \hat{m})$ ) associata al trasferimento di valori completi.
- Il caso buono mantiene $O(n^2)$ messaggi. In presenza di guasti, la complessità di messaggi può salire a $O(n^3)$ a causa del traffico di amplificazione, ma la complessità di bit rimane controllata.
Latenza di Coda: Rendendo produttivo il percorso di timeout, Hermes elimina la penalità della "vista sprecata". Una richiesta che finisce in una cattiva vista paga il timeout e la finalizzazione dell'HCP, invece di attendere un intero ciclo di cambio vista.

5. Significato

Il documento sostiene che Hermes altera fondamentalmente il compromesso tra reattività (quanto velocemente cambia una vista) e stabilità (quanti cambi di vista producono progresso).

Timeout Produttivi: A differenza dei design precedenti dove un timeout implica una vista invalidata, Hermes assicura che anche una vista con un leader fallito finalizzi un prefisso utile del flusso di dati.
Compatibilità con le Architetture Moderne: Colma il divario tra i livelli di disseminazione dei dati disponibili (come DAG o sistemi a corsie) e il consenso, permettendo al gadget di finalità di ordinare blocchi che sono già stati propagati ma che potrebbero divergere leggermente nella fase di disseminazione.
Ottimalità: Hermes raggiunge il limite teorico inferiore di $2\delta$ per il caso buono, risolvendo al contempo il problema della latenza di coda che ha persistito nei sistemi BFT basati su leader, senza richiedere un protocollo di recupero separato o meccanismi di gara (racing).

Il documento posiziona Hermes come l'unico protocollo della sua classe in cui la vista di un leader fallito viene essa stessa finalizzata, ponendosi in contrasto con protocolli come Minimmit (che nullifica tali viste) o Raptr (che usa il voto di prefisso per la disponibilità ma all'interno della proposta di un singolo leader).