(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 N2. 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.
Nessun commento:
Posta un commento
Sono pubblicati solo i commenti che rispettano le norme di legge, le regole della buona educazione e sono attinenti agli argomenti trattati: siamo aperti alla discussione, non alla polemica.