A passeggio con l'informatica #13 – Raggiungere un accordo non è mai facile

di Enrico Nardelli

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 vuol dire, ad esempio, 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 ottimo Accordo. Notate che potremmo assumere che l’ultimo messaggio sia quello 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.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 18 dicembre 2024.

A passeggio con l’informatica #12 – La sincronizzazione fra più esecutori

di Enrico Nardelli

Come descritto nel post introduttivo alla computazione distribuita, un secondo problema rilevante è quello della sincronizzazione, in cui i vari esecutori non devono coordinare il loro lavoro, che ognuno svolge in maniera autonoma, ma devono evitare di intralciarsi nell’uso di risorse che servono a tutti.

Lo discutiamo attraverso l’esempio di un ufficio in cui due impiegati, Rossi e Bianchi, devono ognuno controllare le proprie pratiche senza doversi coordinare nella loro gestione. Assumiamo per semplicità che il loro lavoro consista solo nel controllo, seguito dal rifiuto o dall’approvazione della pratica in esame. L’approvazione della pratica avviene suggellando la decisione attraverso un timbro particolare, fatto da due parti che si trovano in due posti diversi. Se i due impiegati non attuano una qualche forma di sincronizzazione, si possono trovare nella situazione in cui uno ha preso una parte del timbro, l’altro ha preso l’altra parte e nessuno dei due può approvare la pratica. Escludiamo strategie particolari che le persone potrebbero attuare in casi come questi, per esempio andando a trovare l’altro responsabile e concordando che uno dei due ceda la sua parte all’altro per fargli timbrare la sua pratica per poi ricevere indietro il timbro completo per approvare la propria.

Questo è il più semplice esempio possibile di sincronizzazione. Può essere risolto facendo eseguire a entrambi gli agenti uno stesso algoritmo, detto di Peterson, che non riporto interamente qua per la sua complessità formale, rimandando al mio libro La rivoluzione informatica per la sua spiegazione di dettaglio e fornendo nel seguito una descrizione intuitiva.

L’algoritmo assume che vi siano tre “variabili globali” che, nel contesto di un ufficio quale quello che stiamo considerando, possiamo considerare come tre bacheche che tutti gli impiegati possono leggere. Ogni bacheca è identificata da un nome: Rossi_vuole_timbrare, Bianchi_vuole_ timbrare, Adesso_è_il_turno_di. All’inizio dell’algoritmo in ognuna delle prime due bacheche è scritto FALSO, mentre ciò che è scritto sulla terza è irrilevante. L’algoritmo ripete in continuazione la sequenza di azioni descritta nel seguito.

L’impiegato che deve approvare la sua pratica dichiara che vuole timbrare, cioè scrive VERO sulla bacheca che inizia col suo nome, e scrive il nome dell’altro impiegato sulla bacheca che esprime di chi è il turno.

Dopo di questo, controlla se è contemporaneamente vero che l’altro impiegato vuole timbrare e che è il suo turno, e in caso positivo (chiamiamo “semaforo rosso” questa eventualità) si mette ad aspettare che questa situazione diventi falsa.

Quando ciò accade (cioè non vi è più il semaforo rosso) allora (1) va a prendere entrambi le parti del timbro, (2) approva la pratica, (3) rilascia entrambe le parti del timbro. Queste tre azioni vengono tecnicamente definite “sezione critica”, perché sono quelle che devono essere eseguite solo da un automa per volta, per non causare la situazione di blocco descritta all’inizio.

Successivamente all’esecuzione della sezione critica l’impiegato scrive FALSO sulla bacheca che inizia col suo nome e continua a controllare le sue pratiche.

Terminata la descrizione dell’algoritmo facciamo vedere che effettivamente la sezione critica può essere eseguita solo da un automa alla volta e che solo un automa alla volta può essere nello stato di attesa.

Assumiamo che Bianchi stia eseguendo la sua sezione critica e che Rossi sia in attesa. Allora Rossi potrà entrare nella sua sezione critica solo quando Bianchi uscirà dalla sua e scriverà FALSO sulla bacheca Bianchi_vuole_timbrare (rendendo così falsa la condizione che teneva Rossi in attesa, ovvero rimuovendo il semaforo rosso). Quando questo accade, Bianchi si trova a controllare pratiche e Rossi entra nella sezione critica: dopo un po’ anche Rossi uscirà dalla sua sezione critica e passerà a controllare pratiche.

