The Unholy Trinity of Distributed Systems Hell

This post is about the algebraic properties that let a consumer running on at-least-once behave, from the outside, as if it were running on exactly-once without causing an unholy level of errors. Software that is designed to perform correctly under at-least-once delivery semantics enables a substrate to:

• Deliver the same event more than once, because a broker retried after a missed acknowledgement.
• Deliver events out of order, because it only preserves order within a single writer’s stream, not across streams or partitions.
• Deliver events batched together, because a reducer somewhere decided to combine pending work before flushing.

Every one of these scenarios is a way to corrupt a consumer on the receiving end if they aren’t prepared. The real problem occurs when a producer makes promises around these properties, like a producer will never produce duplicate messages, but then violates that promise. You should be able to recognize these properties to design cleaner APIs and understand the promises that libraries and frameworks make before using them. Some promises are nothing more than marketing and fall apart under scrutiny.

This post explores those failures in the context of a state machine, not because algebraic properties are exclusive to state machines, but because state machines make the concepts easy to demonstrate. A state machine’s transition function takes the current state and an incoming event and returns the next state. The algebraic properties that follow are properties of that function.

State machine basics

For the purpose of this post, we only need to think of the absolute basics of how a state machine works. Specifically we’ll look at a type of state machine called a Moore machine. It takes in an input like an event and applies that input to the current state to produce a new state. There is no mutation involved. The only way to transition is to feed the machine an input and capture the output as the new state. The new state is a complete snapshot of every field in the data structure.

Think about a bank example. The current state would be the sum of all bank transactions that have already happened on that account. A new transaction, like a debit, comes in, let’s say a debit against that account for $10. That $10 debit against the current state produces a new state, state prime (state’).

The purpose of this blog post is to think about how we can guard against basic flaws in our transition function. To do that we need to ask:

• What are the algebraic properties of the inputs?
• What happens if we have duplicate debits?
• What happens if we have bank transactions that come out of order?
• Or what if we have a runtime that decides to group a bunch of transactions for flow control purposes?

Will our system behave correctly?

The above diagram shows duplicated events, which is a very common failure mode in systems that lack deduplication. At-least-once delivery means literally at least once, which means duplicated events are actually expected as our API does not promise the substrate will avoid duplicates. Without a way to deduplicate at the consumer, results become incorrect quickly.

Three algebraic properties decide whether the state machine survives a stream that duplicates, reorders, or regroups events:

• Idempotence absorbs duplicates.
• Commutativity absorbs reordering.
• Associativity absorbs regrouping.

These are algebraic properties that extend well beyond math. If your systems handle retries and reorderings correctly, you are likely already applying them. Most engineers have an intuition for these even without knowing the formal terminology, as these properties are critical to designing robust APIs. Violating even one of them by accident will produce corrupted state without crashing, without warning, and without any obvious cause, which in my opinion is far worse than an outage.

One way that these properties can be violated by accident is that they go untested, because they have an awkward testing signature. They easily trick even experienced developers during code review and they are fairly hard to verify at runtime, which is a deadly combination. A function that looks idempotent in the small can still double-count under load. A function that looks commutative on three test cases can still produce divergent state on the fourth. The only way to know is to feed the function the kind of stream production will eventually feed it and watch what comes out the other side.

This post defines each property, gives Rust examples that satisfy and violate it, and walks through four adversarial trials drawn from obzenflow-fsm’s integration test suite. ObzenFlow organizes its hardest tests as six “circles of distributed systems hell,” loosely modelled after Dante. The fourth circle is the one that confronts state machines with the trinity.

What follows is each property in turn, with Rust shapes that satisfy and violate it. The section after walks through how to test for violations against the kind of stream production will eventually produce.

Idempotence

Applying the same event more than once must have the same effect as applying it once. A naive balance += amount operation is not idempotent under retries. Processing the same credit event twice doubles the balance. The fix is deduplication by a stable key such as an event ID or per-source sequence number.

