Link&Think: 2024

domenica 29 dicembre 2024

Quell’insostenibile pesantezza di taggare tutti

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.

sabato 21 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.

sabato 14 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.

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.

martedì 10 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.

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.

sabato 30 novembre 2024

Strolling through informatics #10 – Putting multiple automata to work

previous #9 ––– next #11

by Enrico Nardelli

(versione italiana qua)

As we mentioned in stage 6 of this journey (Understanding algorithms is not difficult), informatics as a scientific discipline was born – from a cultural standpoint – when we began to consider the possibility of executing algorithms mechanically through an automaton. Subsequently, however, we realize that computation can also be carried out with the participation of multiple agents, a condition that in the current era is evident even to the average person, due to the omnipresence of the Internet. This type of situation, generally called "distributed computing", presents various aspects. In the course of the next stages, we will examine three of the most important ones, which we briefly introduce here.

A first aspect is cooperation, which refers to a set of automata that must collectively perform a computation and, therefore, cooperate in achieving this objective. Much like when a group of people must carry out a certain task in collaboration. For example, there might be an office procedure that requires checks on different aspects, each under the responsibility of a different person and to be carried out in an established order. In such cases, communication between the different executors becomes necessary to coordinate the various computations that each one performs.

A second aspect is synchronization, in which there is a need to avoid interfering with each other in the use of shared resources, without there necessarily being cooperation. Still staying within the context of office procedure approval, imagine that each person in charge has their own procedures to approve, without having to coordinate with others for the decision. The approval process, however, requires putting a special stamp on it. The particularity of the stamp is that it is composed of two parts, each stored in a different repository. It is therefore necessary for the various people in charge to synchronize to avoid the case where one person, after having retrieved one part of the stamp, finds themselves blocked because simultaneously another person has already retrieved the other part from the other repository.

A third aspect, consensus, refers to the fact that both communications between the various agents and their behavior can be subject to failures or errors. How then can we be sure that the communications we have sent have actually arrived? How can we be sure we have received the counterpart's response? We observe that this aspect is extremely relevant in practical applications, where failures, temporary or permanent, can normally occur, despite all the precautions that can be taken to prevent this from happening.

Finally, let us clarify that, for simplicity of presentation, we only examine the case of agents all made in the same way and therefore capable of executing the instructions of the same language. Furthermore, we assume that they all have the same hierarchical level, that is, there is no one who commands and others who obey, and that they all execute the same algorithm.

We will therefore consider these three problems, cooperation, synchronization and consensus, in the next three posts, and we will conclude our excursus in the field of distributed computing with a post dedicated to communication protocols, which are a fundamental ingredient of that "network of networks", more commonly known as the Internet, which has been the fundamental factor for the spread of digital systems in the daily life of every person.

A passeggio con l'informatica #10 – Come mettere al lavoro più automi

precedente #9 ––– successivo #11

di Enrico Nardelli

Come abbiamo accennato nella tappa n.6 di questo viaggio (Comprendere gli algoritmi non è difficile), l’informatica come disciplina scientifica nasce – da un punto di vista culturale – quando si comincia a considerare la possibilità di eseguire algoritmi in modo meccanico attraverso un automa. Successivamente, però, ci si rende conto che un’elaborazione può essere attuata anche con la partecipazione di più agenti, condizione che nel periodo attuale è evidente anche all’uomo della strada, a causa dell’onnipresenza di Internet. Tale tipo di situazione, denominata in generale “computazione distribuita”, presenta diversi aspetti. Nel corso delle prossime tappe esamineremo tre dei più importanti, che qui introduciamo brevemente.

Un primo aspetto è la cooperazione, che fa riferimento a un insieme di automi che devono effettuare collettivamente un’elaborazione e, quindi, cooperano nel raggiungimento di quest’obiettivo. Un po’ come quando un gruppo di persone deve realizzare un certo compito in collaborazione. Ad esempio, vi può essere una pratica d’ufficio che necessita di controlli su aspetti differenti, ognuno di competenza di un differente responsabile e da svolgere secondo un ordine stabilito. In tal caso si rende necessaria una comunicazione tra i differenti esecutori per coordinare le varie elaborazioni che ognuno svolge.

