Parallelism, Concurrency, and Synchronization

Work is partitioned, branches execute, a shared-state rule keeps them from colliding, and a join decides what the run actually produced. Whoever owns the join should not also own cancellation. Neither test covers the other.

A production orchestrator shows why they are two tests. In a Parallel state the branches all run at once, and the interpreter waits for every one of them to terminate. A Map state takes a MaxConcurrency field: an integer upper bound on how many iterations may run in parallel. The Amazon States Language specification, revised in 2024, writes both of those down. Fan-out width and join semantics are part of the workflow. Cancellation is not written down beside them.

Something does survive a failed fan-out, and the AWS Step Functions Developer Guide says what: “When a parallel state fails, invoked Lambda functions continue to run and activity workers processing a task token are not stopped.”

The branch has ended and the side effect has not. A join that reports a clean failure is telling the truth about the branches and nothing at all about what they left running.

The failure two branches produce when they edit the same thing already has a name, a paper, and an exact interleaving. The name is P4, Lost Update. It was catalogued in 1995, in a critique of the ANSI SQL isolation levels. The definition there is the whole mechanism in one sentence: “P4 (Lost Update): The lost update anomaly occurs when transaction T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits.”

The history the paper prints is six operations long: H4 = r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1. Both transactions read 100. T2 writes 120 and commits. T1 still holds the value it read before T2 existed. It writes 130 and commits. Nothing raises an error, no lock is violated, and both branches report success. The committed update of T2 is gone. The surviving state, 130, was computed from a value that had already stopped being true.

Two agent branches editing the same configuration reproduce H4 exactly. Tool calls stand in for the reads and writes, and each branch's local tests pass on its own copy.

The same paper adds a second anomaly, P0 (Dirty Write). ANSI SQL-92 does not mention it. The paper concludes that ANSI SQL isolation should be modified to forbid P0 at every isolation level. The guarantee level a system advertises may not exclude the anomaly you actually have.

Parallelism can reduce latency when branches are independent or when several evidence paths can be explored simultaneously.

Concurrency becomes unsafe when branches mutate shared state, consume the same budget, or make decisions from different versions.

A coordinator should define branch inputs, write ownership, synchronization points, cancellation, and merge semantics before work begins. That is not a new demand made of agent runtimes. Kung and Robinson set it out in 1981, as a requirement rather than a convention: “It is required that any transaction consist of two or three phases: a read phase, a validation phase, and a possible write phase (see Figure 1).”

The order carries the safety. The read phase runs on local copies, so nothing shared has moved yet. The validation phase then decides whether the work is allowed to land. Only after it passes does a write phase touch shared state.

The validation condition is three alternatives on the intersection of read sets and write sets. That is the merge rule stated in advance, in terms of what each branch read and what it now wants to write. A coordinator that decides its merge rule after the branches have landed has deleted the middle phase and kept its name.

Independent parallel calls, optimistic concurrency, and uncontrolled shared mutation are three answers to one question: who is allowed to write.

Only one of the three is written down as a standard. HTTP has a request header for exactly this problem. RFC 9110, published in 2022, says what If-Match is for: “If-Match is most often used with state-changing methods (e.g., POST, PUT, DELETE) to prevent accidental overwrites when multiple user agents might be acting in parallel on the same resource (i.e., to prevent the "lost update" problem).” The obligations are normative. An origin server MUST evaluate the condition before performing the method, MUST NOT perform the method if the condition is false, and MAY respond 412 (Precondition Failed). For a resource used as a semaphore, the RFC advises that the server is “better off being stringent in sending 412 for every failed precondition on an unsafe method.”

That is what optimistic concurrency looks like on the wire: the version a branch read, sent back with the write, and a numbered refusal — 412 — when the version has moved. Independent parallel calls avoid the question entirely. Every branch gets immutable inputs and a separate artifact, so no refusal is ever needed. Uncontrolled shared mutation has no refusal to issue. Every branch succeeds. The difference shows up only in the final state, as it did in H4, after everything has already committed.

The strategy is working when parallelism reduces latency without increasing final-state conflicts. It is failing when parallel agents agree because they copied the same error — an agreement that looks like confirmation and is not.

One stage of one workflow, made safe to run in parallel: name the write owner, the join, and the cancellation rule before adding a branch. Then test the design rather than admire it.

That test is more tractable than it sounds. In 2008 four researchers examined 105 randomly selected real-world concurrency bugs from MySQL, Apache, Mozilla and OpenOffice, and reported: “About 92% of the examined concurrency bugs can be reliably triggered by enforcing certain orders among no more than 4 memory accesses.” A race that appears to need luck to reproduce usually needs an order among four or fewer shared accesses. That is small enough to enumerate for a stage you designed yourself, and to force on purpose in a harness.

Two of their other figures should change what you build, not only how you test it. About 34 percent of the non-deadlock bugs involved multiple variables, so a lock per variable is not a fix per bug. About 73 percent of the non-deadlock bugs were not fixed by simply adding or changing locks. The reflex reach for a lock was, in roughly three cases out of four in that sample, not the repair.

So: prove independence from immutable inputs, assign write ownership, version the state that must be mutated, define the join and the conflict rule, and set the cancellation rule. Then seed the branches with a shared wrong assumption and see whether they converge on it. Force the four-access orders you can enumerate. Measure whether the parallel version really finishes sooner without leaving the final state in dispute.

Parallelism is an optimization after correctness. First make one trajectory reliable, then parallelize work whose dependencies and merge rules are understood.

Before widening a fan-out, ask again whether the branches are independent, or whether they all inherit the same assumption from the same place. Twenty-seven versions written by different people from one shared specification did not clear that bar. The independence hypothesis was rejected at the 99 percent confidence level. Ask which write gets refused, and under what rule, before any branch starts. That is a validation phase between the read and the write, not a merge argued about afterward. And do not assume the obvious remedy is the remedy: among the 105 bugs studied, about 73 percent of the non-deadlock ones were not fixed by adding or changing locks.

The fan-out is paying for itself only when it shortens the run and the merged result is not more contested than the serial one would have been.