Riflessioni sulle Scienze

di Alberto Viotto    indice articoli

 

Il paradosso dei due generali

Settembre 2011

• La reciprocità

• E' arrivata la mia email?

• Il livello di incertezza

• Uno solo decide

• Quanta incertezza?

Due armate alleate stanno attaccando una città fortificata. Le armate sono accampate su due colline separate da una valle in cui si trova la città e l’unico modo per comunicare è rappresentato dall’invio di messaggeri, che però possono essere catturati dai nemici mentre attraversano la vallata (1).

Se le due armate attaccheranno insieme la vittoria è sicura, ma se una armata attaccasse da sola è quasi certo che verrebbe sconfitta. I due generali devono concordare l’ora dell’attacco, ma l’unico modo per farlo è tramite un messaggero. E se il messaggero venisse catturato dai nemici?

 

La reciprocità

Per essere sicuro che il suo messaggio sia stato ricevuto, il primo generale deve inviare un messaggero ed aspettare che il secondo generale, con un altro messaggero, gli confermi di avere ricevuto la comunicazione. A questo punto, però, il secondo generale a sua volta non è sicuro che il suo messaggio di conferma sia stato ricevuto: se il suo messaggero viene intercettato, il primo generale non sarà sicuro che la sua comunicazione sia stata ricevuta, e non attaccherà. Se il secondo generale attaccasse senza avere a sua volta ricevuto la conferma, potrebbe andare incontro ad una disfatta. Il primo generale, quindi, deve inviare la conferma della conferma, e ci si riconduce alla situazione iniziale.

E’ facile vedere che la situazione porta ad una ricorsione infinita: per uno dei due generali c’è sempre un messaggero di cui si ignora la sorte. Ognuno dei due generali non riuscirà mai ad organizzare un attacco con la sicurezza di non essere il solo ad attaccare.

 

E’ arrivata la mia email?

Questo paradosso è un caso specifico del “Problema dei generali bizantini” (2), trattato nello studio dei protocolli di comunicazione. Fu pubblicato per la prima volta nel 1975 e ricevette il nome con cui è conosciuto in un articolo del 1978 di Jim Gray, il ricercatore della Microsoft, premio Turing nel 1998, scomparso in circostanze misteriose nella baia di San Francisco nel 2007 mentre andava a disperdere in mare le ceneri della madre (3).

Ogni volta che spediamo una email affrontiamo un problema analogo. L’affidabilità delle email, anche se molto maggiore di quanto fosse ai primi tempi di Internet, è tutt’altro che garantita. Una nostra email si potrebbe perdere senza che ne veniamo informati: è vero che in teoria se qualcosa va storto dovrebbe arrivarci un messaggio speciale detto NDR (Non - delivery report) che ci informa del disguido, ma questo messaggio potrebbe a sua volta perdersi.

Una soluzione può essere quella di chiedere una conferma al destinatario, sia esplicitamente che richiedendo una ricevuta automatica al sistema di email ma, se questa non arriva, non possiamo concludere che il messaggio non sia arrivato: potrebbe essersi perso il messaggio di conferma. Se, invece, la conferma arriva, il livello di incertezza si sposta sul destinatario. Se invia la conferma, non può essere sicuro che questa sia arrivata fino a quando non riceva a sua volta una ricevuta: anche questa, però, potrebbe perdersi.

Il paradosso non ha soluzione e rappresenta un aspetto di una legge generale: bisogna rassegnarsi a convivere con l’incertezza.

 

Il livello di incertezza

Quando spediamo una email, la probabilità che dopo avere premuto il tasto “Invia” non arrivi al destinatario è abbastanza alta, anche perché banalmente potremmo avere sbagliato a scrivere il suo indirizzo (il nostro sistema non ha modo di accorgersene). Se c’è stato un errore, ad esempio perché abbiamo usato un indirizzo e-mail inesistente, è molto probabile che ci arrivi un NDR dal sistema del destinatario, che ha una bassa probabilità di perdersi perché utilizza a ritroso una strada già percorsa.

In modo molto approssimato, possiamo ipotizzare che ci sia una probabilità su cento che il nostro messaggio originale non arrivi; in questo specifico caso, possiamo ipotizzare che ci sia una probabilità su diecimila che l’avviso di mancata ricezione (l’NDR) a sua volta non arrivi. Con queste premesse, la probabilità che un messaggio non arrivi senza che ne siamo informati è di uno su un milione; se qualcuno fa finta di non avere ricevuto una nostra mail che non ha generato un NDR, quindi, è molto probabile che stia facendo il furbo, anche se non ne possiamo essere sicuri.

 