Un secondo è la sincronizzazione, in cui vi è la necessità di non intralciarsi nell’uso di risorse condivise, senza che necessariamente vi sia una cooperazione. Sempre per rimanere nel contesto dell’approvazione di pratiche d’ufficio, si immagini che ogni responsabile abbia le sue pratiche da approvare, senza doversi coordinare con gli altri per la decisione. Il processo di approvazione richiede però di mettere un timbro particolare su di essa. La particolarità del timbro è che è composto da due parti, ognuna conservata in un differente deposito. È quindi necessario che i vari responsabili si sincronizzino per evitare il caso di un responsabile che, dopo aver prelevato una parte del timbro, si trovi bloccato perché contemporaneamente un altro responsabile ha già prelevato l’altra parte dall’altro deposito.

Un terzo aspetto, il consenso, fa riferimento al fatto che sia le comunicazioni tra i vari agenti, sia il loro comportamento, possono essere soggetti a guasti o errori. Come facciamo quindi ad essere sicuri che le comunicazioni che abbiamo inviato siano effettivamente arrivate? Come essere sicure di aver ricevuto la risposta della controparte? Osserviamo che questo aspetto è estremamente rilevante nelle applicazioni pratiche, dove guasti, temporanei o permanenti, possono normalmente accadere, nonostante tutte le precauzioni che possono essere prese affinché questo non succeda.

Chiariamo infine che, per semplicità di presentazione, esaminiamo solo il caso di agenti fatti tutti nello stesso modo e quindi in grado di eseguire le istruzioni di uno stesso linguaggio. Inoltre assumiamo che essi abbiano tutti lo stesso livello gerarchico, ovvero non c’è uno che comanda e altri che obbediscono, e che eseguano tutti lo stesso algoritmo.

Considereremo quindi questi tre problemi, cooperazione, sincronizzazione e consenso, nei prossimi tre post, e concluderemo il nostro excursus nell’ambito della computazione distribuita con un post dedicato ai protocolli di comunicazione, che sono un ingrediente fondamentale di quella “rete delle reti”, più comunemente conosciuta come Internet, che è stata il fattore fondamentale per la diffusione dei sistemi digitali nella vita quotidiana di ogni persona.

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

sabato 23 novembre 2024

Strolling through informatics #9 – Algorithms at the boundary

previous #8 ––– next #10

by Enrico Nardelli

(versione italiana qua)

To complete our picture of algorithmic problem solving, we need to discuss one more situation that is extremely important in today's context. Based on what was said in the previous post (How long does this algorithm take?), there can exist problems for which no algorithms with polynomial complexity functions are known (and therefore we cannot say they belong to class P), but for which proof of the impossibility of obtaining them has not yet been found (and therefore we cannot say they properly belong to class EXP). This means that for these problems we know at least one solution algorithm (whose complexity function is exponential), and this classifies them as computable problems, but we cannot say whether they are problems that belong to the "good" variety (i.e., they admit polynomial algorithms, meaning they are tractable) or the "bad" variety (with only exponential algorithms, meaning they are intractable). In this case the problem is in a kind of limbo, in which theoretical computer scientists have identified a very important set called class NP, which marks the boundary between tractability and intractability.

Without going into the details of how this class is defined (for which I refer to the book The Computer Revolution), we can say that it includes problems whose solutions can be verified in polynomial time and for which only solution algorithms of exponential complexity are known. Indeed, hundreds of these problems exist (thousands if we consider their variants), for which mutual equivalence has been proven. This equivalence means that if a polynomial algorithm were found for just one of them, then all these problems would fall into class P (they would be, that is, tractable problems). If just one of them were instead proven to properly belong to class EXP, then they would all be classified as intractable (though this latter hypothesis seems unlikely to most scholars).

Given the current state of knowledge in theoretical informatics, we know that class P is strictly contained in class EXP (I remind you that a set A is strictly contained in set B if every element of A also belongs to B and furthermore we are certain of the existence of elements that belong to B and do not belong to A). However, the known relationships between classes P, NP and EXP are only of containment, meaning that P is contained in NP and that NP is contained in EXP, but we don't know exactly which of these containments is strict. The most interesting aspect concerns the relationship between classes P and NP. It could be strict or the two classes could coincide. The problem of whether class P and class NP coincide or not, that is

P=NP ?

