Retry Windows and the Limits of Idempotency

When calling a remote service in a distributed system, it is not possible for the client to know if the operation was successfully applied if the operation times-out.

The issue is then how do you prevent the operation from happening more than once?

What we want is a remote operation that produces the same final state no matter how many times it is invoked. We track the identity of the operation with an operation name.

By building a remote call that produces the same final state for a supplied name, it does not matter how many times the caller invokes it. If the client makes another call after a time-out, but a previous call had completed the operation, the service can tolerate the additional invocation without reapplying it.

Why might this be necessary?

Distributed system failure

In addition to a client timing-out, remote calls fail in ways that make it impossible for the caller to know what happened:

• The service applies the operation, then crashes before replying
• The client may retry because of a timeout even though the server had already completed the operation
• The service may have successfully applied the operation, but the response may be lost
• The network may duplicate the request

Services in distributed systems operate using the triple: receive-apply-respond. An error may occur at any point and it is not possible for the client to know what happened. The client only knows an error has occurred that may trigger a reapplication of the remote call. However, it is possible that the service fully applied the operation and crashed during the respond phase.

There is a significant amount of computing and networking infrastructure in between a client and remote service that the client has no control over. This can produce a timeout at the client even though the operation may have been successfully applied at the service. Local information at the client says there has been an error (the timeout) so the client reapplies the remote call, and the service cannot distinguish the duplicated call.

The network in between the caller and the service is also subject to failure. Responses can be lost and requests can be duplicated.

These are rare but they can happen. For example, with REST over HTTP over TCP/IP, the TCP channel will retransmit lost packets, but only if the connection is still alive. If the connection has been torn down, the client sees failure.

REST requests can be duplicated by the application layers above TCP. For example, mobile devices operate on unstable radio links. When the radio layer drops, the network stack of the mobile device's operating system may re‑send the last unsent or partially‑sent HTTP request. Some mobile operating systems behave this way: the mobile device initiates an HTTP POST, the signal is dropped mid-request as the device is moving from network to WiFi so the operating system tears down the TCP connection, re-opens a new connection and re-sends the POST because the operating system believes the previous one failed.

In short, the client cannot reliably know whether the previous operation succeeded.

As the client cannot know what the service has done, and the client may invoke the service multiple times for the same application-level operation, the server must be designed so that an operation is performed at most once.

The service must be able to tolerate the imperfect information the client is basing decisions on.

Idempotency

An idempotent operation is one that, when repeated, produces the same final state as if it were done once.

Put mathematically, a function f is idempotent if f(f(x)) = f(x).

Marking an email as read is an idempotent operation. If the email is unread, marking it as read changes the state to read. If the email is marked as read, setting it to read does not alter the state so the same final state is produced.

By contrast, pressing "volume up" is not idempotent. Each press of the "volume up" button increases the volume; repeating the action changes the final state each time.

It is not possible to implement the mathematical definition of idempotency in a distributed system because a client cannot know whether an operation successfully ran.

Partial failure aside, a client may invoke a service. The service receives the request and successfully applies it but the client, independent of this, times-out. The client's recovery strategy from time-outs is to retry the call.

In this case, neither the client nor the service has failed but the client code interprets the time-out as the operation having not been applied when it has.

Not only are distributed systems characterised by partial failure, they are also characterised by partial information. The client receives a time-out so it is never informed whether the operation was applied or not. The only information available to the client is the time-out so the call is retried.

An idempotent design

To design a service that exhibits idempotent behaviour we must consider what the service should do so that repeating the request does not change its final state.

This requires three separate design points:

1. Name the operation
2. Store the state
3. Short-circuit repeats

As we will see, appropriately naming the operation is the key.

Naming

Naming in distributed systems can be a challenge.

The important quality for a named operation to be applied idempotently in a distributed system is that the name is unique. With a unique name, the service can correctly determine whether to apply the operation once or reject any other attempt, for that same name.

Two characteristics must be true.

It must be true that, over time, no two clients can generate a name that is the same.

Two calls from the same client must be distinguishable over time.

If the first was not true, the service could not distinguish between calls from different clients.

If the second was not true, the service could not distinguish between calls from the same client over time.

A model of uniqueness

Intuitively, when we consider uniqueness we think of unique through time: unique then, unique now, and always unique in the future.

In this model, once a unique operation name has been generated, that value must never be generated again.

A deterministic function will repeat an output if its input repeats, so the only way to guarantee uniqueness through time is to guarantee that the input to a deterministic function never repeats.

This prevents the input value being drawn from a series that can be rewound or reset. Computer clocks, counters, process identifiers that cycle round, or state that can be reset or rolled-back might return to a previous state. With a deterministic function this previous state will generate a value that has been seen before, breaking the "unique through time" requirement.

