Consenso in un Sistema Asincrono

Garanzia in sistemi asincroni (FLP): Non esiste un algoritmo deterministico in grado di garantire il consenso in un sistema asincrono a scambio di messaggi anche con un solo fallimento per crash

Strategie:

• Indebolire la Termination: Introducendo elementi di non determinismo oppure garantendo la termination solo durante i periodi di sincronia del sistema
• Indebolire l’Agreement: Individuando un insieme finito per i possibili valori decisionali dei singoli processi
• Irrobustire il modello del sistema: Introducendo dei failure detector per distinguere i processi lenti (ma corretti) da quelli effettivamente falliti

Sommario

Algoritmo di Paxos

// Metafora del parlamento dell'isola di Paxos

• Protocollo di consenso per sistemi distribuiti con processi inaffidabili
• Obiettivo: Garantire che tutte le repliche convergano allo stesso valore con lo stesso ordine

Proprietà

• Liveness:
  • Uno tra i valori proposti prima o poi viene scelto
  • Se un valore viene scelto, ogni processo prima o poi apprenderà tale scelta