Immaginiamo adesso che, mentre Bianchi continua a controllare pratiche, Rossi dichiari che vuole timbrare. Se Bianchi continua sempre a controllare pratiche allora Rossi non deve attendere (perché su Bianchi_vuole_timbrare c’è scritto FALSO) ed entra nella sua sezione critica. Se, in questa fase in cui Rossi è nella sua sezione critica, anche Bianchi dichiara di voler timbrare, allora troverà il semaforo rosso (perché su Rossi_vuole_timbrare c’è scritto VERO e inoltre sulla bacheca del turno c’è scritto che è il turno di Rossi) e rimarrà in attesa. Siamo quindi nella situazione precedentemente descritta, a parti invertite tra Rossi e Bianchi.

Vediamo invece che succede se, proprio subito dopo che Rossi ha dichiarato che vuol timbrare, anche Bianchi scrive VERO sulla bacheca Bianchi_vuole_timbrare. Allora non può accadere che entrambi vadano nello stato di attesa perché, anche se tentano di scrivere contemporaneamente sulla bacheca che esprime di chi è il turno potranno scrivere solo uno dopo l’altro e alla fine sulla bacheca ci sarà scritto o Bianchi o Rossi. Nel primo caso è Rossi che va in attesa e Bianchi entra nella sezione critica, nel secondo caso, avviene il contrario. Se invece il tentativo di scrittura sulla bacheca del turno, dopo aver dichiarato entrambi la volontà di timbrare non è contemporaneo ma avviene prima (ad esempio) quello di Rossi, allora sarà Rossi a entrare in attesa, ma solo momentaneamente, perché quando poi Bianchi arriva a scrivere sulla bacheca del turno renderà falsa la condizione che bloccava Rossi nello stato di attesa, consentendo a quest’ultimo di entrare nella sua sezione critica mentre lui (Bianchi) va in attesa.

Nel prossimo post esamineremo il terzo importante problema della computazione distribuita, quello del consenso.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione l'11 dicembre 2024.

A passeggio con l'informatica #11 – Come fanno più automi a mettersi d’accordo?

di Enrico Nardelli

Come abbiamo introdotto nel post precedente, stiamo considerando il caso di più agenti che devono eseguire collettivamente un’elaborazione. La comunicazione tra di essi in questo contesto avviene mediante lo scambio asincrono di messaggi. Ricordo che lo scambio asincrono è ciò che avviene con la posta elettronica, mentre lo scambio sincrono è il caso di una telefonata, che richiede la disponibilità contemporanea di entrambi gli interlocutori.

Dobbiamo inoltre precisare con esattezza le caratteristiche dell’insieme degli automi e della loro organizzazione. Per rimanere a un livello molto semplice (e rimandando al mio libro La rivoluzione informatica per maggiori dettagli) assumiamo che ogni esecutore sia identificabile tramite un diverso numero intero. Tutti gli automi eseguono lo stesso algoritmo, ma in ogni esecutore l’algoritmo può prendere decisioni diverse in base ai messaggi ricevuti e al suo identificatore.

Un ultimo elemento rilevante da definire è quale sia la struttura della rete di comunicazione disponibile per l’insieme di automi, cioè con quali altri agenti si possono scambiare i messaggi che sono necessari per realizzare il coordinamento. Ad esempio, un esecutore può parlare con tutti gli agenti o solo con un sottoinsieme? Trascurando i casi irrilevanti di automi che non parlano con alcun altro automa, sono possibili diverse scelte, da quelle assolutamente estreme (e quindi in qualche modo poco interessanti) in cui ogni agente parla solo con un altro agente (il caso a sinistra nella figura sotto) oppure in cui ogni agente parla con tutti gli altri agenti (a destra).

Un modello semplice ma comunque non banale di struttura della rete di comunicazione è quello del cosiddetto “anello”, in cui si immagina l’insieme degli agenti disposti a cerchio e ogni agente parla solo con chi gli sta a destra e a sinistra.

