Real-Time Geofencing Location triggers · low-latency spatial
10 min read 5 sections

Debouncing Boundary Flapping with State Machines

The confirmation window introduced in boundary hysteresis and debounce tuning is usually implemented as a counter, and a counter is where the subtle bugs live. A counter has no answer for a device that produces two of the three votes it needs and then goes silent for an hour; no answer for a device that flips back and forth so the vote never reaches either threshold; and no answer for what the pipeline should report in the meantime. Making the debouncer an explicit state machine, rather than a predicate over a counter, turns each of those from an accident into a labelled state with a defined exit. This page sits under the hysteresis topic within Core Architecture & Latency Constraints.

Concept and specification

The machine has five states and every transition out of them is triggered either by an observation or by the passage of event time. OUTSIDE and INSIDE are the committed states — the only two a downstream consumer ever sees. ENTERING and EXITING are pending states, entered when a fix disagrees with the committed state and left when the vote resolves in either direction. STALE is entered from any state when a device has been silent longer than the staleness horizon, and it exists so that a device returning after an hour is not treated as continuing a vote it started before it went quiet.

State Meaning Exits on Emits
OUTSIDE Committed outside the fence Disagreeing fix → ENTERING; silence → STALE nothing
ENTERING Vote in progress toward inside N agreeing → INSIDE; one agreeing with OUTSIDE → OUTSIDE; timeout → OUTSIDE ENTER on commit
INSIDE Committed inside the fence Disagreeing fix → EXITING; silence → STALE nothing
EXITING Vote in progress toward outside N agreeing → OUTSIDE; one agreeing with INSIDE → INSIDE; timeout → INSIDE EXIT on commit
STALE Device silent past the horizon Any fix → OUTSIDE or INSIDE by direct test optional STALE marker
State at a glance: Meaning, Exits on A row per state, a column per option, so a single axis can be compared across options in one sweep. State at a glance: Meaning, Exits on the same trade-offs, read across instead of down Meaning Exits on Emits OUTSIDE Committed outside the fence Disagreeing fix → ENTERING; silence → STALE nothing ENTERING Vote in progress toward inside N agreeing → INSIDE; one agreeing with OUTSIDE → OUTSIDE; timeout → OUTSIDE ENTER on commit INSIDE Committed inside the fence Disagreeing fix → EXITING; silence → STALE nothing EXITING Vote in progress toward outside N agreeing → OUTSIDE; one agreeing with INSIDE → INSIDE; timeout → INSIDE EXIT on commit STALE Device silent past the horizon Any fix → OUTSIDE or INSIDE by direct test optional STALE marker
The state table read across rather than down — each row is one axis of the decision, colour-keyed so a single trade-off can be followed across Meaning, Exits on, Emits.

Two rules in that table carry all the correctness. First, a single fix agreeing with the committed state abandons the pending vote entirely — it does not decrement a counter. This is what makes an alternating device stable: each agreeing fix resets the vote, so a one-for-one flip pattern can never accumulate a majority. Second, a pending vote that times out resolves toward the committed state, not toward the candidate. The device stopped reporting while it was disagreeing; the last thing actually confirmed is the committed state, and committing the unconfirmed candidate on a timeout is how a silent device manufactures a transition it never made.

The staleness horizon and the vote timeout are different parameters with different jobs, and conflating them is a common bug:

The vote timeout is a few reporting intervals — long enough that a slightly late fix still counts, short enough that a pending state does not linger. The staleness horizon is minutes, and its purpose is to prevent a device that reappears after a long gap from having its old vote or even its old committed state trusted, since the dead-reckoning horizon has long since expired.

Step-by-step implementation

1. Encode the state and the vote in one integer. Per-pair state is the dominant memory term at fleet scale, and packing removes both the object header and the allocation churn.

python 
from __future__ import annotations

# bits 0-2: state, bits 3-7: vote bitmap (most recent vote in bit 3),
# bits 8-12: number of votes recorded so far.
OUTSIDE, ENTERING, INSIDE, EXITING, STALE = range(5)
_STATE, _VOTES, _COUNT = 0b111, 0b1111_1000, 0b1_1111_0000_0000

