Quell’insostenibile pesantezza di taggare tutti

di Enrico Nardelli

A Natale dovremmo essere tutti più buoni del solito e io cerco di seguire questo saggio consiglio, anche perché aiuta ad avere migliori relazioni sociali. Però, uno scomodo sassolino, piccino piccino, fatemelo togliere dalla scarpa, confidando nell'indulgenza del Bambin Gesù.

Avete presente quelli che sui social scrivono dei post, magari molto belli, articolati, profondi, etc. etc. e però li taggano con tutti i loro follower ?

Ecco, per dirla con le parole dell'indimenticato Rino Gaetano: «nun ve reggae più».

Spiego subito il motivo: perché si viene subissati di notifiche e messaggi relativi alla pubblicazione di questi post taggati in modo collettivo.

D'altro canto è un'azione che costa pochissimo a chi la compie, perché non deve elencare uno per uno tutti i contatti ma basta un'etichetta collettiva.

Di conseguenza chi ha scoperto questo meccanismo quasi invariabilmente ha preso la pessima abitudine di farlo su tutti i post e la usa per annunciare urbi et orbi la sua ultima pensata. Tra l’altro dimenticandosi che normalmente sui social si hanno differenti tipologie di seguaci e, se non si è proprio affetti da delirio di onnipotenza, bisognerebbe capire che non ogni pensiero partorito dal proprio cervello è di interesse per tutti.

L'obiezione immediata è: «ma allora smetti di seguirli!» Chi replica così però non tiene presente che il “narcisista” che vuole comunicare a tutto il mondo ogni sua ultima pensata, essendo appunto avido di visibilità, se la prenderà a male se gli togli il follow. Quindi questo non è un suggerimento valido, almeno per me personalmente, visto che non ci tengo affatto a entrare in schermaglie anche nel mondo virtuale, bastandomi quelle del mondo reale.

Pertanto ho cominciato ad applicare la tecnica dell'ignorare: ogni piattaforma ha il modo di "silenziare" i post delle persone che non ci garbano, a totale sua insaputa, e senza togliergli il follow. E, parlandone un po’ in giro, altri mi hanno confermato di aver iniziato ad usare questo rimedio.

I narcisisti di cui sopra avranno mai riflettuto sul fatto che un'azione che fanno per aumentare la loro visibilità risulta in un effetto opposto?

Lo vedremo nel corso dei prossimi mesi.

--
Versione originale pubblicata su "StartMAG" il 26 dicembre 2024.

Strolling through informatics #13 – Reaching an agreement is never easy

previous #12 ––– next #14

by Enrico Nardelli

(versione italiana qua)

In this stage we tackle the third of the relevant problems for distributed computing, that of consensus. In this case too, we introduce it with an example inspired by office life.

The scenario we're considering is therefore that of two colleagues, Anna and Bruno, who need to present themselves together to the office manager to advocate for a common cause. Since they're aware that by going together they'll have better opportunities to make their case, while if only one of them goes a punishment is certain, they've already agreed on a possible day and time to meet in front of the manager's door. At this point they only need to decide whether or not to carry out this plan. To this end, they exchange messages: the problem, however, is that some messages may be lost due to failures or malfunctions of the tools they use, which don't provide a "delivery receipt," that is, a confirmation received by the sender that the message has reached the recipient. This shouldn't be surprising because, even in an age of digital systems, we don't always have certainty that an email message has actually been delivered to the recipient. This means, for example, that after Anna has sent a message to Bruno, she can't be certain that it has arrived and can only wait for a reply or send it again. In other words, Anna can't distinguish the situation where her message was lost from the situation where Bruno's response was lost. Only when Bruno's reply reaches her can she deduce that her message arrived. But at this point it's Bruno who finds himself in a situation of uncertainty: he's not sure that his response has been delivered to Anna.

How can Anna and Bruno solve this situation? Is there an algorithm that could help them be sure they've reached an agreement and no message was lost? The answer, surprising but true, is that even in this very simple scenario, no such algorithm exists.

