E-Commerce Order State Machine in TLA+

Table of Contents

1. Overview

This specification models the state transitions in a typical e-commerce system (inspired by the OpenAPI PetStore example). We explore how Cart, Order, Shipment, and Status can become misaligned in a distributed architecture.

1.1. The Problem: State Synchronization

In microservices architectures, entities often span multiple services:

┌─────────────┐    ┌─────────────┐    ┌─────────────┐    ┌─────────────┐
│   Cart      │───►│   Order     │───►│  Shipment   │───►│   Status    │
│   Service   │    │   Service   │    │   Service   │    │   Service   │
└─────────────┘    └─────────────┘    └─────────────┘    └─────────────┘
      │                  │                  │                  │
      ▼                  ▼                  ▼                  ▼
   CartDB             OrderDB           ShipmentDB         StatusDB

Each service maintains its own state, leading to potential inconsistencies:

  • Cart shows items, but order failed to create
  • Order exists, but shipment never created
  • Shipment delivered, but status shows "processing"

2. State Definitions

2.1. Cart States

---- MODULE ECommerceStates ----
EXTENDS Integers, Sequences, FiniteSets

CONSTANTS Items

\* Cart states
CartStates == {"empty", "active", "abandoned", "converted"}

\* Order states
OrderStates == {"none", "pending", "confirmed", "paid", "cancelled", "refunded"}

\* Shipment states
ShipmentStates == {"none", "preparing", "shipped", "in_transit", "delivered", "returned"}

\* Status (customer-facing aggregated state)
StatusStates == {"browsing", "checkout", "processing", "shipped", "completed", "failed"}

2.2. Variables

VARIABLES
    cart,       \* Current cart state
    order,      \* Current order state
    shipment,   \* Current shipment state
    status,     \* Customer-facing status
    items       \* Items in cart/order

vars == <<cart, order, shipment, status, items>>

3. State Transitions

3.1. Cart Actions

\* Add item to cart
AddToCart(item) ==
    /\ cart \in {"empty", "active"}
    /\ items' = items \union {item}
    /\ cart' = "active"
    /\ status' = "browsing"
    /\ UNCHANGED <<order, shipment>>

\* Remove item from cart
RemoveFromCart(item) ==
    /\ cart = "active"
    /\ item \in items
    /\ items' = items \ {item}
    /\ cart' = IF items' = {} THEN "empty" ELSE "active"
    /\ UNCHANGED <<order, shipment, status>>

\* Abandon cart (timeout or explicit)
AbandonCart ==
    /\ cart = "active"
    /\ cart' = "abandoned"
    /\ status' = "browsing"
    /\ UNCHANGED <<order, shipment, items>>

3.2. Order Actions

\* Convert cart to order (checkout)
CreateOrder ==
    /\ cart = "active"
    /\ items # {}
    /\ order = "pending" \/ order = "none"
    /\ cart' = "converted"
    /\ order' = "pending"
    /\ status' = "checkout"
    /\ UNCHANGED <<shipment, items>>

\* Confirm order (inventory reserved)
ConfirmOrder ==
    /\ order = "pending"
    /\ order' = "confirmed"
    /\ UNCHANGED <<cart, shipment, status, items>>

\* Payment successful
PayOrder ==
    /\ order = "confirmed"
    /\ order' = "paid"
    /\ status' = "processing"
    /\ UNCHANGED <<cart, shipment, items>>

\* Cancel order
CancelOrder ==
    /\ order \in {"pending", "confirmed"}
    /\ order' = "cancelled"
    /\ status' = "failed"
    /\ UNCHANGED <<cart, shipment, items>>

3.3. Shipment Actions

\* Create shipment after payment
CreateShipment ==
    /\ order = "paid"
    /\ shipment = "none"
    /\ shipment' = "preparing"
    /\ UNCHANGED <<cart, order, status, items>>