// Non-idempotent: balance doubles on duplicate
let new_balance = balance.saturating_add(amount);

// Idempotent: skip if already processed
if operation_ids.contains(&id) {
    ctx.duplicate_count.fetch_add(1, Ordering::Relaxed);
    return Ok(Transition {
        next_state: current_state,
        actions: vec![],
    });
}
operation_ids.insert(id.clone());
let new_balance = balance.saturating_add(amount);

The solution is to track what has already been processed. The idempotent version above stores each event ID in a set and short-circuits on duplicates. The transition still fires and returns the current state unchanged. It emits no downstream actions on the duplicate path, which keeps the action stream itself idempotent. A counter on the context records the duplicate locally, but that counter is delivery-attempt telemetry, not a downstream effect. The deduplication rule has to be part of the state machine’s correctness story, even if the surrounding infrastructure provides the stable IDs or cursors that make it practical.

Commutativity

Swapping the order of two independent events should not change the outcome. State machines feed each new event through a function called apply that takes the current state and the event and returns the next state.

let next_state = apply(event, state);

Apply two events in sequence by feeding the first result into the second.

let state_prime = apply(e1, state);
let state_double_prime = apply(e2, state_prime);

Commutativity means the order does not matter.

let forward = apply(e2, apply(e1, state));
let reversed = apply(e1, apply(e2, state));
assert_eq!(forward, reversed);

Subtraction is commutative in this sense. Apply two Debit events of amounts a and b to balance s.

let sequential = (s - a) - b;
let reversed = (s - b) - a;
assert_eq!(sequential, reversed);

Both orderings reach the same final balance.

Appending to a list is not commutative. Apply two Append events of values x and y to an empty list.

let mut sequential = vec![];
sequential.push(x);
sequential.push(y);

let mut reversed = vec![];
reversed.push(y);
reversed.push(x);

assert_ne!(sequential, reversed);

The two final lists differ. List order is often part of the data itself. Time-series readings, audit logs, and transaction histories all depend on append order. A list reconstructed out of sequence no longer matches what the producer recorded.

When commutativity does not hold, the system must model ordering explicitly. Most messaging systems provide some form of per-source sequence number or offset. Across multiple sources the combined stream can still interleave nondeterministically unless you impose a total order or a deterministic tie-break rule.

A similar trade-off shows up at the language level. Rust atomics expose memory orderings from Relaxed to SeqCst so the caller pays only for the strength they need. Imposing a total order has a cost. Not every operation is sensitive to commutativity. Knowing which operations need it is part of the design. Claiming commutativity for an operation that does not have it guarantees data corruption.

When commutativity does hold, as with max or set-union operations, the system can relax ordering constraints and process events in parallel without risk.

Associativity

When a reducer combines events before forwarding them to the state machine, the way it groups them must not change the result. The combine operator takes two events and returns one.

let combined = combine(e1, e2);

Associativity means combining three events in either grouping produces the same result.

let left = combine(combine(e1, e2), e3);
let right = combine(e1, combine(e2, e3));
assert_eq!(left, right);

When this holds, batching and parallel folding are safe.

Addition is associative. Three values summed in any grouping reach the same total.

let left = (10 + 5) + 3;
let right = 10 + (5 + 3);
assert_eq!(left, right);

Naive averaging is not associative. Three values averaged in either grouping produce different totals.

fn naive_average(a: i64, b: i64) -> i64 {
    (a + b) / 2
}

let left = naive_average(naive_average(10, 5), 3);   // (7 + 3) / 2 = 5
let right = naive_average(10, naive_average(5, 3));  // (10 + 4) / 2 = 7
assert_ne!(left, right);

Naive averaging drops the count carried by each partial. Without the count, regrouping changes which values get more weight in the final answer.

Addition, max, set-union, and merge operations all give rise to associative combines. Naive averaging, conditional updates, and operations whose effect depends on the accumulator in a non-monoid-action way do not. When the domain admits no associative combine, the system must process events sequentially. There is no way to parallelize a non-associative fold and get the same result.

