Two Generals’ Problem and Idempotency

Introduction:

The Two Generals’ Problem is a thought experiment in computer science and distributed systems that highlights the challenge of achieving reliable communication over an unreliable network. The problem remains unsolved and it illustrates the inherent difficulty in coordinating actions between two parties (generals, in this case) when messages can be lost or interrupted.

The Setup:

• Two generals are stationed on opposite hills, and they want to coordinate an attack on a city between them.
• Both generals must attack at the same time for the attack to be successful.
• The only way for the generals to communicate is by sending a messenger across the valley between them, but the messenger might be intercepted or lost.

The Problem:

The problem arises when the generals try to reach a consensus.

Two Generals’ Problem

Since the requirement is to attack to the castle at the same time and one army is not enough to capture the castle, generals need to communicate and decide when to attack together. Here this lack of common knowledge causes an inconsistent state.

To illustrate the situation:

General B might start by sending the message, “Let’s attack down at 10:00 on June 1st.” After sending this message, General B cannot be sure whether the messenger has reached the target or whether it has been captured. Because of this uncertainty, General B hesitates to attack. As a solution, we can think of General A sending a confirmation to General B saying, “I have received your message to attack at 10:00 on June 1st.” However, this messenger may also be in danger of being captured, and General A hesitates to attack this time, knowing that General B may not attack if the messenger is captured. Again, we can think of a solution for General B telling General A, “I have received your confirmation to attack at 10:00 on June 1st.” However, again, this messenger may be captured.

So at this point we begin to understand that there is no guarantee that the two generals will agree on a plan of attack, no matter how many rounds of confirmations are made.

Let’s examine some possible scenarios:

1.) If the messenger sent by General B is captured at first attempt, General A will not get any message and General B will not get any confirmation so there will be no consensus to attack together.

2.) The messenger sent by General B reached to General A. General A sent a confirmation to General B but the messenger is captured. Then General B will think the message is not received by General A and there will be no consensus to attack together.

3.) The messenger sent by General B reached to General A. General A sent a confirmation to General B and the message is received by General B. In this case General B will still think that General A can hesitate to attack because he cannot be sure if his confirmation is reached to General B. Therefore a confirmation of confirmation is necessary and there will be no consensus to attack together.

As can be seen, each scenario leads to an inconsistency without a consensus due to the unreliability of the communication path.

Comparison with TCP:

TCP uses a three-way handshake to establish a reliable connection, using SYN, SYN-ACK and ACK. But this is only to understand if both sides can send a message to each other without checking the content of the message. Then when sending an information from one entity to another, TCP provides Duplicate cumulative acknowledgements and Timeout-based retransmissions to be able to sure the message is transferred to the other side. That implies that TCP allows retries which is not the case in Two General’s Problem in which we need a consensus between the entities on a subject without retries.

In Two General’s Problem, each time a message is exchanged, there is a chance it could be lost. As more messages are exchanged, the likelihood increases that at some point, a message will be lost, breaking the sequence.

In TCP, the ultimate target is sending an information to another entity reliably. If we would check the content and try to come up with a consensus with confirmations but without retry, we will end up with the same inconsistency problem as in the Two General’s Problem.

Therefore, although TCP is a very reliable protocol, it doesn’t solve the Two General’s Problem because any remote communication is not 100% reliable, network is not reliable!

Two Generals’ Problem Mitigations:

So if we accept the uncertainty of this communication channel we can try to mitigate it to some extend that we would think be sufficient.

Sending many messengers: Using a serial number

Let’s say General B sends 100 messengers assigning a serial number from 1 to 100 to each. As long as at least 1 messenger pass through General A will get the message, and can also determine the reliability of the channel by looking at the missing numbers in sequence, and adapt the number of confirmation messages.

If we think TCP again, in TCP actually similarly there is a sequence number to capture any missing messages, and to resend them based on the duplicate acknowledgements received.

Just to note, Kafka exactly once delivery, also uses a similar approach, with a sequence number. But instead of keeping the sequence number in memory as in TCP, it persists that to Kafka so that even after restart it will keep enforcing exactly once delivery.

Sending a messenger for every N minutes

Let’s say General B sends a message and waits N minutes where N is the time to cross the valley, give the message and come back. If there is no confirmation comes in N minutes, General B can just retry the same message. So here we change the condition and start allowing retries as a mitigation. If General B gets a confirmation and does not retry, then General A thinks that his confirmation is received because of the absence of retry message.

Considering TCP this is similar to Timeout-based retransmission.

Again this is a mitigation and not 100% reliable because there is always a chance that all retry messages from General B can be captured in an unreliable network which could still leads General A to think that General B got the confirmation.