is probably the most famous open problem in theoretical informatics. The Clay Mathematics Institute included it in 2000 among the seven millennium problems and has offered a prize of one million dollars for its proof.

The problem has particular interest since problems in class NP that are thought not to be in P often form the basis of cryptographic methods that protect the security of commercial transactions on the Internet. For example, the RSA public key encryption system bases its security on the fact that the decomposition of an integer into prime factors is one of these problems.

Since no efficient algorithms (i.e., executable in polynomial time) are currently known for decomposing an integer into its prime factors, the system cannot be broken in an acceptable time. It should be noted that, with sufficient dedicated hardware equipment (which is within reach of large organizations that can count on substantial economic resources such as, for example, the NSA, acronym for National Security Agency, the national security agency of the United States) it is possible to decompose integers of 1,024 bits, which was the recommended value for constructing RSA keys until a few years ago. Bruce Schneier, a US security expert, recommended in 2007, when the decomposition of an integer of about 1,024 bits was announced (albeit of a particular type that made the work simpler), to abandon keys of this length. The availability of so-called "quantum" computers is another possible threat to RSA public key encryption, but appropriate countermeasures are being taken for this eventuality as well.

A passeggio con l'informatica #9 – Algoritmi al confine

precedente #8 ––– successivo #10

di Enrico Nardelli

Per completare il quadro della risoluzione algoritmica dei problemi, dobbiamo discutere ancora una situazione, estremamente importante nel contesto odierno. In base a quanto detto nel post precedente, possono esistere dei problemi per i quali non si conoscono algoritmi con funzione di complessità polinomiale (e quindi non si può dire che appartengono alla classe P), ma per cui non si è ancora trovata la dimostrazione di impossibilità di ottenerli (e quindi non si può dire che appartengono propriamente alla classe EXP). Ciò vuol dire che per essi si conosce almeno un algoritmo risolutivo (la cui funzione di complessità è esponenziale), e questo li classifica come problemi computabili, ma non si sa dire se siano problemi che appartengono alla varietà “buona” (cioè ammettono algoritmi polinomiali, ossia sono trattabili) oppure “cattiva” (con solo algoritmi esponenziali, cioè intrattabili). In questo caso il problema è in una specie di limbo, nel quale gli informatici teorici hanno individuato un insieme molto importante detto classe NP, che marca il confine fra la trattabilità e l’intrattabilità.

Senza entrare nel dettaglio di come tale classe venga definita (per cui rimando al mio libro La rivoluzione informatica), possiamo dire che ad essa appartengono i problemi le cui soluzioni sono verificabili in tempo polinomiale e per i quali si conoscono solo algoritmi risolutivi di complessità esponenziale. In effetti esistono centinaia di questi problemi (migliaia se ne consideriamo le varianti), per i quali è stata dimostrata l’equivalenza reciproca. Questa equivalenza vuol dire che se per uno solo di essi si trovasse un algoritmo polinomiale, allora tutti questi problemi rientrerebbero nella classe P (sarebbero, cioè, problemi trattabili). Se per uno solo di essi si dimostrasse invece l’appartenenza propria alla classe EXP, allora verrebbero tutti classificati come intrattabili (anche se quest’ultima ipotesi appare poco probabile alla maggior parte degli studiosi).

Allo stato attuale delle conoscenze dell’informatica teorica si sa che la classe P è strettamente contenuta nella classe EXP (ricordo che un insieme A è strettamente contenuto nell’insieme B se ogni elemento di A appartiene anche a B e inoltre si è certi dell’esistenza di elementi che appartengono a B e non appartengono ad A). Però, le relazioni note tra le classi P, NP ed EXP sono solo di contenimento, cioè che P è contenuta in NP e che NP è contenuta in EXP, ma non si sa esattamente quale di questi contenimenti sia stretto. L’aspetto più interessante riguarda la relazione tra le classi P e NP. Potrebbe essere stretto oppure le due classi potrebbero coincidere. Il problema se la classe P e la classe NP coincidano o meno, ovvero

P=NP ?

è probabilmente il problema aperto più famoso dell’informatica teorica. Il Clay Mathematics Institute lo ha inserito nel 2000 fra i sette problemi del millennio e ha offerto un premio di un milione di dollari per la sua dimostrazione.