We provide the proof using the mechanism of proof by contradiction. With this mathematical procedure, we assume that something is true, then show that this assumption leads to a logical contradiction (for example, we derive that a statement is simultaneously true and false) and at this point we conclude that the initial assumption is absurd, that is, not true.

Let's suppose, then, that there exists an algorithm, which we'll call Agreement, that allows them to reach an agreement to carry out the plan by both presenting themselves to the office manager. Let's then consider the scenario, which we'll call Possible, in which Agreement has actually made Anna and Bruno reach an agreement through the exchange of the minimum number of messages. Let's then consider a second scenario, called Alternative, in which Anna and Bruno exchange with the Agreement algorithm exactly the same messages exchanged in the Possible scenario: in the Alternative scenario, however, the last message, which we assume was sent by Anna to Bruno, doesn't reach him because it gets lost. From Anna's perspective, there's no difference between the messages she received in the Possible scenario and those she received in the Alternative one: so she goes to the appointment in both scenarios. From Bruno's perspective, in the Alternative scenario he received one fewer message and the Agreement algorithm can make Bruno take one of these two actions: (1) Bruno doesn't go to the appointment, or (2) Bruno goes to the appointment. In case 1, we deduce that the Agreement algorithm is incorrect, because Anna shows up at the office manager's while Bruno doesn't: this is a contradiction with the initial assumption that Agreement makes them both show up and proves the absurdity of Agreement's existence. In case 2, we get that Anna and Bruno actually exchanged one fewer message in the Alternative scenario to both go to the appointment, and this contradicts the hypothesis that Possible is the scenario with the minimum number of messages. Even in case 2, therefore, this contradiction proves the absurdity of the existence of the optimal Agreement algorithm. Note that we could assume the last message is the one sent by Bruno to Anna but the previous reasoning would remain of the same type and its conclusions equally valid.

