How do a monotonic counter, a remembered-message-id set and a clock window differ in what the receiver must keep?
answer
- Three shapes, three different currencies
- One integer, or a set, or a clock
- What happens after a restart
- Ageing an identifier out reopens it
- Retention must cover the window
basics
~20 sA counter stores one number per sender but needs ordered delivery and must survive restarts. An identifier set tolerates disorder but needs storage and a retention bound. A clock window needs synchronised clocks and, alone, still permits replay inside it.
solid answer
~50 sAll three are receiver-held state, and they trade different costs. A **monotonic counter** keeps one integer per sender and refuses anything at or below it: cheapest to store, but it assumes a single ordered stream, breaks under parallel or out-of-order delivery, and is catastrophic if it resets on restart, because every past message becomes acceptable again. A **remembered-message-id set** records an identifier from each accepted message and refuses repeats: tolerant of disorder and multiple sending replicas, but it grows, so it needs a retention bound. A **clock window** checks a signed timestamp against a tolerance: it bounds how long a captured copy is useful, but it costs clock synchronisation, a wide tolerance is a replay window, and a narrow one rejects legitimately late traffic. The standard composition is window plus identifier set, with retention at least as long as the window — so a copy is either too old or already remembered.
go deeper
Know that the receiver has to remember something to refuse a duplicate, and be able to name at least one form that memory takes, such as a counter or a list of message identifiers already handled.
Explain each mechanism's mechanics and its currency: one integer but strict ordering, a growing set but tolerance of disorder, an expiry rule but a clock dependency. Say why a window alone is not a defence.
Pick the mechanism from the receiver's real constraints — parallel senders, restart behaviour, whether a reliable clock exists — and insist that state is written durably before the message is acted on, not after.
Own the coupling: window length and retention are one decision with one owner, and the storage they imply is a running cost. Set it once as an integration standard rather than letting each receiving service choose.
## Why there are exactly three shapes The receiver has to answer one question: *have I already acted on this?* Since nothing in the message can answer it, the receiver compares the arrival against remembered state. There are only three useful shapes for that state, and each buys refusal with a different currency. ### 1. A monotonic counter (sequence number) per sender **Mechanism.** Every message carries a counter inside the signed content. The receiver stores the highest value it has accepted from that sender and refuses anything less than or equal to it. **What it costs.** Almost nothing to store: one integer per sender, regardless of message volume. That makes it the mechanism of choice for constrained devices — a metering or building-control endpoint that receives *actuate* commands has room for a counter and not much else. **Where it breaks.** - *Ordering.* It presumes one logical stream. Two sender replicas, a load-balanced fan-out, or a retry that arrives after a later message all produce values below the high-water mark, and legitimate traffic is refused. - *Gaps.* If the receiver accepts a jump from 41 to 50, messages 42 to 49 can never be delivered afterwards. That is either an availability problem or, if you relax it, a hole. - *Durability.* The high-water mark must be written to non-volatile storage **before** the receiver acts on the message. A receiver that keeps the counter only in memory, and restarts, resets to zero — at which point every message ever sent to it is acceptable again. On a device that reboots often, or is reflashed, this is the dominant failure. - *Sender resets.* A sender re-provisioned with a fresh key material set and a counter back at 1 looks exactly like an attacker rewinding, so the policy for "counter went backwards" must be *refuse*, not *accept and resynchronise*. ### 2. A remembered-identifier set **Mechanism.** Each message carries a unique identifier inside the signed content. The receiver stores the identifiers it has accepted and refuses one it has already seen. **What it costs.** Storage proportional to message rate multiplied by retention, plus a lookup on the hot path that must be atomic with the decision to act — otherwise two copies arriving concurrently both check, both miss, and both execute. **Where it breaks.** The set cannot grow forever, so it has a retention bound — and *the moment an identifier ages out, the message it protected becomes replayable again*. A retention bound is therefore only safe when a second check refuses messages older than the retention, which in practice means a timestamp window. An identifier set with a one-hour retention and no age check is a one-hour delay, not a defence. It is the most tolerant mechanism: out-of-order delivery, parallel senders, and gaps are all fine, because it asks "seen this one?" rather than "is this the next one?". ### 3. A clock window **Mechanism.** The message carries a timestamp inside the signed content. The receiver refuses anything outside a tolerance around its own clock. **What it costs.** Clock discipline on both sides. If the sender's clock drifts, its legitimate traffic is refused; if the receiver's drifts, old copies are accepted. Many constrained receivers have no reliable clock at all, which removes this option entirely. **Where it breaks.** Alone, it is not a replay defence — it is an *expiry* mechanism. Inside the tolerance, a copy can be resent freely and every check passes. Widening the tolerance to stop false rejections from late batch jobs directly widens the interval in which a captured message can be re-executed. Narrowing it to seconds pushes the false-rejection cost onto every legitimate sender with queueing delay. ## The composition that actually works Window plus identifier set, with retention greater than or equal to the window: ``` age(message) > window -> refuse (too old) id in remembered set -> refuse (already seen) otherwise -> record id, then act ``` Each mechanism covers the other's hole: the window bounds the set's size, and the set closes the window's interior. Note the ordering of the last line — recording must be durable and atomic with acting, or a crash between the two either loses the record (replayable) or loses the action (a genuine message silently dropped). Where a clock is unavailable, the counter is the substitute for the window: it plays the same role of making everything older than the current position permanently unacceptable, at the price of demanding order and durable storage. ## What an interviewer is listening for The weak answer names one mechanism and stops. The strong answer names the currency each one spends — storage, ordering, clock, false rejections — and then says which of the receiver's real constraints picks the winner: a partner API with parallel senders and good clocks wants window plus identifier set; a metering endpoint with no clock and scarce storage wants a durably persisted counter and a hard refusal when it moves backwards.
- Why is a five-minute timestamp window, on its own, not a replay defence?Because inside those five minutes the same copy is accepted every time it arrives. A window is an expiry rule: it bounds how long a captured message stays useful, which limits the damage window but does not distinguish a second delivery from the first. It becomes a defence only when paired with memory of what has already been accepted within that period.
- A metering endpoint that receives actuate commands has no reliable clock and loses memory on reboot. What survives?Only a counter written to non-volatile storage before the command is acted on. No clock means a window is unenforceable, and an identifier set needs the same durable storage plus an age rule it cannot compute. The critical policy is that a counter appearing to go backwards — after a reboot or a reflash — must cause refusal, not resynchronisation, or a reset becomes a free replay of every past command.
- What should set the retention bound on a remembered-identifier set?The timestamp window, at minimum. Retention shorter than the window leaves an interval where a copy is neither too old nor remembered, and that interval is pure exposure. Retention longer than the window is safe but costs storage for no additional protection, so window and retention are chosen together rather than by two separate teams.
A counter is a turnstile that only ever goes forwards; an identifier set is a guest list of everyone already admitted; a clock window is a ticket that expires. Only the last two survive people arriving out of order, and only together do they cover the whole night.
saying these in an interview costs you the question
- Keeps identifiers forever and calls that a retention bound
- Widens the clock tolerance to hours to stop false rejections
- Assumes a counter works with parallel or out-of-order senders
- Forgets the counter must survive a receiver restart
- Pairs a window with no memory and calls it replay-proof
- Records the identifier after acting rather than before