def state_of(packed: int) -> int:
    return packed & _STATE

def with_state(packed: int, state: int) -> int:
    return (packed & ~_STATE) | state

def push_vote(packed: int, agree: bool) -> int:
    votes = ((packed & _VOTES) >> 3)
    votes = ((votes << 1) | (1 if agree else 0)) & 0b1_1111
    count = min(5, ((packed & _COUNT) >> 8) + 1)
    return (packed & _STATE) | (votes << 3) | (count << 8)

def clear_votes(packed: int) -> int:
    return packed & _STATE

def agree_count(packed: int) -> int:
    return bin((packed & _VOTES) >> 3).count("1")

2. Write the transition function as a pure function of (state, observation, clock). Purity is what makes the machine testable exhaustively — five states times three observation kinds is fifteen cases, all of which can be asserted.

python 
from dataclasses import dataclass

@dataclass(slots=True)
class Pair:
    packed: int = OUTSIDE
    last_ns: int = 0
    pending_since_ns: int = 0

def step(p: Pair, inside_now: bool, t_ns: int,
         need: int = 3, vote_timeout_ns: int = 4_500_000_000,
         stale_ns: int = 300_000_000_000) -> str | None:
    st = state_of(p.packed)
    if p.last_ns and t_ns - p.last_ns > stale_ns:
        st, p.packed = STALE, with_state(clear_votes(p.packed), STALE)
    p.last_ns = t_ns

    if st == STALE:                                  # re-acquire directly
        p.packed = with_state(clear_votes(p.packed), INSIDE if inside_now else OUTSIDE)
        return None                                  # never emit on re-acquisition
    if st in (OUTSIDE, INSIDE):
        committed_inside = st == INSIDE
        if inside_now == committed_inside:
            return None
        p.packed = push_vote(with_state(clear_votes(p.packed),
                                        ENTERING if inside_now else EXITING), True)
        p.pending_since_ns = t_ns
        return None
    # pending states
    toward_inside = st == ENTERING
    if inside_now != toward_inside:                  # a fix agreeing with committed
        p.packed = with_state(clear_votes(p.packed), INSIDE if not toward_inside else OUTSIDE)
        return None
    p.packed = push_vote(p.packed, True)
    if agree_count(p.packed) >= need:
        p.packed = with_state(clear_votes(p.packed), INSIDE if toward_inside else OUTSIDE)
        return "ENTER" if toward_inside else "EXIT"
    if t_ns - p.pending_since_ns > vote_timeout_ns:  # resolve TOWARD committed
        p.packed = with_state(clear_votes(p.packed), OUTSIDE if toward_inside else INSIDE)
    return None

3. Resolve pending votes without a timer per pair. The timeout above is evaluated lazily, on the next observation for that pair — which is correct for a device that keeps reporting and useless for one that does not. A sweep is still required for silent devices, and it must not be one call_later per pair; the hashed timer wheel that makes it affordable is covered in dwell-time triggers without timer storms.

4. Never emit on re-acquisition from STALE. A device returning after five minutes of silence has an unknown history; committing a transition because its first new fix disagrees with a stale committed state fabricates a crossing whose event time is unknowable. Re-acquire the state silently and let the next genuine crossing emit.

5. Test the machine exhaustively, not statistically. Enumerate every (state, observation) pair and assert both the resulting state and whether an emission occurred. A property test over random fix sequences is a useful addition, with the invariant that emissions must strictly alternate ENTER/EXIT per pair — an invariant a counter-based debouncer violates in exactly the silent-device case.

Benchmark and verification

Measured on a replay of 61 million fixes across 4,000 devices and 6,000 fences, 1.9 million live pairs:

