A system can contain nondeterministic parts and still provide deterministic behavior. But determinism only makes sense relative to two things: a boundary, and an observable property at that boundary.
The question is not whether everything inside the system behaves the same way every time. The question is: what must remain the same when the system is observed from the outside?
Deterministic behavior
Suppose a system receives a state S and produces an observable result y. We can write f(S) = y. The system is deterministic for that property if the same relevant state always produces the same observable result.
Consider a navigation system at an intersection. The observable property is the selected direction. LEFT reaches the destination in 800 metres. STRAIGHT reaches it in 1,400 metres. RIGHT does not reach it.
The rule is to choose the shortest valid route. For this state, f(S) = LEFT. Given the same state and the same rule, the result remains LEFT. A complete rule also defines what happens when routes tie or no route is valid.
Internal details may vary. The computation may take a little longer. Operations may happen in a different order. That does not matter as long as the observable result remains the same.
Nondeterministic behavior
Now consider a process where the same relevant state can produce different observable results. For the same S, it may return g(S) = LEFT on one execution and g(S) = STRAIGHT on another.
If the observable property is direction, the process is nondeterministic at that boundary. Variation becomes important when it changes what crosses the boundary.
The boundary must know enough
A wrapper cannot make a result deterministic simply by sitting around a nondeterministic process. It needs enough authoritative information to resolve the variation independently.
Return to the intersection. Suppose an internal process sometimes proposes LEFT and sometimes STRAIGHT. If the boundary independently knows the available roads, their distances and the rule to apply, it can determine that LEFT is the correct outcome under that rule regardless of the proposal.
If it knows nothing except the proposal it receives, it cannot establish the shortest route. Passing that proposal through has not contained nondeterminism. It has only moved it.
This gives us the key condition: a deterministic boundary needs enough authoritative state and rules to determine the observable result independently of the variation below it. There are several common ways to achieve this.
Canonicalization
Canonicalization is used when different representations mean the same thing. Suppose different sources provide Switzerland, SWITZERLAND, CHE or CH. In this country field, the representations differ, but they refer to the same country.
A canonicalization rule maps them all to one representation: CH. So c(“Switzerland”) = CH, c(“CHE”) = CH and c(“CH”) = CH.
The inputs vary. The value exposed at the boundary does not. Canonicalization works when several valid forms can be reduced to one defined form.
Reconstruction
Reconstruction is used when the correct structure already exists, but its pieces are observed unpredictably. Suppose a file is divided into five pieces: 1, 2, 3, 4, 5. They may arrive over a network as 1, 3, 2, 5, 4.
The arrival order varies. But each piece contains information identifying where it belongs. Once all the pieces are available, the receiver reconstructs 1, 2, 3, 4, 5. The protocol does not choose an order. It recovers the existing one.
TCP over IP illustrates this broader principle. Network delivery may be delayed, duplicated, lost or reordered. TCP uses sequence information, acknowledgements, buffering and retransmission to present an ordered byte stream to the application.
The network remains unpredictable. The order of the bytes delivered above it does not. Timing and successful completion are separate concerns: a failed connection may never deliver the whole stream, and individual application reads may group the bytes differently.
Convergence
Convergence is used when different parts of a system may follow different paths but are designed to reach the same state once they have received the same updates.
Consider two phones sharing the same contact list. For this example, contacts can only be added, and merging keeps every name found on either phone. Both begin with Alice. The first phone adds Bob while offline, so it contains Alice and Bob. The second adds Carol, so it contains Alice and Carol.
For a while, the two states differ. When the devices reconnect and exchange all their additions, both contain Alice, Bob and Carol. Merging the sets in either order produces the same membership.
The paths and intermediate states were different. With the same additions and merge rule, the final observable state is the same. That is convergence. Deletions or conflicting edits would need their own defined rules; reconnection alone does not resolve them.
When the boundary cannot resolve the variation
Sometimes there is not enough information. Suppose the system knows that either LEFT or STRAIGHT is valid, but has no authoritative information that distinguishes them. If its contract requires a uniquely justified choice, it should not choose arbitrarily. It can return a defined unresolved state such as STOP.
This is still deterministic behavior. The rule can be: if one valid result can be established from the authoritative state, return it; if not, return STOP. A fixed tie-breaking rule could also be deterministic, but it would be a different contract.
A deterministic system does not need to create certainty where none exists. It needs defined behavior when certainty is unavailable.
Where nondeterminism ends
Canonicalization, reconstruction and convergence solve different problems. Canonicalization reduces different forms to one representation. Reconstruction recovers an existing structure from unpredictable observations. Convergence allows different delivery orders and timing to lead to the same state once the same updates have been incorporated.
What they have in common is more important than the mechanism. They define a boundary where specified variation below it no longer changes the property exposed above it, under the conditions of that guarantee.
This is not a new idea. Computer systems have relied on it for decades. TCP was documented in RFC 793 in September 1981. Networks reconstruct ordered streams over unreliable delivery. Replicated systems use defined merge rules to converge despite different update timing and execution paths. The techniques differ. The principle is the same.
Determinism does not require the absence of nondeterminism. It requires a clear boundary, a defined observable property, and enough authoritative information to prevent internal variation from changing that property.
Research basis
Jon Postel, 1981. Transmission Control Protocol, RFC 793. The September 1981 specification describes reliable, ordered delivery over a less reliable network.
Wesley Eddy, editor, 2022. Transmission Control Protocol, RFC 9293. The current TCP specification sets out the byte-stream service, sequencing and retransmission mechanisms.
Nuno Preguiça, Carlos Baquero and Marc Shapiro, 2018. Conflict-free Replicated Data Types (CRDTs). An overview of replicated data types whose merge rules ensure that replicas receiving the same updates reach the same state.