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.