03.1 · Option C Reference

Parent: Document 03 (D2 Experiment Plan), Step 0.1 — “write down Option C verbatim.” Status: ✅ Banked. This document is the frozen definition of the reference contestant for the D2 experiment. The simulation implementation of Option C must match this document exactly; any later change requires a logged deviation in Document 04. How to read this later: §1–§3 give the context, §4 is the normative algorithm, §5 explains every line, §6 records the two adaptations (read these before trusting any result), §7 holds worked traces, Appendix A is the bit-shift primer.

---

1. What Option C is, and where it comes from

Option C is the eviction rule from HeavyKeeper, a published, peer-reviewed data structure:

Tong Yang, Junzhi Gong, et al., “HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows,” USENIX ATC 2018.

Context for why “a paper” matters (recorded here because it’s part of the project’s method, not trivia): in data structures, named techniques are defined by peer-reviewed publications. The paper contains mathematical proofs of the eviction rule’s guarantees — that heavy hitters are protected within stated error bounds. By implementing the rule faithfully, we inherit that vetted trust instead of rebuilding it. HeavyKeeper is additionally production-proven: it is the engine behind Redis’s TopK feature.

Role in our experiment: Option C is the measuring stick. Our own Option A (hash-entropy chipping, Doc 03.2) must be statistically indistinguishable from Option C’s results. A measuring stick bent toward our convenience measures nothing — hence “verbatim, with named adaptations only.”

2. The rule in one sentence

When a challenger is allowed to chip the victim, the chip succeeds with probability b^(−count), where b = 1.08 and count is the victim’s strength.

Plain terms: every tally mark the victim owns is an 8% compound-interest payment into its own protection. Not 8% added — 8% multiplied, mark after mark. Weak occupants chip off easily; strong ones become astronomically safe.

3. The curve, and why this shape

Victim strength	b^(−count), b=1.08	Feel
1	~0.926	basically defenseless
3	~0.794	chips off in a couple tries
10	~0.463	coin flip
30	~0.099	1 in 10
100	~4.5 × 10⁻⁴	1 in ~2,200
300	~10⁻¹⁰	lottery ticket
1,000	~10⁻³⁴	not in this universe
5,000	~10⁻¹⁶⁷	fewer than atoms anywhere

Why geometric and not something simpler like 1/count: under 1/count, N challenger attempts per epoch chip a count-N victim about once per epoch — any occupant erodes at a rate proportional to attack volume; elephants are grindable by sheer traffic. Under the geometric curve, protection grows multiplicatively with strength while attacks arrive only additively — past a few hundred tallies, no realistic attack volume dents the occupant. That asymmetry is the security property Option A must reproduce.

The parameter b: 1.08 is the paper’s tuned default, balancing recycle-speed of weak slots vs safety of strong slots. It is a named config parameter (b) in our harness, never a magic number.

4. Normative algorithm (single-threaded simulation semantics)

Scope note: this is the D2 simulation form — single-threaded, per the experiment plan’s scope guardrail. CAS/concurrency semantics are deliberately out of scope here.

// OptionC_Evict runs one eviction attempt after a lockout:
// challenger's bucket is full, no tag matched, no slot empty.
func OptionC_Evict(bucket []Slot, challengerTag uint16, now uint32, rng *rand.Rand) Outcome {

    // 1. Nominate: weakest slot by EFFECTIVE count. Deterministic — never a lottery.
    vi := indexOfMinEffective(bucket, now)
    v := &bucket[vi]

    // 2. Fold decay into the comparison value (Adaptation 1: effective, not raw).
    age := min(now-v.TS, 63)              // portability clamp: ancient ⇒ zero
    eff := v.Count >> age

    // 3. THE roll: succeed with probability b^(−eff).
    if rng.Float64() < math.Pow(b, -float64(eff)) {
        eff--
        if eff == 0 {
            // 4a. Takeover: challenger claims the slot, count 1, fresh stamp.
            *v = Slot{Tag: challengerTag, TS: now, Count: 1}
            return TAKEOVER
        }
        // 4b. Chip: occupant keeps slot/identity; fold-and-decrement
        //     (Adaptation 2: new count MUST carry a fresh timestamp).
        *v = Slot{Tag: v.Tag, TS: now, Count: eff}
        return CHIP
    }

    // 5. Bounce: draw failed. NOTHING anywhere changed; no memory of the attempt.
    return BOUNCE
}

The challenger itself is never tracked on CHIP or BOUNCE — it is reported upward as (estimate=1, first=true) per spec §2 Option A (untracked ⇒ rare ⇒ keep, fail-open).

5. Line-by-line commentary

Nomination is deterministic. The victim is always the minimum-effective slot. Elephants are protected at this stage by arithmetic, not luck: someone weaker is always in front of them. (The lottery only decides whether one chip lands — never who is challenged.)

rng is a seeded generator passed in — never a global. Mental model: a deck of cards shuffled in a known order. Same seed ⇒ same sequence ⇒ any run is exactly replayable from its recorded (workload, params, seed) tuple. The 20 differently-seeded runs of Option C produce its natural variance band — the goalposts Option A must land inside.

How draw < p implements “probability p.” rng.Float64() draws uniformly from [0,1). A uniform draw lands below 0.857 exactly 85.7% of the time — comparing a uniform draw to p is the standard mechanism for turning “succeeds with probability p” into code.

Three exits, one mutation site. TAKEOVER and CHIP each write exactly one slot; BOUNCE writes nothing at all — the structure holds no memory that the attempt happened. Chipping is therefore anonymous and collective: different challengers’ chips pool against the same victim; a slot survives only if its occupant’s own traffic outruns the total challenger pressure on the row.

