A long-running archive scanner can contractually promise a fixed memory ceiling or a wall-clock deadline; how do you decide which bound to own?

## The two implications, side by side Everything in this decision comes from two facts about how the resources bound each other, and they are lopsided. | you promise | what it implies for the other resource | how useful is that | |---|---|---| | `t` steps | at most about `t` work cells, since each step writes at most one | tight and immediately usable | | `s` work cells | at most `2^O(s + log n)` steps, from the configuration count | true, but astronomically loose unless `s` is tiny | The asymmetry has a one-line cause: **memory is reusable and time is not.** A cell overwritten is a cell you get back; a step spent is gone. So a computation may sit inside a modest memory ceiling forever, and a memory promise cannot by itself keep a latency promise. The one place where the second row is genuinely informative is at the bottom of the scale. A **logarithmic** ceiling forces a polynomial number of steps, because the configuration count is then polynomial. That is why a scanner designed around a handful of pointers and counters over a read-only archive has both bounds at once, and it is the strongest version of the memory promise available. ## What each bound is like to own - **A memory ceiling is enforceable and observable.** The process either fits or it does not; the platform enforces it whether or not you do, and a violation is immediate, local and attributable. - **A memory ceiling is also a design constraint, not a runtime knob.** Meeting it may mean replacing retention with recomputation — extra passes over the archive rather than a structure held in the buffer. That cost lands in latency, which is the resource you did not promise. - **A deadline depends on things outside the algorithm**: the hard instance, contention, the state of whatever it reads. It is a statistical promise dressed as an absolute one unless you know the complexity of the work. - **A deadline fails softly and ambiguously.** The output is partial, the caller must decide whether to retry or degrade, and the failure is usually attributed to the wrong component. ## How the decision actually goes 1. **Establish what is known about the work itself.** If the task has a known polynomial time bound with a known degree and an input size you control, a deadline is defensible and the memory bound comes along with it at the same order. 2. **If the task is only known to fit in polynomial space** — anything with the alternating "for every possible reply" structure, for instance — then no honest deadline exists, because the only time bound anyone can prove is exponential in the space used. Promise the ceiling. 3. **If the task can be pushed down to a few counters and pointers over a read-only input**, promise the small ceiling and get the polynomial time bound free. This is worth real design effort precisely because it is the one case where the memory promise implies a useful time promise. 4. **Decide the failure mode you want to hand callers.** An interruptible computation that can return a usable partial answer converts a missed deadline into a degraded result; a computation that only produces an answer at the end cannot. ## The trap in this decision The common mistake is to read "fits in polynomial space" as reassurance about running time. It is the opposite of reassurance: it says the computation will fit in memory while exploring a space that may be exponentially large, and the whole reason such a computation can be written at all is that it reuses the same cells across an enormous number of possibilities. A team that sizes hardware from the memory bound and then quietly expects proportional latency has drawn the wrong conclusion from the right theorem. The mirrored mistake is to treat a memory promise as costless. Meeting a small ceiling usually means giving up retention, and every dropped structure is repeated work over the input. On an enormous read-only archive that trade is frequently worth making — but it is a trade, and it should be argued rather than assumed. ## What to write down A contract that survives review usually names both resources with different strengths: a **hard** memory ceiling, which is enforceable and falsifiable; and a latency statement whose strength matches what is actually known about the problem — a deadline where the complexity is known, a target with a defined degradation path where it is not. Saying which of the two is the guarantee and which is the target is the part that matters; a document that gives both the same weight has not made the decision at all.