Associativity Property Test¶
Property test — instantiates Regroupable Aggregation
Checks the archetype's defining law directly by generating random contribution triples and asserting that (a⊗b)⊗c matches a⊗(b⊗c) under the declared equivalence — while proving that swapping operands is not silently assumed.
An aggregation is only safe to regroup if its combine operation is genuinely associative, and the cheapest way to find out is to interrogate the algebra rather than the deployment. Associativity Property Test takes the combine function in isolation, draws many random triples of summaries a, b, c, and asserts a single equation — combine(combine(a, b), c) equals combine(a, combine(b, c)) under the declared equivalence relation. Its defining move is that it tests the law itself, on synthetic operands, before any real partition tree exists. It is a unit-level guard on the contract, not a rehearsal of the production pipeline — and its second, easily-forgotten job is to check that associativity has not quietly been mistaken for commutativity by also probing whether swapping operands changes the answer.
Example¶
A team maintains an open-source money-math library whose Money type sums amounts across currencies with rounding rules. Someone proposes running these sums in parallel. Before shipping that, an engineer writes a property test in a QuickCheck-style generator: draw three random Money values with mixed magnitudes, currencies, and sign, then assert that folding them left-to-right equals folding right-to-left. The first hundred cases pass. Then the generator produces a triple where two large opposite-sign amounts cancel and a rounding step fires at a half-cent — and left-grouping rounds up while right-grouping rounds down. The equation fails.
That single counterexample, minimized by the generator to the smallest reproducing triple, tells the team their rounding-in-combine breaks associativity. The test also runs a companion assertion that a ⊗ b need not equal b ⊗ a, confirming the operation is not commutative and warning against any scheduler that reorders. The outcome is not a passing badge but a registered exception: rounding must move out of the combine step, and until it does, this operation is logged as ineligible for parallel regrouping.
How it works¶
- Generate, don't enumerate. A property generator produces triples with adversarial variety — unequal magnitudes, cancellation, empty and singleton summaries, boundary values — rather than a hand-picked handful.
- Assert the equivalence, not equality. The pass/fail predicate is the declared relation: byte identity, exact numeric equality, or a bounded difference. A bounded relation is checked against the budget, not eyeballed.
- Separate the swap check. A distinct assertion probes commutativity so a permutation-sensitive operation cannot masquerade as merely regroupable.
- Shrink and register. On failure the generator minimizes the counterexample, and the case is filed as a sequencing exception rather than silently retried until it passes.
Tuning parameters¶
- Generator distribution — how adversarial the drawn operands are. Skewing toward cancellation and extreme magnitudes finds precision bugs faster but can flood the log with known-hard cases.
- Trial count — more triples raise confidence but cost CI time; high-risk combines warrant thousands, a display formatter a few dozen.
- Equivalence tolerance — the band a bounded relation allows. Tighten it and floating-point combines fail; loosen it and real drift slips through.
- Arity of the law — three operands prove associativity; extending to random-depth folds catches deeper accumulation errors at more cost.
- Swap-check toggle — whether commutativity is asserted true, asserted false, or left unchecked, per what the operation actually claims.
When it helps, and when it misleads¶
Its strength is that it catches a broken law before the law is trusted at scale, and it does so on cheap synthetic inputs where a defect is reproducible and minimizable — the whole point of property-based testing[n1]. It is the fastest way to distinguish a genuinely associative operation from one that only looked associative on symmetric example data.
Its failure mode is complacency from green tests: a passing property test proves the law holds on the generator's distribution, not on production's. If the generator never draws the cancelling triple, the rounding bug ships anyway — symmetry in the test data hides the defect exactly as it hides it in production. It also says nothing about lineage, compatibility, or whether the real reduction tree preserves what the law assumes. The guarding discipline is to treat a pass as necessary-not-sufficient: bias the generator toward known-hard structure, and back it with a full-tree replay before deployment rather than trusting triples alone.
How it implements the components¶
grouping_equivalence_relation— the assertion predicate is the declared "same result" standard, made executable as a comparison.order_preservation_rule— the separate swap assertion enforces that associativity is not read as commutativity, fixing operand sequence as the default.sequencing_exception_registry— failing or order-sensitive triples are filed as registered exceptions rather than being tuned away.
It does not exercise a real partition tree against a trusted baseline: regrouping_test_oracle, reference_computation_path, and divergence_monitor belong to Randomized Partition Replay, which replays whole trees rather than checking the algebraic triple.
Related¶
- Instantiates: Regroupable Aggregation — this test validates the archetype's defining associativity law at the contract level.
- Sibling mechanisms: Randomized Partition Replay · Deterministic Pairwise Accumulation · Tree Reduction · Map–Combine–Reduce Pipeline · Mergeable Summary Object · Hierarchical Subtotal Rollup · Rollup Reconciliation Report · Versioned Merge Protocol · Weighted Moment Accumulator
Editorial Notes¶
Form Classification¶
Form family: Experiment, Test & Rehearsal
Rationale: Checks the archetype's defining law directly by generating random contribution triples and asserting that (a⊗b)⊗c matches a⊗(b⊗c) under the declared equivalence — while proving that swapping operands is not silently assumed, making its operative form a deliberate probe, variation, simulation, or practiced execution used to generate evidence or readiness.
Independent corroboration: The frozen evidence defines Associativity Property Test as 'Checks the archetype's defining law directly by generating random contribution triples and asserting that (a⊗b)⊗c matches a⊗(b⊗c) under the declared equivalence — while proving that swapping operands is not silently assumed', so its operative form is Experiment, Test & Rehearsal.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Mathematics
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Abstract algebra defines associativity and its distinction from commutativity as properties of binary operations.
Related originating lineages:
- Computer Science & Software Engineering — QuickCheck-style property-based testing generates and shrinks counterexamples in executable combines.
Review resolution: Mathematics is the agreed primary source of associativity and equivalence. Property-based software testing turns that algebraic law into generated executable checks, so cross-disciplinary synthesis is more accurate than a sealed mathematical lineage. Its reuse is broad but the test artifact is not universal to every domain.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Property-based testing checks that a stated property holds over many machine-generated inputs and, on failure, shrinks the case to a minimal counterexample. Popularized by QuickCheck (Haskell) and its descendants; associativity is the textbook property such tools are used to falsify. ↩