Il più semplice problema che si può affrontare, in tema di cooperazione, è quello della scelta di un “comandante” o “direttore”, per eventualmente in futuro guidare l’azione del collettivo.

All’inizio nessuno degli agenti dell’anello è il direttore. La soluzione corretta del problema si ha quando esattamente uno degli agenti è il comandante e lo rimane stabilmente, nel senso che il processo di elaborazione che ha portato alla sua scelta non gli fa più cambiare stato, e questa informazione è nota a tutti.

Un semplice algoritmo, detto di Chang-Roberts, per risolvere questo problema nelle ipotesi che stiamo considerando è fatto nel modo che adesso descriviamo. Ricordiamo che questo algoritmo viene eseguito da ogni agente.

Ogni esecutore inizia l’algoritmo o per sua spontanea decisione o perché gli arriva un messaggio dall’agente alla sua destra. Se un esecutore riceve un messaggio con identificatore minore del suo non fa niente. Se un esecutore riceve un messaggio con un identificatore maggiore del suo lo inoltra all’agente alla sua sinistra. Se un esecutore riceve un messaggio con il suo identificatore si proclama il direttore e lo annuncia all’agente alla sua sinistra. Se un esecutore riceve un messaggio con il risultato dell’elezione del direttore lo inoltra all’agente alla sua sinistra, a meno che non si tratti del suo identificatore. In ogni caso l’esecuzione dell’algoritmo in questo agente termina.

Un esempio di esecuzione nel caso di un insieme di 6 automi è mostrato nella figura più sotto, cui il numero all’interno di ogni cerchietto è l’identificatore e il numero accanto alla freccia rossa è il messaggio che viene inviato.

Nell’esempio, per facilità di illustrazione, tutti gli esecutori iniziano nello stesso momento, ma l’algoritmo è indipendente da questa assunzione. I vari passi della computazione sono mostrati uno alla volta procedendo da sinistra a destra e poi dall’alto in basso. Per ogni esecutore, quello successivo in senso orario nella figura è quello che l’algoritmo considera alla sua sinistra. L’ultima immagine rappresenta sinteticamente il fatto che l’agente 6, avendo ricevuto al passo precedente il messaggio con il suo identificatore, l’ha inoltrato come messaggio di scelta del direttore alla sua sinistra e ha ricevuto il messaggio di scelta del direttore dall’agente alla sua destra.

Possiamo convincerci che l’algoritmo sia corretto osservando che l’identificatore di valore massimo viene inoltrato da tutti gli esecutori fino a raggiungere quello identificato da esso (prime sei immagini), mentre ogni altro identificatore viene prima o poi fermato. Quindi uno solo degli agenti determinerà di essere il direttore e avviserà tutti gli altri (la settima immagine).

Ci possiamo porre il problema di quanti messaggi in tutto siano necessari per terminare questo algoritmo. Rimandando al testo La rivoluzione informatica per una discussione più approfondita, ricordo qui soltanto che, prendendo in considerazione solo il caso pessimo (come discusso nella puntata Ma quanto ci mette quest’algoritmo?), questo si ha quando gli identificatori degli automi sono sempre decrescenti, andando lungo l’anello in senso orario. In tal caso il numero di messaggi necessario è proporzionale a N ². Con un’analisi più sofisticata si può dimostrare che in media il numero di messaggi utilizzati da questo algoritmo è N∙(log N ). Questa è anche la complessità che il miglior algoritmo conosciuto per questo problema (si tratta di quello di Hirschberg-Sinclair) garantisce nel caso pessimo. Tale algoritmo è anche il migliore possibile, dal momento che si è dimostrato che qualunque algoritmo ha bisogno di inviare almeno N∙(log N ) messaggi.

Nel prossimo post affronteremo il secondo dei problemi più importanti che caratterizzano la computazione distribuita, quello della sincronizzazione.

--
Versione originale pubblicata da "Osservatorio sullo Stato digitale" dell'IRPA - Istituto di Ricerche sulla Pubblica Amministrazione il 7 dicembre 2024.