3. Problemi di Consenso

Far concordare processi su un valore comune nonostante guasti.

• Requisiti:
  • Terminazione: Tutti i processi corretti decidono
  • Accordo: Decisione unanime tra processi corretti
  • Integrità: Se tutti propongono lo stesso valore, la decisione deve rispettarlo
• Problemi correlati:
  • Generali Bizantini (BG): Accordarsi nonostante nodi maliziosi. Soluzione solo se \( N \geq 3f + 1 \) (dove \( f \) è il numero di guasti).
  • Consistenza Interattiva (IC): Accordarsi su un vettore di valori proposti.
  • Equivalenza: BG, IC e Consenso (C) sono risolvibili reciprocamente.

4. Consenso in Sistemi Sincroni vs Asincroni

• Sincroni:
  • Tempi di esecuzione e comunicazione limitati.
  • Soluzioni possibili (es. algoritmo di Dolev con \( f+1 \) cicli per tollerare \( f \) guasti).
  • Limite inferiore: Almeno \( f+1 \) cicli per tollerare \( f \) guasti.
• Asincroni:
  • Nessun limite noto su tempi di esecuzione/comunicazione.
  • Teorema FLP: Nessun algoritmo deterministico garantisce il consenso con anche un solo guasto.
  • Soluzioni approssimate:
    • Indebolire terminazione/accordo.
    • Introdurre failure detector o casualità (es. Paxos).

5. Algoritmo Paxos

• Ruoli:
  • Proposer: Propone valori.
  • Acceptor: Accetta proposte.
  • Learner: Apprende la decisione finale.
• Fasi:
  1. Prepare: Proposer invia una proposta agli acceptor.
  2. Accept: Se la maggioranza accetta, il valore è scelto.
  3. Learning: I learner diffondono la decisione.
• Proprietà:
  • Safety: Valore unico e legittimo.
  • Liveness: Progresso garantito solo durante periodi di sincronia.
• Varianti:
  • Multi-Paxos: Ottimizzazione per ridurre messaggi.
  • RAFT: Alternativa più semplice basata su leader.

6. Consenso Sicuro

• Minacce: Attacchi bizantini, manipolazione di messaggi
• Soluzioni:
  • Autenticazione: Firma digitale dei messaggi
  • Rilevamento anomalie: Scartare valori devianti dalla maggioranza
  • Crittografia: Protezione da attacchi esterni