Testing for Broken Algebraic Promises

We’ve defined idempotence, commutativity, and associativity, and shown what satisfies and violates each in Rust. The remaining question is how to verify the properties at runtime. The same test shape works for all three. Build a state machine with handlers on both sides, one that satisfies the property and one that violates it. Feed the machine a stream that exercises the failure mode the property is meant to absorb.

Four trials cover the trinity:

• Trial 1: Idempotence. Flood the machine with duplicate events. The dedup handler suppresses them. The non-idempotent handler compounds them.
• Trial 2: Commutativity. Run two machines on the same events in opposite orders. The order-sensitive handler diverges. The commutative handler does not.
• Trial 3: Associativity. Compare sequential application against pre-combined deltas. The handler with an associative combine agrees. The handler without one diverges.
• Trial 4: The trip-wire. A Corrupted terminal state that fires when the machine reaches impossible territory. Theatre, but the shape is real. Detect impossible state, transition to terminal, emit alarm.

The first three trials test the trinity, one property each. The fourth tests that the machine knows when to give up.

Trial 1: Idempotence

The idempotence trial floods the state machine with deliberate duplicates and asserts that the final state reflects only the unique events. To make that possible, the test puts a deduplication set called operation_ids inside the state itself, alongside the balance and the operations log.

enum BeastState {
    Counting {
        balance: i64,
        operations: Vec<String>,
        operation_ids: HashSet<String>,
    },
    Overflowed,
    Corrupted(String),
}

operation_ids lives inside the state, not in a side cache. Putting dedup memory inside the state machine is what lets the transition function be reasoned about as a deterministic function of state and event.

It’s worth pointing out that the integration test version of the state enum uses an unbounded HashSet<String>. That is good enough for a test, but inadequate for a long-running production system at production scale. Production systems approach storing previously seen IDs in some kind of known direction based on the actual system:

• A sliding-window cursor of the form “I have seen everything up to offset N” trades exact dedup for a strong ordering assumption from the broker.
• A Bloom or cuckoo filter trades correctness in the false-positive direction for bounded memory, so idempotence holds only with high probability.
• Tombstoned event IDs with TTL trade correctness in the false-negative direction. A duplicate that arrives after the TTL gets processed twice.

Each is a different correctness story, but all of them share that idempotence at very high scale may not be perfect, so trade-offs will need to be made. Which approach fits depends on the broker’s ordering guarantees and on the failure mode the application can absorb.

Here’s the scenario we’re going to test:

1. Send ten unique credit events to the machine.
2. Deliver each event three times to simulate at-least-once duplication.
3. Assert the final balance is 1000 (ten unique credits, not thirty deliveries).

The Credit handler does what the idempotence section above showed. It checks the set, suppresses the event if the ID has already been processed, and otherwise applies the credit and records the ID. The trial then drives the machine with ten unique credit events, each delivered three times under the at-least-once contract.

for i in 0..10 {
    let event = BeastEvent::Credit {
        id: format!("credit_{i}"),
        amount: 100,
    };
    for _ in 0..3 {
        machine.handle(event.clone(), &mut ctx).await.unwrap();
    }
}

assert_eq!(
    balance, &1000,
    "Idempotency failed! Duplicate credits were processed"
);

Without the dedup branch, the balance would be 3000. In a banking domain, that is a customer triple-charged on a single transaction. In an inventory ledger, it is stock that disappears three times faster than the underlying reality. In a metrics aggregator, it is graphs that lie by a factor of three on the day a queue retried. The exact pathology depends on the domain. The cause is the same though, that a non-idempotent operator under at-least-once delivery produces wrong state, and the wrongness scales with how badly the broker decided to retry.

This bug class is also one of the easiest to miss in development. Tests with a single in-memory consumer almost never see duplicates. The duplicates show up the day the queue retries, the day the consumer crashes mid-batch, the day a network partition heals, but by then the data is already wrong, and the only way to fix it is to find the right offset, replay from there, and hope the dedup set is comprehensive enough to absorb the second pass.