Uno solo decide

Ma come fanno i sistemi informatici a convivere con questa incertezza? Uno dei motivi è che la maggior parte delle comunicazioni non sono paritarie, come nel caso dei due generali, ma asimmetriche: un sistema “master” comunica ad un sottosistema che cosa deve fare, ed aspetta la sua conferma per procedere. Il sottosistema, invece, una volta ricevuto l’ordine ed inviato il messaggio di ritorno, procede a fare quanto ordinato senza attendere a sua volta la conferma, come se il secondo generale attaccasse al momento richiesto trascurando il rischio di andare incontro alla disfatta.

Il buon funzionamento del sistema principale è quello che conta, il sottosistema è “sacrificabile”. Se non si adottasse questa semplificazione, il paradosso impedirebbe qualsiasi tipo di operazione concertata.

 

Quanta incertezza?

Un altro approccio ingegneristico al problema consiste nell’abbassare il più possibile il livello di incertezza, ad esempio inviando più “messaggeri” (cioè più pacchetti di dati nel caso di un protocollo di comunicazione). La probabilità che un pacchetto si perda può essere rilevante, ma la probabilità che tutti i pacchetti si perdano è sensibilmente più bassa e la si può giudicare completamente trascurabile.

Contrariamente a quanto comunemente si crede, infatti, anche nel campo dei computer si ha a che fare con probabilità estremamente alte e non con certezze. Un messaggio criptato, ad esempio, può essere decodificato se si conosce la chiave crittografica, ed uno dei sistemi per scoprirne il contenuto è di provarne tutte le combinazioni, con un “attacco a forza bruta”. Anche se estremamente improbabile, è possibile che la si scopra al primo tentativo; nel caso della codifica DES {XE "DES"} (4), ad esempio, la probabilità del successo immediato di un attacco a forza bruta è di uno su due elevato alla cinquantaseiesima potenza, e cioè di uno su 64.000.000.000.000.000.

Per un confronto, si ritiene che la frequenza con cui si verifica l’impatto di un meteorite da "catastrofe globale", in grado di provocare la morte di un quarto della popolazione mondiale, sia di una ogni milione di anni circa; in altri termini, la probabilità che questo accada nel prossimo minuto è di uno su:

 

1.000.000 x 525.600 (numero di minuti in un anno)

 

circa 500.000.000.000. La probabilità di una catastrofe globale nel prossimo minuto è più di 100.000 volte maggiore della probabilità che un attacco ad una codifica DES {XE "DES"} abbia successo al primo colpo. Questa probabilità è così bassa che si può dire, trasformando un aspetto quantitativo in un aspetto qualitativo, che semplicemente non esiste e che la codifica DES è sicura.

 

   Alberto Viotto

 

Se qualche lettore trovasse questo articolo interessante o ne volesse discutere, all'autore farebbe piacere ricevere delle e-mail all'indirizzo: alberto_viotto@hotmail.com

 

NOTE

1) http://en.wikipedia.org/wiki/Two_Generals%27_Problem

2) http://en.wikipedia.org/wiki/Byzantine_Generals%27_Problem

3) http://research.microsoft.com/en-us/um/people/gray/

4) http://www.oneitsecurity.it/28/08/2008/lalgoritmo-des/

 

Altri articoli di Alberto Viotto

 

Alberto Viotto offre gratuitamente due suoi Ebook:

 

Come ti fregano
Analisi dei meccanismi del marketing ed altri trucchi

 

"Da mattina a sera, sui giornali, sulle televisioni, sul web,  siamo sommersi da messaggi pubblicitari che sembrano pensati per un pubblico di semideficienti. Naturalmente il circo del marketing ha un costo, che ricade sull’ambiente ma anche su di noi, costretti a pagare di più i prodotti che ci servono (circa 400€ in più in media su ogni auto nuova).
Di chi la colpa? Ahimè, è nostra, perché compriamo i prodotti pubblicizzati; se la pubblicità non facesse aumentare le vendite i produttori smetterebbero di  tormentarci. Un rapido esame dei meccanismi del marketing ci può aiutare ad immunizzarci."

Achille e la tartaruga e altri paradossi

 

"Una nuova e più elegante soluzione al paradosso più famoso. Altri celebri enigmi (il sorite, il cretese mentitore, il gatto quantistico, la stanza cinese) affrontati da un punto di vista non convenzionale".