\* Ship the order
ShipOrder ==
    /\ shipment = "preparing"
    /\ shipment' = "shipped"
    /\ status' = "shipped"
    /\ UNCHANGED <<cart, order, items>>

\* In transit
InTransit ==
    /\ shipment = "shipped"
    /\ shipment' = "in_transit"
    /\ UNCHANGED <<cart, order, status, items>>

\* Delivered
Deliver ==
    /\ shipment = "in_transit"
    /\ shipment' = "delivered"
    /\ status' = "completed"
    /\ UNCHANGED <<cart, order, items>>

\* Return initiated
ReturnOrder ==
    /\ shipment = "delivered"
    /\ shipment' = "returned"
    /\ order' = "refunded"
    /\ UNCHANGED <<cart, status, items>>

4. Invariants: Detecting State Mismatches

4.1. Consistency Invariants

\* Cart and Order consistency
CartOrderConsistency ==
    \* If order exists, cart must be converted or active
    (order # "none" /\ order # "pending") => cart \in {"converted", "active"}

\* Order and Shipment consistency
OrderShipmentConsistency ==
    \* Shipment only exists for paid orders
    (shipment # "none") => order \in {"paid", "refunded"}

\* Shipment and Status consistency
ShipmentStatusConsistency ==
    \* If delivered, status must be completed
    (shipment = "delivered") => status = "completed"

\* No orphaned shipments
NoOrphanedShipments ==
    \* Cannot have shipment without a paid order
    (shipment \in {"preparing", "shipped", "in_transit", "delivered"}) =>
        order \in {"paid", "refunded"}

\* Items consistency
ItemsConsistency ==
    \* If cart is empty, no items should exist
    (cart = "empty") => items = {}

4.2. Temporal Properties (Safety)

\* Safety: Order never goes backwards
OrderNeverGoesBackwards ==
    [](order = "paid" => [](order # "pending"))

\* Safety: Delivered items stay delivered (unless returned)
DeliveredStaysDelivered ==
    [](shipment = "delivered" =>
        [](shipment \in {"delivered", "returned"}))

\* Safety: Cancelled orders never ship
CancelledNeverShips ==
    [](order = "cancelled" => [](shipment = "none"))

4.3. Temporal Properties (Liveness)

\* Liveness: Paid orders eventually ship
\* (Not shipment = "shipped": that state lasts one step, and a check
\* that samples it can miss it entirely.)
PaidOrdersEventuallyShip ==
    (order = "paid") ~> (shipment \in {"shipped", "in_transit", "delivered", "returned"})

\* Liveness: Shipped orders eventually complete
ShippedEventuallyCompletes ==
    (shipment = "shipped") ~> (status = "completed")

5. Failure Scenarios

5.1. Network Partition Examples

\* Scenario: Order service confirms, but shipment service doesn't receive message
PartitionAfterOrderConfirm ==
    /\ order = "paid"
    /\ shipment = "none"  \* Stuck - shipment never created
    \* This violates: PaidOrdersEventuallyShip

\* Scenario: Shipment delivered, but status service unreachable
PartitionAfterDelivery ==
    /\ shipment = "delivered"
    /\ status = "processing"  \* Stale status
    \* This violates: ShipmentStatusConsistency

5.2. Race Conditions

\* Scenario: Customer cancels while shipment is being created
RaceCancelAndShip ==
    \* Two concurrent actions:
    \* 1. Customer clicks "Cancel Order"
    \* 2. Warehouse starts preparing shipment
    \*
    \* Possible outcomes:
    \* - Order cancelled, shipment cancelled (correct)
    \* - Order cancelled, shipment proceeds (BAD: shipped cancelled order)
    \* - Shipment created, cancel fails (acceptable: customer can return)

    \* The invariant that catches this:
    /\ order = "cancelled"
    /\ shipment # "none"
    \* This violates: CancelledNeverShips

6. Model Configuration

\* Initial state
Init ==
    /\ cart = "empty"
    /\ order = "none"
    /\ shipment = "none"
    /\ status = "browsing"
    /\ items = {}

\* Where a behaviour legitimately ends. Stuttering here is explicit, so
\* TLC's deadlock check stays on and still catches a state nothing handles.
Terminated ==
    \/ cart = "abandoned"
    \/ order = "cancelled"
    \/ shipment \in {"delivered", "returned"}

Done == Terminated /\ UNCHANGED vars

\* All possible transitions
Next ==
    \/ \E item \in Items: AddToCart(item)
    \/ \E item \in items: RemoveFromCart(item)
    \/ AbandonCart
    \/ CreateOrder
    \/ ConfirmOrder
    \/ PayOrder
    \/ CancelOrder
    \/ CreateShipment
    \/ ShipOrder
    \/ InTransit
    \/ Deliver
    \/ ReturnOrder
    \/ Done

\* Specification
Spec == Init /\ [][Next]_vars /\ WF_vars(Next)

\* Properties to check
THEOREM Spec => []CartOrderConsistency
THEOREM Spec => []OrderShipmentConsistency
THEOREM Spec => []ShipmentStatusConsistency
THEOREM Spec => []NoOrphanedShipments

====

7. Running the Model Checker

7.1. TLC Configuration

Create a ECommerceStates.cfg file:

CONSTANTS
    Items = {i1, i2, i3}

SPECIFICATION Spec

INVARIANTS
    CartOrderConsistency
    OrderShipmentConsistency
    ShipmentStatusConsistency
    NoOrphanedShipments
    ItemsConsistency

PROPERTIES
    OrderNeverGoesBackwards
    DeliveredStaysDelivered
    CancelledNeverShips
    PaidOrdersEventuallyShip
    ShippedEventuallyCompletes

SPECIFICATION Spec rather than INIT=/=NEXT: the liveness properties depend on the WF_vars(Next) conjunct, which INIT=/=NEXT silently drops.

7.2. Expected TLC Output

TLC 2.19, tlc -config ECommerceStates.cfg ECommerceStates.tla:

Model checking completed. No error has been found.
142 states generated, 78 distinct states found, 0 states left on queue.
The depth of the complete state graph search is 12.

Each fix is load-bearing. Re-checked 2026-10-22 by reverting one at a time:

Revert TLC reports
drop Done from Next Deadlock reached
INIT Init / NEXT Next instead of Spec temporal properties violated
PaidOrdersEventuallyShip as shipment = "shipped" temporal properties violated

An earlier version of this note printed 847 states generated and 234 distinct. That output was never produced by this spec: the history audit trail grew on every step, so the state space was infinite, and the cfg's INIT=/=NEXT hit a deadlock at the first abandoned cart. The trail is gone (nothing checked it), "none" is now in OrderStates, and the unused MaxQuantity constant is removed.

8. Lessons for System Design

8.1. Key Insights

  1. State machines are implicit - Most e-commerce systems have these states, but they're scattered across services without formal specification.
  2. Invariants catch bugs early - The consistency checks would have caught issues before production.
  3. Temporal properties matter - Liveness properties ensure the system makes progress.

8.2. Recommendations

Issue TLA+ Detection Production Symptom
Orphaned shipment NoOrphanedShipments Customer charged, nothing ships
Stale status ShipmentStatusConsistency Customer sees "processing" for delivered item
Cancel race CancelledNeverShips Cancelled order still ships
Stuck order PaidOrdersEventuallyShip Paid order never ships

8.3. Integration with OpenAPI/PetStore

The PetStore API defines similar states:

Order:
  status:
    enum: [placed, approved, delivered]

Pet:
  status:
    enum: [available, pending, sold]

This TLA+ spec extends those simple enums into a complete state machine with transition guards and consistency invariants.

9. Live Demo

Interactive visualization of this state machine:

10. References