FA-73285 / Probabilistic sketches / Member archive

Cuckoo filter with partial-key relocation: failed insert keeps partial relocations · case 05

A failed insert silently evicts some other item's fingerprint, creating a false negative.

Member previewVariant 5 · 3 implementations · 10 checks per implementation

Case contract

Input {m (power of two), max_kicks, ops} with pre-hashed 32-bit items. Fingerprint f is bits 24-31, with 0 remapped to 1 (0 marks an empty slot in packed tables). i1 = h mod m and the alternate bucket is alt(i, f) = (i XOR (f*0x5bd1e995 mod 2^32)) mod m, so it is computable from the fingerprint alone. Buckets hold 2 fingerprints. Insert tries i1, then i2, then performs up to max_kicks evictions starting at i1, swapping slot (kick mod 2); on failure the table is restored and "full" is returned. Delete removes one copy, from i1 first. Return [results, buckets].

Why this case matters

Cuckoo filters give deletable approximate membership for caches and dedup stores; relocation only works if the alternate bucket is derivable from the stored fingerprint.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
fill 1 m=8 kicks=4	`[["ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "full", "ok", "ok", "full", "full", false, true, true, true, false, true, true, false, false], [[135], [], [132, 62], [35], [160, 240], [229, 206], [40, 231], [1, 237]]]`	`[["ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "full", "ok", "ok", "full", "full", true, true, true, true, true, true, true, false, false], [[135], [], [132, 224], [13], [221, 35], [229, 206], [40, 231], [1, 237]]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.