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.

[[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 27 November 2024.