6. Named adaptations (the “air-fryer” changes)

The paper’s structure has no concept of time — no timestamps, no decay; counts only grow. Ours is built around time. Grafting their rule onto our word forces exactly two changes, recorded here so that any future quality difference can be attributed correctly (recipe vs. our changes).

Adaptation 1 — the exponent uses the effective (decayed) count, not the raw stored count

The stakes, by example: a slot stores raw 96 but has been silent 5 epochs ⇒ effective 3.

Exponent choice	Chip probability	Consequence
raw 96	1.08⁻⁹⁶ ≈ 1/1,600	a fading ghost defends like a living resident — hogs the slot for epochs; resurrects the very lockout bug D2 exists to kill
effective 3	≈ 0.79	the departed occupant is swept away in a couple of attempts

Rule: protection belongs to who you are now, not who you were. Applied identically to Options A and C, so it cannot confound the comparison.

Adaptation 2 — a successful chip must also restamp the clock (fold-and-decrement)

Our count is meaningless alone; it is always “N tallies as of epoch H” — the pair travels together. The trap if a chip wrote a new count but kept the stale stamp: victim (raw 96, age 5) ⇒ eff 3 ⇒ chip to 2; store (count 2, old TS). The next reader folds again: 2 >> 5 = 0. The same decay was applied twice, annihilating an occupant we meant to weaken by one tally. Therefore every fresh count is written with TS = now — “2 tallies, as of now.” The paper never mentions this because the paper has no clock to keep honest.

7. Worked traces (keep these; they are the fastest way back into the algorithm)

Bucket state used below (eff = raw >> age):

slot:     0      1      2      3      4      5      6      7
raw ct: 4810    977    310     44     12      9     96      2
age:      0      0      0      0      0      0      5      0
eff:    4810    977    310     44     12      9      3      2

Trace 1 — challenger X arrives, bucket full, no tag match. Nominate: slot 7 (eff 2 is the minimum — note slot 6 nearly nominated at eff 3 despite raw 96; that is Adaptation 1 working). Fold: eff = 2 >> 0 = 2. Roll: p = 1.08⁻² ≈ 0.857. Suppose draw = 0.31 < 0.857 ⇒ CHIP: slot 7 becomes (same tag, TS=now, count 1). X walks away untracked, reported rare/keep. (Had the draw been 0.91 ⇒ BOUNCE, structure bit-for-bit untouched.)

Trace 2 — next challenger, seconds later, same epoch (verified by hand during Step 0.1 review): Nominate: slot 7 again (eff 1, still the minimum). Fold: 1 >> 0 = 1. Roll: p = 1.08⁻¹ ≈ 0.926.

• draw < 0.926 (≈93%): eff → 0 ⇒ TAKEOVER — slot 7 becomes (challenger tag, TS=now, count 1); the newcomer starts its own maximally-fragile audition as the new minimum.
• draw ≥ 0.926 (≈7%): BOUNCE — even a count-1 occupant’s survival is only unlikely to end, never guaranteed.

The audition principle (why fragile newborns are correct): a fluke that took a slot sits at count 1 — the next nominee — and is chipped out within a few challenges. A genuine new elephant refills tallies far faster than ~93%-odds chips remove them and is untouchable within an epoch. The structure never judges which keys deserve tracking; the traffic performs the audition.

8. Downstream use of this document

• The harness’s internal/sketch Option-C policy implements §4 exactly; golden tests reference the traces in §7.
• Option C × 20 seeds × workload matrix ⇒ variance bands (Doc 03, Step 4.1 gate).
• Doc 03.2 (Step 0.2) designs mask schedules whose implied probabilities must hug §3’s curve; §3’s table is the target.

---

Appendix A — Right-shift primer (>>)

Recorded because >> is the beating heart of decay; refresh here anytime.

What it is: x >> n slides the binary bits of x right by n positions; bits falling off the right edge are destroyed (not wrapped), zeros enter from the left. Decimal is only how we display the value before and after — the machine holds bits.

13 = 1101₂
13 >> 1 = 110₂ = 6     (the trailing 1 fell off — that was the ".5")
13 >> 2 =  11₂ = 3
13 >> 3 =   1₂ = 1
13 >> 4 =        0

Two equivalent mental models: (1) binary sliding — explains why; (2) repeated halving, rounding down each step — how you compute at a whiteboard: 44 >> 3: 44 → 22 → 11 → 5.

Facts we lean on:

• x >> 0 = x (identity — age-0 slots read at face value).
• Zero is a sticky floor: 2 >> 5 = 0 (slide 1 → 1, slide 2 → 0, slides 3–5 → still 0). No error, no negative — discarding from nothing yields nothing; counts are unsigned so there is no sign bit to corrupt.
• Small counts die fast (1 >> 1 = 0 — a count-1 mouse vanishes after one silent epoch), large counts fade slowly. Mice bury themselves; elephants linger. This is evaporation, derived — not a policy, arithmetic.
• 24-bit counts ⇒ 24 halvings annihilate any value ⇒ “total amnesia after 24 epochs” in the tick table.
• Why halving (base 2) and not 1.5 or e: the CPU performs a shift in one cycle; division takes tens. We chose the decay rate the hardware gives us for free — the math serves the machine.
• The min(age, 63) clamp is load-bearing: Go defines over-wide shifts as 0, but C leaves shift ≥ width undefined — real x86 masks the shift amount, so shifting by 64 can return the value unchanged, resurrecting ancient counts. The clamp makes “ancient = zero” true in every language.