Trial 2: Commutativity

The commutativity trial sets up an experiment that should give two different answers. It stands up two copies of the same state machine, feeds them the same three append events in opposite orders, and then asserts that the resulting states do not match.

let append_events = vec![
    BeastEvent::Append { id: "1".into(), value: "First".into() },
    BeastEvent::Append { id: "2".into(), value: "Second".into() },
    BeastEvent::Append { id: "3".into(), value: "Third".into() },
];

for event in &append_events {
    machine.handle(event.clone(), &mut ctx).await.unwrap();
}

for event in append_events.iter().rev() {
    machine2.handle(event.clone(), &mut ctx).await.unwrap();
}

assert_ne!(
    ordered_ops, reversed_ops,
    "Operations are commutative when they shouldn't be!"
);

The assertion is assert_ne!, not assert_eq!. The trial is proving non-commutativity, not the other way around. If the two final states matched, something upstream of the handler would have silently sorted or deduplicated the events, and the implementation would be making a guarantee its author had not.

In production, commutativity fails because:

• Substrate reorders.
• Brokers reorder.
• Partitions hold independent local order but say nothing about cross-partition order.
• Parallel consumers process in non-deterministic sequence.

Any of these reorderings is fine if the operator is commutative. Max, set-union, and addition do not care which event arrives first. But they are not fine if the operator depends on order.

Knowing the operator is non-commutative pushes the burden upstream. Either the producer assigns sequence numbers, or the consumer sorts on a stable key, or the architecture commits to a single partition for all events that share an aggregate. None of those choices is automatic. They are the consequences of intentional software design decisions.

Trial 3: Associativity

The associativity trial runs two sub-experiments. The first checks that a debit handler is safely batchable when its payloads are combined by addition. The second checks that a handler with no associative combine on payloads breaks under regrouping.

For the debit case, two state machines start at 100. The first receives two Subtract events of 10 and 5. The second receives a single Subtract whose value is the addition of the two payloads. Both end at 85. The combine operator on debit payloads is addition, addition is associative, and the FSM produces the same final state whichever schedule the upstream chose.

// Sequential: (100 - 10) - 5 = 85.
let mut sequential_debits = build_subtract_machine(100);
sequential_debits
    .handle(BeastEvent::Subtract { id: "sequential_a".into(), value: 10 }, &mut ctx)
    .await
    .unwrap();
sequential_debits
    .handle(BeastEvent::Subtract { id: "sequential_b".into(), value: 5 }, &mut ctx)
    .await
    .unwrap();

// Batched: 100 - (10 + 5) = 85.
let batched_delta = 10_i64.saturating_add(5);
let mut batched_debit = build_subtract_machine(100);
batched_debit
    .handle(BeastEvent::Subtract { id: "batched".into(), value: batched_delta }, &mut ctx)
    .await
    .unwrap();

assert_eq!(balance_of(sequential_debits.state()), 85);
assert_eq!(balance_of(batched_debit.state()), 85);

For the failing case, the handler averages the incoming value into the running balance with (balance + value) / 2. No associative combine exists for this event payload.

The natural attempt is to average the two payloads with the same operator, but naive averaging is not itself associative:

• Two events of 10 and 5 applied to a starting balance of 100 give naive_average(naive_average(100, 10), 5) = 30 sequentially.
• Pre-combining the payloads gives naive_average(100, naive_average(10, 5)) = naive_average(100, 7) = 53.

The states diverge because naive averaging is not associative, as we can see below.

// Sequential: naive_average(naive_average(100, 10), 5) = 30.
let mut left_associated_average = build_naive_average_machine(100);
left_associated_average
    .handle(BeastEvent::NaiveAverage { id: "avg_a".into(), value: 10 }, &mut ctx)
    .await
    .unwrap();