Il problema ha un interesse particolare dal momento che problemi nella classe NP che si pensa non siano in P sono spesso alla base dei metodi crittografici, che proteggono la sicurezza delle transazioni commerciali su Internet. Ad esempio, il sistema di cifratura a chiave pubblica RSA ha alla base della sua sicurezza il fatto che la scomposizione di un numero intero in fattori primi è uno di questi problemi.

Poiché non si conoscono, al momento attuale, algoritmi efficienti (cioè eseguibili in tempo polinomiale) per scomporre un intero nei suoi fattori primi, il sistema non può essere violato in un tempo accettabile. Va ricordato che, con sufficienti attrezzature hardware dedicate (che sono alla portata di organizzazioni di grandi dimensioni che possono contare su ingenti risorse economiche quali, ad esempio, l’NSA, acronimo di National Security Agency, l’agenzia per la sicurezza nazionale degli Stati Uniti) si riescono a scomporre interi di 1.024 bit, che era il valore raccomandato per la costruzione delle chiavi di RSA fino a qualche anno fa. Bruce Schneier, esperto USA di sicurezza, ha raccomandato nel 2007, quando è stata annunciata la scomposizione di un intero di circa 1.024 bit (anche se di un tipo particolare che ha reso il lavoro più semplice) di abbandonare le chiavi di questa lunghezza. La disponibilità di computer cosiddetti “quantistici” è un’altra possibile minaccia alla cifratura a chiave pubblica RSA, ma anche per questa eventualità si stanno prendendo le opportune contromisure.

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

sabato 16 novembre 2024

Strolling through informatics #8 – How long does this algorithm take?

previous #7 ––– next #9

by Enrico Nardelli

(versione italiana qua)

We saw in the previous post that for some computations, it's impossible to find any algorithm. Additionally, since we are mortal and don't have infinite time available to obtain an answer, we're also interested in knowing how long a certain algorithm might take to complete its computation.

Initially, we're interested in distinguishing those problems, called tractable, where as the problem grows in size we continue to wait a "human" amount of time for the answer, from those problems, called intractable, where this doesn't happen. Instead of talking about time, I'll discuss these aspects by referring to the number of steps needed to solve the problem by the best known algorithm for it. The reason for this choice is that time can depend on the intrinsic speed of the specific computer used to execute the (program that implements the) algorithm, while we're interested in a characterization independent of technological developments. In any case, the results in terms of tractability or intractability don't change. Conversely, but we won't discuss this in these posts and I refer you to the book La rivoluzione informatica for a discussion, the use of quantum computers makes tractable some of the problems that are intractable using a classical computer (which is an automaton equivalent to the UTM).

Every algorithm, once expressed in a program, requires time proportional to the number of instructions that must be executed. Given the algorithm, therefore, one can write the mathematical function, called the algorithm's complexity function, which expresses this number based on the size N of the problem. We should all remember, having studied it in school, the difference between a polynomial function and an exponential function. In the first, the argument N is the base of a power (e.g., N ² or N ³ or even N ¹⁰), while in the second it's the exponent of the power (e.g., 2N or 3N or even 10N). Exponential functions grow much faster than polynomial ones. In the following table we report the value of these functions for different values of the argument N. We recall that the symbol "~" means "about," "approximately," and that the notation, for example, 10¹⁰ indicates the digit 1 followed by 10 zeros, that is, the value 10 billion. In the table you can see that already for N = 60, all the exponential functions presented have a value greater than all the polynomial functions.

It's important to remember that the complexity function is expressed, for each algorithm, with reference to the so-called "worst case" for the algorithm's execution, that is, the most unfavorable one in terms of the number of instructions to execute (assuming, for simplicity, that all instructions require the same time). Let's consider the first of the problems presented in the previous post, that of sorting. We want to know what the maximum guaranteed execution time of the algorithm is as a function of the quantity N, whatever may happen with the N input data. It can be proven that for this problem the best known algorithm guarantees a time proportional to N log(N ), where "log" is the logarithmic function we should remember from high school, and this result cannot be improved.