Implementation Unresolved pending states after 1 h Alternation violations Bytes per pair Throughput
Counter, no timeout 41,200 3,910 264 2.9M/s
Counter + per-pair timer 0 3,910 312 0.4M/s
State machine, lazy timeout only 38,700 0 32 3.4M/s
State machine + timer wheel 0 0 32 3.1M/s
Unresolved pending states after 1 h, Bytes per pair, Throughput — 4 options Each panel scales on its own, so Unresolved pending states after 1 h, Bytes per pair, Throughput are compared across 4 options without sharing an axis they do not share a unit with. Unresolved pending states after 1 h, Bytes per pair, Throughput — 4 options Implementation — the table above, drawn to scale Counter, no timeout Counter + per-pair timer State machine, lazy timeout only State machine + timer wheel Unresolved pending states after… 41,200 0 38,700 0 Bytes per pair 264 312 32 32 Throughput 2.9M/s 0.4M/s 3.4M/s 3.1M/s
Unresolved pending states after 1 h, Bytes per pair and 1 more for Counter, no timeout, Counter + per-pair timer, State machine, lazy timeout only and 1 more, drawn from the measurements in the table above. Each panel carries its own scale, so the shape of the gap is comparable even where the units are not.

The alternation column is the correctness result: the counter emits 3,910 ENTER-after-ENTER or EXIT-after-EXIT pairs over the replay, every one of which is a downstream consumer being told a device entered a fence it was already in. The state machine emits none by construction, because a commit always clears the vote and sets the committed state atomically. The throughput column is the reason to bother with bit packing — a per-pair timer costs an order of magnitude, while a timer wheel costs 9%.

To verify a deployment rather than a replay, export pending_pairs and pending_age_seconds as gauges. In a healthy system the pending count is a small fraction of active pairs and the age histogram has nothing above the vote timeout. A growing pending count with a rising age is the signature of the silent-device leak, and it is visible long before it shows up as missing triggers.

Failure modes and edge cases

Failure mode Signature Mitigation
Vote timeout resolves toward the candidate Phantom transitions from devices that went silent Always resolve toward the committed state
Emitting on STALE re-acquisition Bursts of transitions when connectivity returns Re-acquire silently; let the next crossing emit
Shared vote across fences A device near two fences votes for the wrong one Key state by (device, fence), never by device alone
Pending state never evicted Memory grows with fleet-days rather than fleet size Evict OUTSIDE pairs past the staleness horizon; never evict INSIDE
Out-of-order fixes Votes recorded in the wrong sequence Place the debouncer downstream of the reorder buffer
Vote timeout shorter than the reporting interval Every vote times out; no transition ever commits Set the timeout to about 1.5× M reporting intervals
Failure mode at a glance: Signature, Mitigation A row per failure mode, a column per option, so a single axis can be compared across options in one sweep. Failure mode at a glance: Signature, Mitigation the same trade-offs, read across instead of down Signature Mitigation Vote timeout resolves toward the candidate Phantom transitions from devices that went silent Always resolve toward the committed state Emitting on STALE re-acquisition Bursts of transitions when connectivity returns Re-acquire silently; let the next crossing emit Shared vote across fences A device near two fences votes for the wrong one Key state by (device, fence), never by device alone Pending state never evicted Memory grows with fleet-days rather than fleet size Evict OUTSIDE pairs past the staleness horizon; never evict INSIDE Out-of-order fixes Votes recorded in the wrong sequence Place the debouncer downstream of the reorder buffer Vote timeout shorter than the reporting interval Every vote times out; no transition ever commits Set the timeout to about 1.5× M reporting intervals
The failure mode table read across rather than down — each row is one axis of the decision, colour-keyed so a single trade-off can be followed across Signature, Mitigation.

The third row is worth expanding because it produces the most confusing symptom. A device approaching two adjacent fences generates disagreeing observations for both, and a debouncer keyed only by device will interleave them into one vote sequence, producing transitions that belong to neither fence. The symptom is a trigger stream that is individually plausible and collectively impossible, and it disappears the moment the key includes the fence — the same keying discipline the idempotency key uses downstream.

The eviction rule in the fourth row has an asymmetry that is easy to get wrong under memory pressure. An OUTSIDE pair carries no information — it is the default state — so dropping it is free. An INSIDE pair is the only record that the device is in the fence, so dropping it converts the eventual genuine EXIT into silence and leaves the downstream consumer believing the device is still inside forever. Under memory pressure, shed OUTSIDE pairs aggressively and spill INSIDE pairs to a durable store rather than dropping them.