This is what theory tells us. In practice, when two people arrange an appointment this way, as they exchange messages their confidence level increases (also as a function of the level of knowledge each has of the other's reliability) and, generally, when one of the parties has received two messages from the counterpart, they consider themselves reasonably sure that an agreement has been reached. This is the situation illustrated in the figure below:

Those who are a bit more suspicious might make a third exchange of messages, but they'll tend to consider themselves quite confident of having reached consensus. Obviously, when the stakes are high and 100% certainty is needed, people use the telephone, that is, synchronous communication, or communication mechanisms that certify the successful delivery of the message.

In the next post we'll briefly examine "communication protocols," that is, the set of rules that define how two executors coordinate to exchange information.

[[The posts in this series are based on the Author's book (in Italian) La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, (= The Informatics Revolution: Knowledge, Awareness and Power in the Digital Society) to which readers are referred for further reading]].

--
The original version (in italian) has been published by "Osservatorio sullo Stato digitale" (= Observatory on Digital State) of IRPA - Istituto di Ricerche sulla Pubblica Amministrazione (= Research Institute on Public Administration) on 18 December 2024.

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

precedente #12 ––– successivo #14

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.

Strolling through informatics #12 – Synchronization among multiple agents

previous #11 ––– next #13

by Enrico Nardelli

(versione italiana qua)

As described in the introductory post on distributed computing, a second significant problem is that of synchronization, where the various executors don't need to coordinate their work, which each one performs autonomously, but must avoid interfering with each other when using resources that everyone needs.

We'll discuss this through the example of an office where two employees, Rossi and Bianchi, must each check their own files without having to coordinate their management. For simplicity, let's assume their work consists only of checking, followed by either rejecting or approving the file under examination. File approval happens by sealing the decision with a special stamp made of two parts located in two different places. If the two employees don't implement some form of synchronization, they might find themselves in a situation where one has taken one part of the stamp, the other has taken the other part, and neither can approve their file. We'll exclude particular strategies that people might implement in cases like these, for example going to find the other person responsible and agreeing that one gives up their part to the other so they can stamp their file and then receive back the complete stamp to approve their own.

This is the simplest possible example of synchronization. It can be solved by having both agents execute the same algorithm, called Peterson's algorithm, which I won't report entirely here due to its formal complexity, referring to my book La rivoluzione informatica for its detailed explanation and providing an intuitive description below.

The algorithm assumes there are three "global variables" which, in the context of an office like the one we're considering, we can think of as three bulletin boards that all employees can read. Each bulletin board is identified by a name: Rossi_wants_to_stamp, Bianchi_wants_to_stamp, Now_it's_the_turn_of. At the beginning of the algorithm, FALSE is written on each of the first two bulletin boards, while what's written on the third is irrelevant.

The algorithm continuously repeats the sequence of actions described below.

The employee who needs to approve their file declares they want to stamp, that is, writes TRUE on the bulletin board that begins with their name, and writes the other employee's name on the bulletin board that expresses whose turn it is.

After this, they check if it's simultaneously true that the other employee wants to stamp and that it's their turn, and if so (let's call this eventuality a "red light") they wait for this situation to become false.

When this happens (i.e., there's no longer a red light) then (1) they go get both parts of the stamp, (2) approve the file, (3) release both parts of the stamp. These three actions are technically defined as the "critical section," because they're the ones that must be executed by only one automaton at a time, to avoid causing the deadlock situation described at the beginning.

After executing the critical section, the employee writes FALSE on the bulletin board that begins with their name and continues checking their files.

Having finished describing the algorithm, let's show that indeed the critical section can be executed by only one automaton at a time and that only one automaton at a time can be in the waiting state.

Let's assume Bianchi is executing their critical section and that Rossi is waiting. Then Rossi will be able to enter their critical section only when Bianchi exits theirs and writes FALSE on the Bianchi_wants_to_stamp bulletin board (thus making false the condition that was keeping Rossi waiting, or removing the red light). When this happens, Bianchi is checking files and Rossi enters the critical section: after a while Rossi will also exit their critical section and move on to checking files.

Let's now imagine that, while Bianchi continues checking files, Rossi declares they want to stamp. If Bianchi continues always checking files then Rossi doesn't have to wait (because FALSE is written on Bianchi_wants_to_stamp) and enters their critical section. If, during this phase when Rossi is in their critical section, Bianchi also declares they want to stamp, then they'll find the red light (because TRUE is written on Rossi_wants_to_stamp and moreover it's written on the turn bulletin board that it's Rossi's turn) and will remain waiting. We're therefore in the previously described situation, with roles reversed between Rossi and Bianchi.

Let's see instead what happens if, right after Rossi has declared they want to stamp, Bianchi also writes TRUE on the Bianchi_wants_to_stamp bulletin board. Then it can't happen that both go into the waiting state because, even if they try to write simultaneously on the bulletin board that expresses whose turn it is, they can only write one after the other and in the end either Bianchi or Rossi will be written on the bulletin board. In the first case, it's Rossi who waits and Bianchi enters the critical section; in the second case, the opposite happens. If instead the attempt to write on the turn bulletin board, after both have declared their intention to stamp, is not simultaneous but happens first (for example) by Rossi, then Rossi will enter the waiting state, but only momentarily because when Bianchi then comes to write on the turn bulletin board, they'll make false the condition that was blocking Rossi in the waiting state, allowing the latter to enter their critical section while they (Bianchi) wait.

In the next post we'll examine the third important problem of distributed computing, that of consensus.

[[The posts in this series are based on the Author's book (in Italian) La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, (= The Informatics Revolution: Knowledge, Awareness and Power in the Digital Society) to which readers are referred for further reading]].

--
The original version (in italian) has been published by "Osservatorio sullo Stato digitale" (= Observatory on Digital State) of IRPA - Istituto di Ricerche sulla Pubblica Amministrazione (= Research Institute on Public Administration) on 11 December 2024.

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

precedente #11 ––– successivo #13

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.

Strolling through informatics #11 – How do multiple automata reach agreement?

previous #10 ––– next #12

by Enrico Nardelli

(versione italiana qua)

As we introduced in the previous post, we are considering the case of multiple agents that must collectively execute a computation. Communication between them in this context occurs through the asynchronous exchange of messages. I remind you that asynchronous exchange is what happens with email, while synchronous exchange is the case of a phone call, which requires the simultaneous availability of both parties.

We must also specify exactly the characteristics of the set of automata and how they are organized. To remain at a very simple level (and referring to my book The Computer Revolution for more details) we assume that each executor is identifiable through a different integer number. All automata execute the same algorithm, but in each executor the algorithm can make different decisions based on the messages received and its identifier.

A final relevant element to define is what the structure of the communication network available to the set of automata is, that is, with which other agents they can exchange the messages that are necessary to achieve coordination. For example, can an executor talk to all agents or only to a subset? Neglecting the irrelevant cases of automata that don't talk to any other automaton, various choices are possible, from the absolutely extreme ones (and therefore somewhat uninteresting) where each agent talks only to one other agent (the case on the left in the figure below) or where each agent talks to all other agents (on the right).

A simple but nonetheless non-trivial model of communication network structure is the so-called "ring", where the set of agents is imagined arranged in a circle and each agent talks only to those on its right and left.

The simplest problem that can be addressed is that of choosing a "leader" or "director", to possibly guide the collective's action in the future.

Initially, none of the agents in the ring is the director. The correct solution to the problem occurs when exactly one of the agents is the leader and remains so stably, meaning that the computation process that led to its selection no longer causes it to change state, and this information is known to all.

A simple algorithm, called Chang-Roberts, to solve this problem under the assumptions we are considering works as follows. Remember that this algorithm is executed by each agent.

Each executor starts the algorithm either by its own decision or because it receives a message from the agent on its right. If an executor receives a message with an identifier smaller than its own, it does nothing. If an executor receives a message with an identifier larger than its own, it forwards it to the agent on its left. If an executor receives a message with its own identifier, it proclaims itself the director and announces it to the agent on its left. If an executor receives a message with the result of the director election, it forwards it to the agent on its left, unless it concerns its own identifier. In any case, the execution of the algorithm in this agent terminates.

An example of execution in the case of a set of 6 automata is shown in the figure below, where the number inside each circle is the identifier and the number next to the red arrow is the message being sent.

In the example, for ease of illustration, all executors start at the same time, but the algorithm is independent of this assumption.

The various steps of the computation are shown one at a time proceeding from left to right and then from top to bottom. For each executor, the next one clockwise in the figure is the one the algorithm considers to its left. The last image synthetically represents the fact that agent 6, having received the message with its identifier in the previous step, forwarded it as a director selection message to its left and received the director selection message from the agent on its right.

We can convince ourselves that the algorithm is correct by observing that the identifier with the maximum value is forwarded by all executors until it reaches the one identified by it (first six images), while every other identifier is eventually stopped. Therefore, only one of the agents will determine to be the director and notify all others (the seventh image).

We can pose the problem of how many messages in total are necessary to complete this algorithm. Referring to the text The Computer Revolution for a more thorough discussion, I only recall here that, considering only the worst case (as discussed in the episode How long does this algorithm take?), this occurs when the identifiers of the automata are always decreasing, going around the ring clockwise. In that case, the number of messages needed is proportional to N². With a more sophisticated analysis, it can be shown that on average the number of messages used by this algorithm is N∙(log N). This is also the complexity that the best known algorithm for this problem (the Hirschberg-Sinclair algorithm) guarantees in the worst case. This algorithm is also the best possible, since it has been proven that any algorithm needs to send at least N∙(log N) messages.

[[The posts in this series are based on the Author's book (in Italian) La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, (= The Informatics Revolution: Knowledge, Awareness and Power in the Digital Society) to which readers are referred for further reading]].

--
The original version (in italian) has been published by "Osservatorio sullo Stato digitale" (= Observatory on Digital State) of IRPA - Istituto di Ricerche sulla Pubblica Amministrazione (= Research Institute on Public Administration) on 7 December 2024.

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

precedente #10 ––– successivo #12

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.