Let's now assume that executing a single instruction requires a modern computer one nanosecond, that is, one billionth of a second. In formula, 10^-9 (that is, 1/10⁹) seconds. Let's then consider the second problem, of shortest paths, for which the best algorithm guarantees in the worst case the execution of at most N³ instructions for a list with N cities (ignoring marginal improvements obtained in recent years). Then we're able to solve it for 100 cities in one thousandth of a second (because 1,000,000, that is 10⁶, multiplied by 10^-9 equals 10³, that is 1/10³ = 0.001) and for 1,000 cities in one second (1,000³ = 10⁹, which multiplied by 10^-9 equals exactly 1). If we then needed to solve it for 10,000 cities, 1,000 seconds would be needed, or about 17 minutes. For 100,000 cities it would even require a million seconds, equal to about 12 days: a very long time, but all in all acceptable.

Let's instead see what happens for the third problem, the traveling salesman, for which the best known algorithms require the execution of 2N instructions for a list with N cities. In this case we could solve it for 20 cities in just over one thousandth of a second, but already for 30 cities one second would be necessary, 40 cities would require 17 minutes, and 50 would be the maximum number of cities for which the problem is solvable waiting a time of 12 days. The solution for 60 cities could be obtained in about 32 years, clearly an unacceptable time.

So here's how the distinction between "tractable" and "intractable" problems is given based on the type of function that expresses the number of steps necessary for its solution algorithms. In particular, if a solution algorithm is known for which such a complexity function is polynomial, that is, the problem admits a polynomial algorithm, then the problem is called tractable (that is, it's said to belong to class P). If instead it has been proven that every possible solution algorithm has an exponential complexity function, the problem is intractable (that is, it's said to belong properly to class EXP). While in the first case it's enough to find just one polynomial algorithm to define the problem as tractable, in the second case the proof must be conducted independently of specific algorithms, since the set of possible solution algorithms is infinite and the fact that a polynomial complexity algorithm hasn't been found so far doesn't imply that it doesn't exist.

To discuss this situation from another point of view and to better understand that intractability cannot be solved with technological advances, let's consider what would happen if we had a computer a thousand times faster than current ones. Having 12 days available, we would be able to solve the second problem for a million cities instead of 100,000. In the case of the third problem, in the same time of 12 days we would only manage to go from 50 to 60 cities!

The next post, the last one dedicated to algorithms, will consider a boundary situation between tractability and intractability that is very relevant both from a cultural and practical point of view.

A passeggio con l'informatica #8 – Ma quanto ci mette quest’algoritmo?

precedente #7 ––– successivo #9

di Enrico Nardelli

Abbiamo visto nel post precedente che per alcune elaborazioni non è possibile trovare alcun algoritmo. In aggiunta, dal momento che siamo mortali e non abbiamo a disposizione un tempo infinito per ottenere una risposta, ci interessa anche sapere quanto tempo può metterci un certo algoritmo a completare la sua elaborazione.

In prima istanza ci interessa distinguere quei problemi, chiamati trattabili, in cui man mano che il problema cresce di dimensione continuiamo a dover aspettare un tempo “umano” per la risposta, e quei problemi, detti invece intrattabili, in cui questo non accade. Invece di parlare di tempo, discuterò questi aspetti facendo riferimento al numero di passi necessario per risolvere il problema da parte del miglior algoritmo noto per esso. Il motivo di questa scelta è che il tempo può dipendere dalla velocità intrinseca dello specifico calcolatore usato per l’esecuzione del (programma che concretizza) l’algoritmo, mentre noi siamo interessati a una caratterizzazione indipendente dalle evoluzioni tecnologiche. In ogni caso, i risultati in termini di trattabilità o intrattabilità non cambiano. Viceversa, ma non ne parleremo in questi post e vi rimando al libro La rivoluzione informatica per una discussione, l’utilizzo di computer quantistici rende trattabili alcuni dei problemi che sono intrattabili usando un computer classico (che è un automa equivalente alla MUT).

Ogni algoritmo, una volta espresso in un programma, richiede un tempo proporzionale al numero delle istruzioni che devono essere eseguite. Dato quindi l’algoritmo, si può scrivere la funzione matematica, detta funzione di complessità dell’algoritmo, che esprime questo numero in base alla dimensione N del problema. Dovremmo ricordare tutti, per averla studiata a scuola, la differenza tra una funzione polinomiale e una funzione esponenziale. Nella prima, l’argomento N è la base di una potenza (p.es. N ² oppure N ³ o anche N¹⁰), mentre nella seconda è l’esponente della potenza (p.es. 2^N oppure 3^N o anche 10^N ). Le funzioni esponenziali crescono molto più velocemente di quelle polinomiali. Nella tabella seguente riportiamo il valore di queste funzioni per differenti valori dell’argomento N. Ricordiamo che il simbolo “ ~ ” vuol dire “circa”, “approssimativamente”, e che la notazione, ad esempio, 10¹⁰ indica la cifra 1 seguita da 10 zeri, cioè il valore 10 miliardi. Nella tabella si vede che già per N = 60, tutte le funzioni esponenziali presentate hanno valore maggiore di tutte le funzioni polinomiali.

È importante ricordare che la funzione di complessità viene espressa, per ogni algoritmo, in riferimento al cosiddetto “caso pessimo” per l’esecuzione dell’algoritmo stesso, ovvero a quello più sfavorevole in termini di numero di istruzioni da eseguire (assumendo, per semplicità, che tutte le istruzioni richiedano uno stesso tempo). Consideriamo il primo dei problemi presentati nel post precedente, quello dell’ordinamento. Vogliamo sapere quale sia il tempo massimo garantito di esecuzione dell’algoritmo in funzione della quantità N, qualunque cosa possa accadere con gli N dati in ingresso. Si può dimostrare che per questo problema il miglior algoritmo conosciuto garantisce un tempo proporzionale a N⋅log(N ), dove “log” è la funzione logaritmica che dovremmo ricordarci dalle scuole superiori, e questo risultato non è migliorabile.

Assumiamo ora che l’esecuzione di una singola istruzione richieda a un moderno computer un nanosecondo, cioè un miliardesimo di secondo. In formula, 10^-9, cioè (1/10)⁹ secondi. Consideriamo poi il secondo problema, dei cammini minimi, per il quale il miglior algoritmo garantisce nel caso pessimo l’esecuzione di al più N ³ istruzioni per una lista con N città (trascurando miglioramenti marginali ottenuti negli ultimi anni). Allora siamo in grado di risolverlo per 100 città in un millesimo di secondo (perché 1.000.000, cioè 10⁶, moltiplicato per 10^-9 fa 10^-3, cioè (1/10)³ = 0,001) e per 1.000 città in un secondo (1.000³ = 10⁹, che moltiplicato per 10^-9 fa esattamente 1). Se avessimo poi bisogno di risolverlo per 10.000 città, servirebbero 1.000 secondi, ovvero circa 17 minuti. Per 100.000 città sarebbe addirittura necessario un milione di secondi, pari a circa 12 giorni: un tempo molto lungo, ma tutto sommato accettabile.

Vediamo invece cosa accade per il terzo problema, del commesso viaggiatore, per il quale i migliori algoritmi conosciuti richiedono l’esecuzione di 2^N istruzioni per una lista con N città. In questo caso potremmo risolverlo per 20 città in appena più di un millesimo di secondo, ma già per 30 città sarebbe necessario un secondo, 40 città richiederebbero 17 minuti, e 50 sarebbe il massimo numero di città per cui il problema è risolvibile aspettando un tempo di 12 giorni. La risoluzione per 60 città potrebbe essere ottenuta in circa 32 anni, chiaramente un tempo inaccettabile.

Ecco quindi che la distinzione tra problemi “trattabili” e problemi “intrattabili” viene data in base al tipo di funzione che esprime il numero di passi necessario per i suoi algoritmi risolutivi. In particolare, se è noto un algoritmo risolutivo per il quale tale funzione di complessità è polinomiale, cioè il problema ammette un algoritmo polinomiale, allora il problema è detto trattabile (cioè, si dice che appartiene alla classe P). Se invece si è dimostrato che ogni possibile algoritmo risolutivo ha una funzione di complessità esponenziale, il problema è intrattabile (cioè, si dice che appartiene propriamente alla classe EXP).

Mentre nel primo caso basta trovare un solo algoritmo polinomiale per definire il problema come trattabile, nel secondo caso la dimostrazione deve essere condotta prescindendo da specifici algoritmi, dal momento che l’insieme dei possibili algoritmi risolutivi è infinito e il fatto che un algoritmo di complessità polinomiale non sia stato finora trovato non implica che non esista.

Per discutere questa situazione da un altro punto di vista e far comprendere meglio che l’intrattabilità non può essere risolta con gli avanzamenti tecnologici, consideriamo cosa accadrebbe se avessimo un computer mille volte più veloce di quelli attuali. Avendo allora a disposizione 12 giorni, saremmo in grado di risolvere il secondo problema per un milione di città invece che per 100.000. Nel caso del terzo problema, nello stesso tempo di 12 giorni riusciremmo a passare solo da 50 a 60 città!

Il prossimo post, l’ultimo dedicato agli algoritmi, prenderà in considerazione una situazione di confine fra la trattabilità e l’intrattabilità molto rilevante sia da un punto di vista culturale che pratico.

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

sabato 9 novembre 2024

Strolling through informatics #7 – Can we always find an algorithm?

previous #6 ––– next #8

by Enrico Nardelli

(versione italiana qua)

The question we left off with in the previous post (Understanding algorithms isn't hard) was whether it's always possible to find the algorithm to perform the processing we have in mind.

For this purpose, we first need to clarify that the situations to which we can apply algorithms require that it be possible to describe precisely both the set of possible input data to the algorithm itself and the set of acceptable output results, expressed as a function of the inputs. But even for problems that can be formulated in this way, we'll see below that the answer is negative. We should add that the description is sometimes done, for algorithms that never terminate because the processing they must perform should not stop, with reference to a specific time interval.

Let's now consider four problems that present different characteristics in terms of computability (the names that denote the field of informatics concerned with these aspects), which will be discussed in this and the next post.

A first example of a problem (called "sorting") that can be approached algorithmically takes as input a list of N integers and requires as output the list of numbers ordered by increasing value.
A second example of a problem (called "shortest paths") takes as input a list of N cities, for each of which a list of cities (belonging to the list itself) is specified to which they are directly connected by a road segment whose length is given. The output requires, for each pair of cities P and Q in the list, the sequence of road segments that leads from P to Q with minimum total length.
A third example (called "traveling salesman") has the same input as the second, but the output requires obtaining a sequence of road segments that passes through all the cities in the list exactly once and has minimum total length.
A fourth problem (called "halting") takes as input a specific program written in a particular programming language and any of the possible input data to the program. The required output is "TRUE" if that program processing this data stops after a finite time, "FALSE" otherwise.

We observe that the algorithm, to be such, must "work," that is, produce the correct output, for all possible inputs. This means, for the first problem, for all possible lists of N numbers; for the second and third problems, for all possible lists of N cities with all possible connections to adjacent cities; for the fourth problem, for all possible programs written in the chosen language and all their possible input data.

For the first three problems described above, solving algorithms exist, so these problems are said to be computable, while the fourth problem, the halting problem, admits no solving algorithm, and is therefore an incomputable problem. At this point someone might think, given that an algorithm must anyway be expressed in a particular programming language through a program that must be executed by a particular automaton, that it would suffice to have a more modern language or a more powerful automaton.

This is not the case. It was Alan Turing himself who demonstrated, in the 1936 scientific article that is considered the birth of informatics as an autonomous scientific discipline, that the fourth problem is not intrinsically solvable, regardless of what the programming language or automaton used might be. In other words, no algorithm exists for the halting problem.

I emphasize that this result remains true even considering "quantum" type automata (which are the theoretical model of the so-called "quantum computers" much talked about in recent years). This is an extremely important result, not only from a cultural standpoint but also on a philosophical level, because it defines very precise limits to what can be achieved through computers and, therefore, also to our possibility of "knowing" something through algorithmic procedures. This cannot but please us, given that as human beings we have at our disposal other ways of "knowing," which go beyond the absolute mechanical rationality of an automaton and which the latter do not possess.

In the next post we will deal with the time necessary for executing algorithms and how this can vary from acceptable situations to others that are completely unsustainable.

A passeggio con l'informatica #7 – Possiamo sempre trovare un algoritmo?

precedente #6 ––– successivo #8

di Enrico Nardelli

La domanda con cui ci siamo lasciati nel post precedente era se sia sempre possibile trovare l’algoritmo per effettuare l’elaborazione che abbiamo in mente.

A questo scopo bisogna prima di tutto chiarire che le situazioni alle quali possiamo applicare gli algoritmi richiedono che sia possibile descrivere con precisione sia l’insieme dei possibili dati di ingresso (detto input ) all’algoritmo stesso che l’insieme dei risultati in uscita (detto output ) accettabili, espressi in funzione degli input. Ma anche per i problemi formulabili in questo modo, vedremo nel seguito che la risposta è negativa. Aggiungiamo che la descrizione viene eventualmente fatta, per algoritmi che non terminano mai perché le elaborazioni che devono effettuare non si devono interrompere, con riferimento a un determinato intervallo temporale.

Consideriamo adesso quattro problemi che presentano caratteristiche diverse in termini di computabilità (o calcolabilità, i termini che denotano il settore dell’informatica che si occupa di questi aspetti), che verranno discusse in questo e nel successivo post.

Un primo esempio di problema (detto “ordinamento”) affrontabile algoritmicamente prevede in input una lista di N numeri interi e richiede in output la lista dei numeri ordinati per valore crescente.
Un secondo esempio di problema (detto “cammini minimi”) prevede in input una lista di N città, per ognuna delle quali è specificato un elenco di città (appartenenti alla lista stessa) alle quali esse sono connesse direttamente da un tratto di strada di cui viene data la lunghezza. In output si richiede, per ogni coppia di città P e Q dell’elenco, la successione dei tratti di strada che porta da P a Q che ha lunghezza totale minima.
Un terzo esempio (detto “commesso viaggiatore”) ha lo stesso input del secondo, ma l’output richiede di ottenere una successione di tratti di strada che passi per tutte le città dell’elenco una volta sola e abbia lunghezza totale minima.
Un quarto problema (detto “arresto”) ha come input uno specifico programma scritto in un determinato linguaggio di programmazione e uno qualunque dei possibili dati di ingresso al programma. L’output richiesto è “VERO” se quel programma elaborando questi dati si arresta dopo un tempo finito, “FALSO” altrimenti.

Osserviamo che l’algoritmo, per essere tale, deve “funzionare”, cioè produrre l’output corretto, per tutti i possibili input. Ciò vuol dire, per il primo problema, per tutte le possibili liste di N numeri; per il secondo e il terzo problema, per tutte le possibili liste di N città con tutte le possibili connessioni a città adiacenti; per il quarto problema, per tutti i possibili programmi scritti nel linguaggio scelto e tutti i loro possibili dati di ingresso.

Per i primi tre problemi sopra descritti esistono algoritmi risolutivi, quindi si dice che i problemi sono computabili, mentre il quarto problema, quello dell’arresto, non ammette alcun algoritmo risolutivo, ed è quindi un problema incomputabile. A questo punto qualcuno potrebbe pensare, visto che un algoritmo deve essere comunque espresso in un determinato linguaggio di programmazione mediante un programma che deve essere eseguito da un determinato automa, che basterebbe avere un linguaggio più moderno o un automa più potente.

Non è così. È stato proprio Alan Turing a dimostrare, nell’articolo scientifico del 1936 che viene considerato la nascita dell’informatica come disciplina scientifica autonoma, che il quarto problema non è intrinsecamente risolvibile, a prescindere da quale siano il linguaggio di programmazione o l’automa usati. In altre parole, non esiste un algoritmo per il problema dell’arresto.

Sottolineo che tale risultato rimane vero anche considerando automi di tipo “quantistico” (che sono il modello teorico dei cosiddetti “computer quantistici ” di cui molto si parla in questi anni). Si tratta di un risultato importantissimo, non solo dal punto di vista culturale ma anche su un piano filosofico, perché definisce dei limiti ben precisi a ciò che può essere realizzato mediante i calcolatori e, quindi, anche alla nostra possibilità di “conoscere” qualcosa attraverso procedimenti algoritmici. Il che non può che farci piacere, visto che come esseri umani abbiamo a nostra disposizione altri modi di “conoscere”, che esulano dall’assoluta razionalità meccanica di un automa e che questi ultimi non possiedono.

Nel prossimo post ci occuperemo del tempo necessario per l’esecuzione degli algoritmi e di come questo possa variare da situazioni accettabili ad altre del tutto insostenibili.

6 novembre 2024