Quattordicesima puntata del nostro viaggio
In questa tappa affrontiamo il terzo dei problemi rilevanti per la computazione distribuita, quello del consenso. Anche in questo caso lo introduciamo con un esempio ispirato alla vita d’ufficio.
Lo scenario considerato è quindi quello di due colleghi, Anna e Bruno, che devono presentarsi insieme dal capo-ufficio per sostenere una causa comune. Poiché sono consapevoli del fatto che andando insieme avranno maggiori opportunità di farsi valere, mentre se va uno solo dei due una punizione è certa, hanno già concordato il possibile giorno e ora in cui incontrarsi davanti alla porta del capo. A questo punto devono solo decidere se realizzare o no questo piano. Allo scopo si scambiano messaggi: il problema però è che qualche messaggio può perdersi a causa di guasti o malfunzionamenti degli strumenti che usano, che non prevedono una “ricevuta di consegna”, cioè una conferma ricevuta dal mittente che il messaggio è arrivato al destinatario. Ciò non deve sorprendere perché, anche in un’epoca di sistemi digitali, non sempre si ha la certezza che un messaggio di posta elettronica sia stato effettivamente consegnato al destinatario. Questo, ad esempio, vuol dire che, dopo che Anna ha inviato un messaggio a Bruno, non può avere la certezza che esso sia arrivato e può soltanto attendere una risposta o inviarlo di nuovo. In altre parole, Anna non può distinguere la situazione in cui il suo messaggio è andato perso dalla situazione in cui è la risposta di Bruno che si è persa. Solo quando le giunge la risposta di Bruno può dedurre che il suo messaggio è arrivato. Ma a questo punto è Bruno che si trova in una situazione di incertezza: non è sicuro che la sua risposta sia stata consegnata ad Anna.
Come possono fare Anna e Bruno per risolvere questa situazione? Esiste un algoritmo che possa aiutarli ad avere la sicurezza che si sono messi d’accordo e nessun messaggio è andato perso? La risposta, sorprendente ma vera, è che, anche in questo semplicissimo scenario, non esiste un tale algoritmo.
Ne diamo la prova con il meccanismo della dimostrazione per assurdo. Con questo procedimento matematico si assume che qualcosa sia vero, poi si fa vedere che da questa assunzione deriva una contraddizione logica (ad esempio, si deriva che un’affermazione è contemporaneamente vera e falsa) e a questo punto si conclude che l’assunzione iniziale è assurda, cioè non vera.
Supponiamo, allora, che esista un algoritmo, che chiamiamo Accordo, che consente di mettersi d’accordo per realizzare il piano presentandosi entrambi dal capo-ufficio. Consideriamo poi lo scenario, che chiamiamo Possibile, in cui Accordo ha fatto effettivamente mettere d’accordo Anna e Bruno con lo scambio del numero minimo di messaggi. Consideriamo poi un secondo scenario, chiamato Alternativo, in cui Anna e Bruno si scambiano con l’algoritmo Accordo esattamente gli stessi messaggi scambiati nello scenario Possibile: nello scenario Alternativo però l’ultimo messaggio, che ipotizziamo sia stato inviato da Anna a Bruno, non raggiunge quest’ultimo perché viene perso. Dal punto di vista di Anna, non c’è differenza tra i messaggi che ha ricevuto nello scenario Possibile e quelli che ha ricevuto in quello Alternativo: quindi, va all’appuntamento in entrambi gli scenari. Dal punto di vista di Bruno, nello scenario Alternativo gli è arrivato un messaggio in meno e l’algoritmo Accordo può far compiere a Bruno una di queste due azioni: (1) Bruno non va all’appuntamento, oppure (2) Bruno va all’appuntamento. Nel caso 1 si deduce che l’algoritmo Accordo è scorretto, perché Anna si presenta dal capo-ufficio mentre Bruno no: questa è una contraddizione con l’assunto iniziale che Accordo li faccia presentare entrambi e prova l’assurdità dell’esistenza di Accordo. Nel caso 2 si ottiene che Anna e Bruno hanno effettivamente scambiato nello scenario Alternativo un messaggio in meno per andare entrambi all’appuntamento, e questo contraddice l’ipotesi che Possibile sia lo scenario col numero minimo di messaggi. Anche nel caso 2, quindi, tale contraddizione prova l’assurdità dell’esistenza dell’algoritmo Accordo. Notate che potremmo assumere che l’ultimo messaggio, quello che viene perso, sia stato inviato da Bruno ad Anna, ma il ragionamento precedente rimarrebbe dello stesso tipo e le sue conclusioni ugualmente valide.
Questo è quello che ci dice la teoria. Nella pratica, quando due persone concordano un appuntamento in questo modo, man mano che si scambiano messaggi il loro livello di confidenza aumenta (anche in funzione del livello di conoscenza che ognuna di esse ha dell’affidabilità dell’altra) e, generalmente, quando una delle due parti ha ricevuto due messaggi dalla controparte, si ritiene ragionevolmente sicura che l’accordo sia stato raggiunto. È la situazione illustrata nella figura sottostante:
Quelli un po’ più diffidenti, magari, faranno un terzo scambio di messaggi, ma tendenzialmente si riterranno abbastanza sicuri di aver raggiunto il consenso. Ovviamente, quando la posta in gioco è alta e serve la certezza al 100%, le persone usano il telefono, cioè la comunicazione sincrona, oppure meccanismi di comunicazione che certificano l’avvenuta consegna del messaggio.
Nel prossimo post prenderemo brevemente in esami i “protocolli di comunicazione” ovvero l’insieme di regole che definiscono come due esecutori si coordinano per scambiare informazioni.
( I post di questa serie sono basati sul libro dell’Autore La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti. I lettori interessati al tema possono anche dialogare con l’Autore, su questo blog interdisciplinare, su cui i post vengono ripubblicati a partire dal terzo giorno successivo alla pubblicazione in questa sede. )