left_associated_average
    .handle(BeastEvent::NaiveAverage { id: "avg_b".into(), value: 5 }, &mut ctx)
    .await
    .unwrap();

// Regrouped: naive_average(100, naive_average(10, 5)) = 53.
let grouped_average = naive_average(10, 5);
let mut right_grouped_average = build_naive_average_machine(100);
right_grouped_average
    .handle(BeastEvent::NaiveAverage { id: "avg_grouped".into(), value: grouped_average }, &mut ctx)
    .await
    .unwrap();

assert_eq!(balance_of(left_associated_average.state()), 30);
assert_eq!(balance_of(right_grouped_average.state()), 53);

Naive averaging looks like benign smoothing, but it has no associative combine, so any batcher that coalesces events will produce a different answer than sequential application would have. The FSM cannot detect either case from the inside so the constraint has to be enforced where the batching happens.

The fix is the same as for commutativity. Push the constraint upstream and make it the caller’s responsibility. Either the producer guarantees no regrouping for handlers that lack an associative combine, or the runtime knows which event types are safe to coalesce and only coalesces those. There is no transparent, application-agnostic way to make a non-associative combine behave under regrouping.

Trial 4: The Mark of the Beast

The fourth circle of distributed systems hell descends, finally, into pure theatre. A mix of credits and debits drives the balance to exactly 666, the number of the beast itself, and a MarkOfBeast event arrives to pass judgement on the machine. The handler reads three conditions and decides whether the FSM has crossed into territory from which there is no return.

let duplicates = ctx.duplicate_count.load(Ordering::Relaxed);
if balance == 666 || duplicates == 666 || operations.len() == 666 {
    return Ok(Transition {
        next_state: BeastState::Corrupted("The number of the beast!".to_string()),
        actions: vec![BeastAction::ApocalypseNow],
    });
}

A balance of 666, a duplicate count of 666, or an operations log of length 666. Any one of them flips the FSM into Corrupted and emits ApocalypseNow.

The trial is more theatre than algebra, but it does test something real. Sequential saturating arithmetic over hundreds of operations produces a deterministic balance, and the FSM’s terminal-state transition fires cleanly once the application layer detects an impossible condition. Building this kind of trip-wire into a state machine is how you stop a corrupted aggregate from continuing to accept writes after it crosses a line.

The line in production is rarely 666. It is more often a negative balance, a duplicate count above some threshold, or an operations log that grew faster than a sane workload should produce. The shape is the same.

What you are really looking for is an invariant that must never be violated. The way to surface it is to run the other three trials at high volume, structured so that the trip-wire fires the moment any property is silently violated. The trip-wire is just the messenger. The invariants behind it are the real subject.

You might already encode some of these as types, like a balance that cannot go negative or a counter with a known upper bound. The compiler enforces those invariants before any test runs. When the type system cannot carry the weight, a sentinel trip-wire still earns its place. Theatrical tests reward creative thinking about what should never happen and how to catch it the instant it does.

Closing

These three properties are not universal requirements. For instance, some domains are intentionally order-dependent. But when a system claims to support replay, at-least-once delivery, or parallel event processing, public APIs must satisfy whichever subset of these properties the delivery guarantees demand.

Each property fails differently and needs its own test harness:

• Idempotence fails under duplicates. The test floods the handler with retries and checks that the dedup worked.
• Commutativity fails under reordering. The test runs two machines on the same events in opposite orders and asserts they diverge.
• Associativity fails under regrouping. The test runs two machines on the same total work sliced different ways and asserts they diverge.

Deeply understanding idempotence, commutativity, and associativity helps you design more robust and dependable APIs. Algebraic properties will shape both the promises you make to users and the APIs you build, whether you intentionally design for them or not. It’s better to design for them rather than learn about them under the duress of real-world distributed systems failures.

Determinism is enough against perfect inputs and under perfect runtime conditions, but the unholy trinity of algebraic tests is what your systems need against everything else.