Implementing this model with TPM

The Trusted Platform Module (TPM) is a dedicated security processor that provides a set of security functions that the operating system cannot fake, reset, or bypass.

A TPM has its own CPU and secure non-volatile RAM, cryptographic capabilities, and anti-tamper and anti-rollback protections.

It is isolated from the main CPU and operating system. Both the Linux root user and Windows Administrator cannot extract the TPM's private keys.

Typical TPM Features

1. Hardware‑rooted identity via a manufacturer‑fused Endorsement Key (EK)
2. Secure key generation and storage, e.g., disk encryption with BitLocker or LUKS2
3. Measured boot via cryptographic hashes of firmware, bootloader, kernel and drivers
4. Remote attestation so what software was booted can be shown
5. Monotonic counters that only increase, never repeat, and can survive power cycles
6. Sealed storage that can encrypt data that is only decrypted if certain TPM keys exist
7. Anti‑rollback protection so counter values and other state cannot be replayed

A combination of the Endorsement Key and a monotonically increasing counter gives a globally unique value through time.

The EK is unique per machine. Two processes on the same machine can generate:

EK_ID COUNTER_A EK_ID COUNTER_B

the TPM hardware guarantees that COUNTER_A and COUNTER_B are different. As the counters are only monotonically increasing, the combined identifier of "EK_ID COUNTER" will be globally unique over time.

A physical TPM satisfies our uniqueness model.

An Exception

If a virtual machine is being used, COUNTER can be reset. This is because the state used by the virtualised TPM is part of the VM's state which can be reset.

Therefore:

EK_ID COUNTER_A

could be generated and the VM rolled back to an earlier state and:

EK_ID COUNTER_A

then might be generated again.

Using a virtual TPM breaks out uniqueness model.

The Uniqueness Requirement

The important quality when naming an idempotent operation is that the name is unique so that the service can unambiguously distinguish a call.

The notion of a globally unique name through time is over-specified to implement idempotency, although access to such names in a distributed system is useful.

For idempotency, what is required is an operation name that can be recognised as referring to a previously seen operation.

In the vTPM exceptional case, a reset of a VM would cause a client to send an ID that had been seen before, whereas without the VM reset, a new ID would have been sent.

As the ID is repeated, the operation would not be applied. In this sense, the design is safe, although a new name should have been generated and the operation applied or failed.

Unique at the moment

The requirement of an idempotent service is one that does not apply an operation twice in the face of the client retrying (rightly or wrongly) based on its local information: the client may retry as its service invocation times-out.

It is assumed that retries are issued within a small window of time. In this case, as long as the identifier is unique within that window, the service will remain idempotent.

We have relaxed (removed the need for) the "unique over time" requirement so that idempotency can be implemented.

Store the state

So that the service can detect repeated invocations, it must persistently store incoming operation names.

Short-circuit repeats

During the retry window, the stored operation name ensures an operation will only be applied once.

Before an operation is applied, the persistent state is checked, using the client-provided operation name as a key.

If the key has been seen before and the previous operation outcome was marked as 'applied', the operation previously succeeded, so the current invocation is a repeat and the previous result can be sent back to the client without reapplying the operation.

If the key has been seen before and the previous operation outcome was marked as 'failed to apply', the operation has previously been issued from a client, but it has failed and has not been applied. However, in this case, this failure status must be sent back to the client.

This is because idempotency requires that a failed operation (made over several calls) produces the same final state, for that name. If this was not the case, and the previously failed operation was subsequently applied, the operation name would have been associated with a failed operation, and then a successful operation. This breaks idempotency as more than one state is associated with the operation name.

Once an identifier is associated with a failed operation, it must remain failed. To apply the operation, a new identifier must be used.

Here we define a distributed systems version of idempotency where only one state can be associated with an operation name.

The retry window

In the above design, idempotency holds during the client's retry window.

The outcome of that window is either a successfully applied operation or a failed operation, and if the operation failed, the client must issue a new operation signalled by a new identifier.

The question now becomes "what if a retry is attempted outside the retry window". There is a solution for this but a different approach is required that will be discussed in an upcoming article.

Conclusion

Mathematical idempotency is not possible in a distributed system due to partial information.

Operational idempotency is shown above. In distributed systems this is a service‑side guarantee that, for a given operation name, only one final state will ever be associated with that name despite client retries caused by partial failure or partial information. This guarantee is bounded to the retry window and depends entirely on the trustworthiness of the operation name during that window.

Read next: What Python async exposes that synchronous code hides
Async shows you the hidden waits and coupling that your synchronous code masks.

Related Articles

• The Myth of Complete Specifications
• Vibe Coding Is Not Engineering
• Why Junior Engineers Matter More as AI Expands
• Chat Interface to System Component
• The Limits of Stateless LLMs