The mitigation strategies to Two Generals’ Problem have a side effect, the receiver will receive the same message more than once. So in that case if we consider computer systems, if the message is received once and processed, what will happen when it is received again? In many cases it should not be processed again, and instead be ignored, or just a confirmation would be sent again.

A receiver that can do that is a so called Idempotent consumer. So this brings us to the concept of Idempotency.

Idempotency:

By definition, Idempotency is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application.

It provides at-most-once guarantee and allow retry operations safely.

Within a non-distributed system, calling a component in the same network, such as function calls, can succeed or fail. However when calling a remote component, it’s impossible to know whether the call reached the component or not because a problem can occur on the way to or the way back.

From an API standpoint, idempotency means clients can make the same call repeatedly and produce the same result. As a result, it is necessary to apply deduplication on the receiver using a unique key. This unique value is generated by the client and expires after a certain period and UUID is the most commonly used type as an idempotency key.

Idempotency Implementation:

Idempotency is implemented on the receiving side by asking the question to a persistent store, have I seen this before?

It is typically implemented with a database that enforces a unique constraint because an in-memory solution can lead to memory overload and may not be reliable in multi-instance environments without complex locking mechanisms.

When to persist the Idempotency key? There are two approaches:

Eager: Insert before handling the message. This will require a clean-up if handling the message fails.

Lazy: Insert after handling the message. In this case be sure to use the same transaction with handling the message and persisting the idempotency key, to roll back the handle message logic in case idempotency key already exists.

Considering the concept of the application it is also wise to ask following questions while handling a duplicate key:

Is ignoring the event correct?

You may want to throw an error in the case of duplicates, perform additional operations such as cleanup, or simply ignore them.

Why have I seen this event again?

You may see the event again due to network issues, retries or lost acknowledgments in distributed systems, and idempotency ensures that processing it multiple times has no adverse effects.

How long should we keep that event id in database to check the duplication?

The event ID should be kept in the database for a duration that covers the maximum expected time for retries or processing delays, typically based on the system’s retry policy and SLAs. This could range from a few seconds for simple retries to several days if the operation may be retried later.

Idempotency and HTTP APIs:

In the context of HTTP APIs, GET, PUT, DELETE, HEAD, OPTIONS, and TRACE are idempotent. If you repeatedly delete an entity from the system, whether the entity exists or not, the end state will be the same, there will be no entity. On the other hand POST and PATCH operations are not idempotent. Posting multiple times, a new entity will create that many new entities. Patch is also not a safe and idempotent operation if the following cases are used in a Patch request:

• Adding a value to a list
• Incrementally updating a value based on previous value
• Using previous value in where condition of any query

Solution for unsafe Post and Patch operations is provided by IETF specification using Idempotency. The Client sending a request sends a unique key along and the server keeps track of key-request pairs. Server has to options:

• The server already has a record of such a pair and discards the request
• The server has no such previous record and stores the pair

The Idempotency-Key HTTP header: A string value. The specification uses a UUID as an example. It’s the client’s responsibility to generate such a value, which must be unique.

According to IETF specification an approach to implement Idempotency in a web application could be adding a web filter with the following steps:

• Create a table with Key (UUID), Hash of Request(byte[]), Response(String) columns
• Apply this filter only for post and patch requests
• Check Idempotency-Key header, if empty, write error to response
• Get hash of request body (+headers, cookies etc. depending on the use case)
• Insert key, hash pair to DB
• In case of an exception during insertion of key and hash pair, check existence of the key in DB and if the hashes between the request and the DB are not equal write error to response. If they are equal Check DB record for response column and return the response. If the response column is empty write error to response with message “A request with the same Idempotency-Key for the same operation is being processed or is outstanding"
• Call the next filter
• In case of exception throwed from the next filter, delete the the idempotency entity, otherwise update the idempotency database row with the response

Conclusion:

The Two Generals’ Problem demonstrates that in certain scenarios, it is impossible to achieve 100% reliable coordination over an unreliable communication channel. No amount of message exchange can guarantee that both parties are fully synchronized because of the inherent risk of message loss.

In distributed computing, this problem is used to explain the difficulty of ensuring agreement or coordination in the presence of unreliable networks. It’s related to the broader field of consensus problems and has implications for designing fault-tolerant distributed systems.

The mitigations of the Two Generals’ Problem uses retries which brings a new problem on the receiver side, handling the duplicate messages. Consumers that can handle duplicate messages are called Idempotent consumers which allows safe retries. Idempotency allows to make the same call repeatedly while producing the same result.