1 Introduction↩︎

Every rank-based selection rule in a drifting environment trusts an object that nobody maintains. Dynamic evolutionary algorithms advance parents by tournaments, keep top segments, protect elites, and carry nondominated fronts, all read off a fitness ranking whose entries were measured at different times; the environment keeps moving between measurements. Re-evaluating the population detects the change but spends the evaluations that would have generated offspring; trusting the cache spends nothing and silently corrupts every decision downstream, advancing the wrong parents and shielding champions that have already fallen. The question this paper starts from is therefore an evolutionary one: what can selection still rely on when current fitness comparisons, rather than arithmetic, are the scarce resource?

Our answer is to build the missing object as a data structure and prove exactly what it can promise. A hidden total order on \(n\) items drifts by elementary moves while a structure spends one truthful pairwise comparison per step and keeps serving rank queries anyway. The deliverable we ask of it is deliberately more than an estimate. It is an estimate with promises: a deterministic bound on how stale every entry can be, a certificate attached to every reported rank that bounds the hidden motion since that entry was last verified, exact recovery laws after abrupt changes, and transfer theorems that carry these promises into whatever consumes the ranking. Truncation, tournament, elitist, and Pareto selection consume exactly this object, and the guarantees survive verbatim because they never reference what the items are. The central technical question is one of maintained guarantees: what can a unit comparison budget promise, per item and per query, about an order it can never see at rest?

The split separates three layers that the dynamic-optimization literature tends to blur, and the paper holds the boundary explicitly. Rank-process maintenance, what the board itself can promise under drift, is proved (Sections 4 and 5). Selection-error transfer, how board error becomes decision error for truncation, tournaments, elitism, and Pareto fronts, is proved, with a coupling proposition carrying per-decision rates into whole-trajectory guarantees for any tournament-driven algorithm (Sections 6 and 7). Optimization performance, what those decisions earn on a particular landscape, is empirical by design, and the full-scale loops of Section 8.10 measure it against the field’s own response repertoire at equal evaluation budgets, with paired tests and effect sizes rather than bare orderings.

Our tractable baseline is a uniform adjacent-transposition process on a Poisson clock, the elementary mutation kernel of the symmetric group read as an adversary. Proposition 2 shows why adjacent swaps are the exact ranking-level primitive of continuous trajectories with isolated crossings; it also makes clear what the abstraction loses. The Poisson and spatial-uniformity assumptions are used only where stated, and the experimental study later replaces them by clustered crossings, hot spots, rate regimes, and nonlocal shocks.

First: what is unavoidable? Theorem 4 shows that any probing schedule fixed in advance, no matter how clever the estimator that digests the answers, must tolerate expected Kendall distance \(\Omega(\min(\alpha,1)\,n)\) at every time beyond a horizon of \(n/2\) steps, with explicit constants (\(\tfrac{n-1}{12}\) at unit rate). The proof technique is the technical heart of the paper: after Poissonization the event counts at the \(n-1\) rank locations become independent, and the parity of the count at any single location is shown to be independent of the entire transcript the algorithm ever sees, provided the location’s two neighbors stayed quiet and the resident pair was never probed directly. Disorder then survives not because the algorithm is slow but because the transcript carries zero bits about a linear number of coin flips.

Second: what structure should one run? We analyze the comparison patrol (Section 4): three arrays and a cursor in \(3n+O(1)\) words; the cursor sweeps the estimate’s adjacent positions cyclically, repairs each local discordance it meets, and timestamps both items it touches. The patrol does \(O(1)\) work per step, answers every query in \(O(1)\), probes every item at least once per cycle, and guarantees a deterministic verification age of at most \(2(n-1)\) for every item at every time, within a factor four of what any schedule with the same budget can achieve (Proposition 6). A boustrophedon variant, which reverses direction at the ends in the manner of coverage paths, trades a slightly better error constant for a deterministic \(4(n-1)\) age bound.

Third: what does the structure cost at equilibrium, and what after a shock? A one-line invariant carries most of the new theory: in a drift-free cycle, every item whose reported rank exceeds its hidden rank is swapped down exactly once (Lemma 2). Consequently the patrol is self-stabilizing in the exact sense of needing at most \(L\) and more than \(L-1\) cycles to sort an estimate whose maximum overstatement is \(L\) (Theorem 7); the reversed board, the worst case, is measured at \(1022.001\) cycles against the predicted window \((1022,\,1023]\) at \(n=1024\). The same lemma prices abrupt change: a shock of overstatement \(L\) is repaired in at most \((L{+}1)(n{-}1)\) probes, a full binary-insertion rebuild costs \(\sum_{m=2}^{n}\lceil\log_2 m\rceil\) probes whatever happened, and the two laws cross at \(L\approx\log_2 n\) (Theorem 8). A hybrid that watches only its own swap counter, the one statistic the structure owns for free, recovers within twice the better pure response without being told \(L\) (Proposition 9). At equilibrium we prove a floor: every location-oblivious prober, the patrols included, holds expected Kendall error at least \(\min(\alpha,1)(n-1)/24\) (Theorem 10), so the patrol equilibrium is \(\Theta(\min(\alpha,1)\,n)\) with explicit constants on both sides; the measured ceiling constant \(0.5\) is stated as a conjecture (Conjecture 11) and audited, rather than asserted, by an exact birth and death ledger of discordant pairs that verifies Little’s law to within one percent (Section 8.4).

Fourth: what can the structure promise per query? Every rank query is answered in \(O(1)\) together with a displacement certificate (Section 5): an interval, computed from the item’s verification age alone, that bounds how far the hidden rank can have moved since the item was last touched. Soundness is Lemma 3, a Freedman-type martingale tail combined with a Poisson tail; the half-width depends on the age only through the ratio \(g/n\), so a patrol-maintained board promises \(\pm 8\) positions at the \(95\%\) level for \(n=1024\), and the same width at \(n=4096\). The promise is served as an explicit two-part contract (Definition 2): a proven motion radius, valid under any maintainer and any schedule, composed with a calibrated residual whose finite-sample validity across independent calibration runs is itself a proposition (Proposition 15), not a hope. The certificates are the kinetic notion of a certificate transplanted to a setting with no trajectories: nothing is known about motion except its statistics.

The same machinery then leaves the line and enters the plane (Section 6). A planar point set in general position is, up to monotone reparametrization, a pair of total orders; when both orders drift, the set of maximal points, the staircase frontier of Kung, Luccio, and Preparata [1], drifts with them. Running one patrol per coordinate maintains the frontier: we prove the purely combinatorial bound \(|M \,\triangle\,\widehat{M}| \le 2(K^x + K^y)\) relating the misreported frontier to the two Kendall distances (Theorem 19), exhibit a family on which the bound is met up to its factor two, and assemble the reported frontier in \(O(n)\) on demand. The charging argument localizes: only discordant pairs with both endpoints on the union of the two frontiers can ever be charged (Theorem 20), which replaces the global Kendall budget by a frontier-incident one and closes most of the gap between the worst-case bound and generic instances, measured across front geometries from logarithmically sparse to fully antidiagonal (Section 8.7).

The maintained order is consumed directly by evolutionary selection (Section 7). Items are candidates, the hidden order is the current fitness ranking, and the patrol supplies truncation, tournament, and elitist selection with explicit staleness information. The connection is carried by theorems rather than analogy. Truncation selection obeys the transfer bound \(|T_k \,\triangle\,\widehat{T}_k| \le 2\lfloor\sqrt{K}\rfloor\) (Theorem 22), and a block-exchange family attains the bound at every value of its right-hand side; a binary tournament between a uniformly random pair errs with probability exactly \(K_t/\binom{n}{2}\) (Proposition 24); and the displacement certificates upgrade to per-decision selection guarantees through a margin rule that selects only items remaining inside the top \(k\) under the certified worst case (Proposition 25). The frontier of Section 6 is the two-objective member of the same family: the staircase is the Pareto frontier of two drifting objectives, maintained on the same budget with the same certificates.

The empirical study has three levels (Section 8). The first treats the structure as a data structure: step time, memory, access locality, certificate tightness, and the reversed-board stabilization law, measured to \(n=65{,}536\). The second stresses the maintenance model: thirty paired seeds, five drift rates, non-Poisson regimes, explicit local and nonlocal shocks with their recovery laws and the hybrid’s switching behavior, a Little’s law audit of the equilibrium through an exact inversion ledger, a split-seed calibration audit of the two-part certificate, and Pareto fronts ranging from logarithmically sparse to fully antidiagonal. The third embeds every policy in the same steady-state EA on Dynamic BitMatching and Moving Peaks. Patrol, periodic full re-evaluation, random partial, elite-first, and sentinel-triggered re-evaluation, no re-evaluation, a budget-free oracle, and the stronger dynamic-optimization responses, random immigrants, triggered hypermutation, memory with reinjection, partial restart, and the patrol+refresh hybrid, are compared under identical total objective-evaluation budgets. We report optimization error, recovery, selection mistakes, Kendall disorder, certified yield, and empirical diagnostics of the induced rank process with paired confidence intervals and multiple-test correction. The diagnostics close a loop the theory opens: the recovery crossover at \(L\approx\log_2 n\) becomes a measurable decision rule, and the benchmark landscapes are placed on the correct side of it.

1.0.0.1 Contributions.

1. A fully specified maintained-order abstract data type under a unit comparison budget: \(O(1)\) probe work, \(O(1)\) certified queries, \(3n+O(1)\) words, an exact unattended-decay envelope (Lemma 1), and an explicit reduction from continuous dynamic fitness to adjacent rank crossings (Proposition 2).

2. An \(\Omega(\min(\alpha,1)\,n)\) steady-state lower bound for all oblivious schedules with explicit constants, by Poissonization and parity decoupling (Theorem 4), and a companion floor of the same order for every location-oblivious prober, the patrols included (Theorem 10): the patrol equilibrium is \(\Theta(\min(\alpha,1)\,n)\) with both constants exhibited and the remaining gap, the ceiling constant \(\approx 0.5\), isolated as a conjecture (Conjecture 11) with an exact ledger-level audit (Section 8.4).

3. The bump lemma and exact self-stabilization: a drift-free cycle swaps every overstated item down exactly once (Lemma 2), so sorting from maximum overstatement \(L\) takes at most \(L\) and more than \(L-1\) cycles (Theorem 7).

4. A deterministic recovery calculus for abrupt change: shock transfer \(K\mapsto K+J\) (Proposition 3), quiet-aftermath recovery within \((L{+}1)(n{-}1)\) probes, a provable crossover against the \(\sum_{m\le n}\lceil\log_2 m\rceil\) rebuild at \(L\approx\log_2 n\) (Theorem 8), and a swap-count hybrid within twice the better pure response without knowing \(L\) (Proposition 9).

5. Displacement certificates with proven coverage, \(n\)-free width at fixed relative age, a non-homogeneous intensity extension (Lemma 3, Corollary 4), and an explicit two-part query contract: proven motion radius composed with a calibrated residual carrying a finite-sample validity guarantee (Definition 2, Propositions 14 and 15).

6. Deterministic, instance-wise frontier bounds: the global charging bound \(|M \,\triangle\,\widehat{M}| \le 2(K^x{+}K^y)\), tight up to its constant (Theorem 19), its frontier-local refinement charging only discordances inside \(M\cup\widehat M\) (Theorem 20), and \(O(n)\) assembly.

7. A selection layer for drifting fitness: the truncation transfer bound \(|T_k \,\triangle\,\widehat{T}_k| \le 2\lfloor\sqrt{K}\rfloor\) with a matching family at every value of the bound (Theorem 22), the exact tournament error identity (Proposition 24), and certified elitism with per-decision confidence (Proposition 25), priced against a generational re-evaluation baseline at equal budget (Section 8.8).

8. A full dynamic-EA evaluation on two benchmark families, eleven policies including random immigrants, triggered hypermutation, memory, restart, and the patrol+refresh hybrid, gradual and abrupt changes, three severities, equal objective-evaluation budgets, and induced rank-process diagnostics that instantiate the crossover of Theorem 8 as a practical policy rule (Section 8.10).

9. A seeded, test-covered ancillary package reproducing every table and figure, including exact theorem tests, per-run CSV data, paired statistical tests, source hashes, and a one-command paper profile.

1.0.0.2 The ledger of claims.

The paper deliberately runs three kinds of statement side by side, and Table 1 is the boundary between them, stated once so that no later sentence has to be read twice. Everything labeled a theorem, lemma, proposition, or corollary is proved in full; everything empirical is a thirty-seed (or ten-seed, where stated) measurement with its protocol in Section 8; exactly one statement is a conjecture, it concerns a single constant, and both of its neighbors, the floor below and the audit beside it, are exact.

The results form three short, independent chains plus two standalone floors, and Figure 1 draws the map: the repair chain (bump lemma to self-stabilization to recovery to the hybrid), the certificate chain (motion tail to two-part contract to certified elitism to failure time to the coupling transfer), and the charging chain (global to localized to its necessity), with the two lower bounds and the transfer identities standing on the model alone. No proof in the paper depends on the conjecture.

2 The drifting-order model↩︎

2.1 Process, probes, estimates↩︎

Let \(V\) be a set of \(n \ge 3\) items. At every time \(t \in \mathbb{N}\) the hidden state is a bijection \(r_t : V \to \{1,\dots,n\}\), the hidden ranking; \(r_t(x)\) is the rank of item \(x\), rank \(1\) being least. Ranks \(\ell\) and \(\ell+1\) are bridged by location \(\ell \in \{1,\dots,n-1\}\).

Time step \(t\) consists of two phases.

1. Drift. \(N_t \sim \mathrm{Poisson}(\alpha)\) events execute, independently of everything else. Each event draws a location \(\ell\) uniformly from \(\{1,\dots,n-1\}\) and swaps the two items currently at ranks \(\ell\) and \(\ell+1\).

2. Probe. The algorithm selects a pair \(\{x,y\} \subseteq V\) and receives the truthful bit \([r_t(x) < r_t(y)]\), where \(r_t\) is the ranking after the drift phase.

The drift kernel is the elementary mutation operator on the symmetric group; a single event is the smallest change a total order can absorb. The algorithm maintains an estimate \(\hat{r}_t : V \to \{1,\dots,n\}\), also a bijection, which it may revise after each probe. A schedule is the rule selecting the probed pairs. A schedule is oblivious if the entire sequence of probed pairs is fixed before time begins (possibly drawn at random, independently of the drift); it is adaptive if probes may depend on earlier answers. Estimators are never restricted: they may be adaptive, randomized, and computationally unbounded. The patrol of Section 4 is adaptive in the mildest possible way (its probe targets depend on its own estimate) and uses \(O(1)\) work per step.

The two stochastic assumptions play different roles. The Poisson clock makes event counts on disjoint intervals independent and supplies the tails used in Section 5. Uniform choice among the \(n-1\) rank locations makes elementary moves spatially exchangeable and determines the martingale variance. By contrast, the shock, selection, and Pareto-front transfer results are deterministic and use neither assumption. The robustness study of Section 8.9 deliberately violates both.

2.2 Disorder functionals↩︎

For two rankings \(\sigma, \tau\) on \(V\) the Kendall distance \(K(\sigma,\tau)\) is the number of discordant pairs, i.e.pairs \(\{x,y\}\) ordered oppositely by \(\sigma\) and \(\tau\), and the footrule \(F(\sigma,\tau) = \sum_{x \in V} |\sigma(x)-\tau(x)|\) is the total rank displacement. Diaconis and Graham [2] proved \[\label{eq:dg} K(\sigma,\tau) \;\le\; F(\sigma,\tau) \;\le\; 2\,K(\sigma,\tau),\tag{1}\] so the two functionals agree up to a factor two and \(F/n\) reads as the mean per-item rank error. We abbreviate \(K_t = K(\hat{r}_t, r_t)\) and \(F_t = F(\hat{r}_t, r_t)\).

Two more quantities are bookkept by the structures of this paper. The verification age \(a_t(x)\) of item \(x\) is the number of steps since a probe last involved \(x\) (items count as verified at \(t=0\)). A displacement certificate for \(x\) is a radius \(D\) such that the hidden rank of \(x\) has moved less than \(D\) since \(x\)’s last verification, with prescribed confidence; certificates are the subject of Section 5.

2.3 Unattended decay↩︎

The first fact of the model is that an estimate left alone rots at unit rate, and the onset of the rot is exactly computable. This curve is the zero-budget envelope against which every maintainer is judged.

2.4 From dynamic fitness to rank drift↩︎

The connection to dynamic evolutionary optimization is exact for gradual fitness motion and deliberately lossy.

The reduction retains exactly what rank-based selection consumes: pairwise order and crossing frequency. It discards fitness gaps, gradients, basin geometry, and the magnitude of improvement. The theory therefore applies directly to truncation, tournament, rank-based replacement, and nondomination, but not to fitness-proportionate selection or adaptation rules that consume numerical gaps. The homogeneous Poisson/uniform-location law is a tractable baseline for the crossing process, not a claim about every dynamic landscape.

There are two cost interpretations. With a comparison oracle, one probe is one duel or preference query. With scalar fitness, comparing two stale candidates requires at most two current objective evaluations. The full EA experiments charge both evaluations and hold the total evaluation budget fixed across maintenance policies.

2.5 Abrupt environmental changes↩︎

An abrupt change need not be represented by a fictitious gradual trajectory. Let \(r^-\) and \(r^+\) be the true rankings immediately before and after a change and call \(J=K(r^-,r^+)\) its rank-shock size.

Gradual drift thus supplies probabilistic age certificates, whereas abrupt changes receive a deterministic damage certificate. When a change detector fires, pre-change age certificates are invalidated until the affected items are probed again; continuing to advertise them would be unsound.

3 A lower bound for oblivious probing↩︎

A schedule with a unit budget touches one pair per step while drift disturbs \(\alpha\) locations per step in expectation. The next theorem makes the resulting deficit quantitative for every oblivious schedule. The proof inspects a window of \(w\) steps, Poissonizes the drift so that the event counts \(H_1,\dots,H_{n-1}\) at the \(n-1\) locations become independent \(\mathrm{Poisson}(\mu)\) variables with \(\mu = \alpha w/(n-1)\), and then shows that for any location whose neighbors stayed quiet and whose resident pair was never probed inside the window, the parity of \(H_\ell\), the one quantity that decides the current order of the resident pair, is independent of the entire transcript. An estimator may be arbitrarily intelligent; on those locations it is guessing a fair-ish coin it has never observed.

4 The comparison patrol↩︎

4.1 The structure↩︎

The patrol index stores three arrays and a cursor: \(S[1..n]\) with \(S[j]\) the item at estimated rank \(j\) (so \(S = \hat{r}^{-1}\)), the inverse \(\mathrm{pos}[x] = \hat{r}(x)\), the timestamps \(\mathrm{last}[x]\) of each item’s most recent probe, and a cursor \(c \in \{1,\dots,n-1\}\). Memory is \(3n + O(1)\) words. One step costs one probe and \(O(1)\) updates.

The cyclic patrol visits locations \(1,2,\dots,n-1\) and wraps around; the boustrophedon patrol reverses direction at the ends, the turning pattern of coverage paths in robotic planning [5]. Both repair exactly the local discordances they meet, which makes a drift-free patrol a bubble sort: with \(\alpha = 0\) the estimate reaches the truth within \(n-1\) cycles [6]. Under drift, repair and decay balance, and the rest of the paper quantifies the equilibrium.

Queries are constant-time reads: \(\mathrm{rank}(x) = \mathrm{pos}[x]\), \(k\)-th item \(= S[k]\), and the order of any two items by comparing positions. Each answer is decorated by CertifiedRank with a radius computed from the item’s age alone.

4.2 Ages↩︎

The boustrophedon patrol satisfies the same \(O(n)\) age guarantee with constant \(4\) instead of \(2\) in (i) (an item near a turning end is probed twice in quick succession, then not for almost two traversals); the case study finds the realized maximum ages of both patrols indistinguishable, concentrated at \(\approx 1.0\,n\).

4.3 Self-stabilization and recovery↩︎

Write \(\ell_t(x) = \hat{r}_t(x) - r_t(x)\) for the overstatement of item \(x\): positive when the board reports \(x\) above its hidden rank. Since \(\sum_x \ell_t(x) = 0\), the positive parts carry half the footrule, \(\sum_x \ell_t(x)^+ = F_t/2\). Call a cycle aligned if the cursor visits locations \(1, 2, \dots, n-1\) in this order, and quiet if no drift event occurs during it. One invariant of the quiet cycle carries the rest of this section.

The theorem is exact in practice, not only in statement: from the reversed board the implementation sorts at measured sweep counts of \(62.016\), \(126.008\), \(254.004\), \(510.002\), and \(1022.001\) for \(n = 64\) through \(1024\), each equal to \(L-1\) cycles plus a single probe, each inside its predicted window \((L-1,\, L]\) (Section 8.1). The sort completes at the first probe of the final cycle because the last surviving overstatement has, by then, descended to the foot of the board. In the language of distributed protocols the patrol is a self-stabilizing structure in the sense of Dijkstra [7]: started from arbitrary corruption it converges to a legitimate state without external intervention, and here the convergence time is not merely bounded but characterized to within one cycle.

Self-stabilization prices abrupt environmental change. An abrupt shock (Proposition 3) leaves the estimate intact and teleports the truth; its damage to the board is exactly an overstatement profile.

The crossover converts the locality of a shock into a policy: a change that overstates no candidate by more than about \(\log_2 n\) positions is cheapest to absorb in place, and a change that scrambles ranks globally is cheapest to rebuild through. A block reversal of width \(w\) has \(L = w-1\); a handful of long-range exchanges already drives \(L\) to \(\Theta(n)\). Neither quantity must be known in advance, because the structure can watch the one statistic it owns for free.

The factor-two structure is the rent-or-buy trade of competitive analysis [8]: patrolling is renting, the rebuild is buying, and the swap counter is the meter. Section 8.6 runs the three policies against block reversals of width \(4\) through \(n\) and against nonlocal exchanges, at \(\alpha = 0\) where the theorem speaks and at \(\alpha = 1\) where it does not; the measured recovery of the pure patrol equals \(L\) sweeps exactly at \(\alpha = 0\), and the hybrid lands within its bound in every run.

4.4 The equilibrium, from both sides↩︎

The patrol is a repair process: each probe removes at most one discordance, and only an adjacent one. This subsection bounds its steady-state error from below by a theorem and from above by a conjecture that the experiments audit at the level of individual discordance lifetimes; the two sides agree on the order \(\Theta(\min(\alpha,1)\,n)\) and disagree only about a constant.

Call a maintainer location-oblivious if the estimate location it probes at step \(t\) is a function of \(t\) alone, possibly randomized independently of the drift. Both patrols qualify (their cursor ignores the answers); the random adjacent baseline qualifies; repeated insertion sort does not (its probe location depends on the comparison outcomes). Theorem 4 does not bound the patrols, because their probed pairs depend on the evolving estimate; the next theorem closes exactly that gap.

The patrol therefore cannot beat the \(\Theta(\min(\alpha,1)\,n)\) law it is measured to obey: disorder of this order is not a deficiency of the cursor but the price of a unit budget, paid by the oblivious class (Theorem 4) and by the location-oblivious class alike. What the theorems leave open is the constant, and we state its value as a conjecture rather than dress a measurement as a theorem.

The conjecture is a stock-flow prediction: a discordance is born at a uniformly random location, waits about \((n-1)/2\) steps for the cursor, and is repaired on the first visit unless drift moves it first, so Little’s law sizes the standing stock at \(K^\ast \approx \alpha \cdot (n-1)/2\). What is rigorous in that sentence is the accounting identity, not the lifetime estimate:

The identities make the conjecture falsifiable at a finer grain than a single number: the experiments can measure births and lifetimes exactly, because the relative order of a fixed pair changes only at drift events of that pair and probe swaps of that pair, so a ledger keyed by pairs tracks every birth and death without approximation. Section 8.4 runs this audit: the product \(\bar\lambda\,\overline{W}\) reproduces the measured \(K^\ast\) to within \(0.2\%\) across two decades of \(\alpha\) and a factor of four in \(n\), the mean lifetime at \(\alpha = 2^{-4}\) is \(0.525\) sweeps against the conjectured \(0.5\), and \(97\%\) of discordances are repaired on the first cursor visit. As \(\alpha\) grows the birth rate per unit drift falls (events increasingly land on already-discordant locations) while lifetimes stretch (repairs compete with re-drift), and the two effects cancel to keep \(K^\ast/(\alpha n)\) inside \([0.508,\, 0.554]\) over the entire grid: the constant the conjecture asserts, observed from inside the queue rather than from its surface.

4.4.0.1 What the patrol buys.

The constants fix the paper’s position in the evolving-data line exactly. Repeated insertion sort is the equilibrium-error champion of that line, and this paper does not contest the title: the patrol concedes \(2.5\)–\(8.6\%\) of raw Kendall error by construction, because its cursor keeps walking where an error-greedy maintainer would linger. What the concession purchases is the maintained interface, and the interface is the contribution. It consists of a deterministic verification age of \(2(n-1)\) for every item at every instant (Proposition 6), a certified displacement interval attached to every reported rank (Section 5), a per-item comparison load capped at two per cycle, exact self-stabilization and recovery laws (Theorems 7 and 8), a provable floor showing the residual error is not the cursor’s fault (Theorem 10), and transfer theorems that carry these guarantees into downstream consumers (Theorems 19 and 22, Proposition 25). None of this is available from the insertion sort: its realized worst-case age runs \(85\%\) higher, fluctuates with the pass structure, admits no deterministic bound at all (Section 8.5), and falls outside the location-oblivious class, so even the floor must be argued differently. The resulting decision rule is sharp. When only the aggregate error of the board matters, run repeated insertion sort. The moment any consumer acts on individual entries (a selection step, a reported frontier, a service-level promise on rank queries), the certificate is the deliverable, and the patrol supplies it at a single-digit premium that Section 8 prices exactly; the comparison against all four natural reference points is fixed in one place by Table 16 in Section 9.

5 Displacement certificates↩︎

A structure that may be \(n\) probes stale must say so. The patrol’s promise is built from the only motion statistic the model grants: between probes, an item’s hidden rank performs a lazy \(\pm 1\) walk driven by the drift events at its two flanking locations.

The protocol is deliberately split-sample: calibrate \(b\) on one set of seeds, audit it on a disjoint set. Section 8.5 runs the split at \(n = 1024\), \(\alpha = 1\) with fifteen calibration and fifteen audit runs: the calibrated padding is \(b = 4\) at target exceedance \(10^{-2}\), the held-out exceedance is \(0.0046\), and the audited coverage of the composed interval at \(\delta = 0.05\) is \(0.99994\). The finite-sample certificate of Proposition 15 is honest about its units: at \(m = 15\) runs it guarantees only \(\varepsilon_b \le 0.32\), and tightens as \(m^{-1/2}\); the rigor lives in the motion part, the sharpness in the audit, and the contract never confuses the two.

6 The evolving frontier↩︎

The frontier layer is a transfer application of the maintained order, the first of two consumers (the second is selection, Section 7), and its claims are scoped accordingly: we do not propose a new dynamic-geometry framework, we prove that the patrol’s promises survive composition into a geometric report. The model boundary deserves to be stated as sharply as the theorems that live inside it.

A finite planar point set in general position is determined, up to a monotone reparametrization of each axis, by its pair of coordinate total orders. Let both orders drift independently at rate \(\alpha\), each probed by its own patrol (two probes per round in total). The maxima \(M\), the points dominated by no other in both coordinates, form the staircase frontier of Kung, Luccio, and Preparata [1]; maintaining maxima under explicit point updates is classical [14], and here the updates are hidden drift. The reported frontier \(\widehat M\) is the set of maxima of the estimated orders, assembled in \(O(n)\) by one sweep down the \(x\)-patrol’s array \(S^x\) keeping the running best estimated \(y\)-position. Reported and true frontier are tied together instance-wise:

The global bound spends one unit of frontier error per discordance anywhere on the board. Rereading its own proof shows that almost all of that budget can never be used: every witness pair the charging argument touches has both endpoints on a frontier.

Two constructions pin the refinement in place: it cannot be improved by more than its factor two, and it cannot be replaced by any quantity that looks at only one of the two frontiers.

Internal disorder of the true frontier alone, or of the reported frontier alone, certifies nothing; the damage is carried by cross pairs between the two, which is exactly what \(K_{\mathrm{loc}}\) counts and what its evaluation over \(M \cup \widehat M\) pays for. The refinement is geometry-sensitive through the single quantity \(|M \cup \widehat M|\): a sparse staircase exposes few pairs to the charge, an antidiagonal one exposes all of them, and the worst case of Theorem 19 is recovered exactly there, so nothing is lost. What is gained is measured in Section 8.7: on independent random orders the realized frontier error is \(0.49\) per snapshot, the localized bound evaluates to \(1.1\), and the global bound to \(2.3 \times 10^3\); across copula-correlated geometries through the fully antidiagonal family the localized bound tracks the realized error within a factor of \(2.3\), while the global certificate stands three to four orders of magnitude above it. The bound is still instance-wise and distribution-free; it has simply learned to look at the staircase before spending the Kendall budget. In the language of multi-objective optimization the staircase is the Pareto frontier, the nondominated set of two drifting objectives; Section 7 completes that reading.

7 Selection under drifting fitness↩︎

The model of Section 2 now returns to the reading that motivates the paper, with nothing changed: a comparison-limited evolutionary selection layer. Items are candidate solutions, the hidden order is the current fitness ranking, adjacent transpositions are the generic ranking-level trace of gradual environmental drift (Section 2.4), and the patrol maintains a certified ranking from which selection decisions can be made with explicit staleness guarantees. This section makes the reading formal. The results are maintenance-layer guarantees: they bound what any selection rule that consumes ranks can lose to drift, beneath and independently of whatever search dynamics run above. Three mechanisms consume the estimate, and each acquires its own theorem: truncation selection keeps the reported top \(k\), tournament selection advances the reportedly fitter of a random pair, and elitism protects reported champions.

7.1 Truncation selection transfers at the square root↩︎

For a ranking \(\sigma\) of \(V\) and \(1 \le k < n\) write \(T_k(\sigma) = \{x : \sigma(x) > n - k\}\) for its top-\(k\) set, so that truncation selection acting on the estimate keeps \(T_k(\hat{r}_t)\) while the environment rewards \(T_k(r_t)\). The damage is the symmetric difference, and it transfers from the Kendall distance at the square root, not linearly.

The bound is global and the realized error is boundary-local: only discordant pairs that straddle rank \(n-k\) move items across the selection boundary, and at equilibrium the patrol’s displacements have \(n\)-free magnitude (Table 6), so the realized symmetric difference is \(O(1)\) per boundary. The case study measures \(0.5\)–\(1.2\) misplaced candidates across every boundary from \(k = 4\) to \(k = 512\) against a transfer bound of \(46\) (Section 8.8); the block-exchange family shows the gap belongs to the instance, not to the theorem.

7.2 Tournament selection: an exact identity↩︎

The identity prices tournament selection on a maintained board with no slack at all. At patrol equilibrium the per-decision error rate is \(K^\ast/\binom{n}{2} \approx 1.1\,\min(\alpha,1)/(n-1)\), vanishing linearly in the population size even though the absolute disorder \(K^\ast = \Theta(\alpha n)\) grows. Some corruption is unavoidable in a drifting environment, since Theorem 4 keeps \(K_t = \Omega(\min(\alpha,1)\,n)\) for the entire oblivious class; the patrol holds the realized rate to within a measured factor \(1.1\) of the balance prediction and, unlike any error-only maintainer, certifies per item how the corruption is distributed. In the vocabulary of dueling bandits [16], the maintainer is the arm-ranking layer, and the identity converts its structural error into the per-duel decision risk of whatever selection runs above it.

7.3 Certified elitism↩︎

Elitism is the selection decision that costs the most when wrong: a candidate protected as a champion after it has silently fallen out of the elite. The displacement certificates of Section 5 turn elitism into a per-decision guarantee.

Under the patrol the rule is uniform rather than adaptive: ages never exceed \(2(n-1)\), so \(D \le 8\) at \(\delta = 0.05\), \(\alpha = 1\) for every \(n\) (Remark 17), and with the calibrated \(b = 4\) the margin is twelve positions. Any candidate reported twelve or more positions inside the boundary can be selected with a per-decision guarantee, on a board of any size, at any time. No maintainer without an age bound offers this: under the random-probe baseline the margin tracks the certified width of the oldest item, which grows like \(\sqrt{\log n}\) and keeps growing. The case study runs the rule at \(k \in \{16, 64, 256\}\), selects \(559{,}800\) candidates, and records one wrong pick (precision \(0.999998\)) while still certifying \(96\%\) of the boundary’s capacity at \(k = 256\) (Section 8.8).

7.4 Selection reliability over time↩︎

The identities above price single decisions; search runs on streams of them, so the layer should also say how long a stream stays clean. The statement is short because the machinery already paid for it.

While no certified failure has occurred, every champion the rule protects is a true member of the top \(k\): elitist tracking-loss events, the silent protection of a fallen elite that costs dynamic optimizers most, occur at rate at most \(\delta + \varepsilon_b\) per certified decision, deterministically accounted. The measured slack is large in the structure’s favor: across \(559{,}800\) certified picks the case study records one error, a realized rate of \(1.8 \times 10^{-6}\) against a contractual \(\delta + \varepsilon_b \approx 0.055\) (Section 8.8).

Per-decision error rates also propagate into whole-algorithm guarantees, not by analogy but by coupling: any conclusion proved for an idealized evolutionary algorithm that sees the true ranking transfers to the same algorithm running on the maintained board, with an additive slack the tournament identity prices exactly.

At the patrol equilibrium \(\bar K \approx 0.55\min(\alpha,1)\,n\) the horizon is \(\binom{n}{2}/(2\bar K) \approx 0.45\,(n-1)/\min(\alpha,1)\) tournaments: for a population of \(512\) at unit drift, about \(230\) consecutive selection decisions are expected to be exactly the decisions of the idealized algorithm. In particular every hitting-time or tracking statement available for the idealized process, for instance in the dynamic runtime-analysis literature [17]–[19], holds for the maintained process up to the stated additive slack, with \(\mathbb{E}K_{(t)}\) supplied by the equilibrium theory of Section 4.4 rather than assumed.

These propositions also mark, deliberately, where the layer’s authority ends. Hitting times, tracking error, and diversity dynamics couple the selection stream to the landscape, the variation operators, and the change process; the frequency-and-magnitude axis of dynamic runtime analysis [18], [19] parameterizes exactly that coupling. This paper contributes the interface those analyses consume: exact per-decision error rates, failure-time floors, and a measurable displacement statistic that locates a landscape relative to the recovery crossover of Theorem 8. When drift decorrelates ranks faster than the budget re-verifies them, no ranking layer can convert order into progress, and the certificates do not pretend to: they report the obsolescence itself, through ages, withheld post-shock coverage, and the swap-rate detector, which is precisely the information an evaluation manager needs to trigger the responses of Section 8.10.

7.5 Two drifting objectives↩︎

Theorem 19 is the two-objective member of the same family. The maxima of a planar point set under its coordinate orders are exactly the Pareto-optimal candidates under two objectives: the nondominated set that multi-objective evolutionary methods in the NSGA line [20] maintain as their population elite. Read this way, the frontier theorem states that if two objectives drift and each is tracked by a patrol on its induced ranking, the reported nondominated set differs from the true one by at most \(2(K^x + K^y)\), instance-wise, with both Kendall distances controlled by their patrols and the assembly costing \(O(n)\) per generation. The measured frontier error of \(0.48\) points per snapshot (Section 8.7) is the two-objective analogue of the boundary locality above: discordances corrupt selection only where they touch the elite.

8 Experimental evaluation↩︎

The paper profile uses thirty paired seeds. The maintenance grid is \(n\in\{256,1024,4096,16384\}\) and \(\alpha\in\{2^{-4},2^{-2},1,4,16\}\), with \(80\) measured sweeps after burn-in; an additional ten-seed run reaches \(n=65{,}536\). Frontier experiments warm-start the estimates because they test maintenance rather than initial construction. The robustness and full-EA protocols are specified in their subsections. Every per-seed observation, confidence interval, statistical test, source hash, and command line is included in anc/results/.

Four maintainers are compared throughout: the cyclic and boustrophedon patrols, the repeated insertion sort (the maintainer with proven \(\Theta(n)\) steady state at unit rate [21]), and the random adjacent probe, which relaxes exactly one ingredient of the patrol, the deterministic cursor, and prices it. The selection study of Section 8.8 adds a fifth, the generational re-sorter: it re-sorts the whole population by binary insertion (about \(n \log_2 n\) live comparisons per generation) and serves the previously published generation meanwhile, the ranking-level shadow of full periodic re-evaluation under the identical unit budget.

8.1 The structure as a data structure↩︎

Table 3 measures the patrol as an artifact rather than as a process: wall-clock step cost, memory footprint, the deterministic age bound, and access locality, reported through the access span, the expected distance between consecutive probed locations, a portable proxy for cache behavior that does not depend on hardware counters. The patrol’s step is a constant-time, span-one operation on three flat arrays; the random baseline performs the same arithmetic yet jumps \(\Theta(n)\) locations per probe and pays for it both in time and, unboundedly, in age. The last two rows close the loop on two theorems at once. The certificate row compares the certified radius at age \(n\) with the realized \(99\)th displacement percentile, the gap being the price of Freedman generality (Section 8.5). The stabilization row starts the patrol from the reversed board, the worst case of Theorem 7, and observes sorting at \(1022.001\) sweeps for \(n = 1024\): one probe past \(L-1\) full cycles, inside the predicted window \((L-1,\, L]\), with the same exactness at every size tested down to \(n = 64\).

8.2 Equilibrium and scaling↩︎

Table 4 and Figure 3 carry the equilibrium story. Four reads. First, \(K^\ast/n\) is constant in \(n\) for every maintainer: the \(\Theta(\alpha n)\) equilibrium of Remark 5 realized. Second, the floor is now two-sided theory rather than analogy: at \(\alpha = 1\) the cyclic patrol measures \(K^\ast = 0.553\,n\) against its own proven floor of \(0.045\,n\) (Theorem 10, a factor \(12.2\)) and the oblivious bound \((n-1)/12\) of Corollary 1; every remaining disagreement between theory and measurement lives in the constant of Conjecture 11, which Section 8.4 audits directly. Third, the collapse: dividing by \(\alpha n\) flattens every cyclic-patrol configuration onto \(0.465\)–\(0.556\). Rates through \(\alpha=4\) remain close to the conjectured balance constant \(\tfrac12\); at \(\alpha=16\) the decline marks the onset of repair saturation rather than a new scaling law. Fourth, the price of patrol structure is small and the price of no structure is not: the boustrophedon patrol sits \(2.5\%\) above repeated insertion sort at \(n = 4096\), the cyclic patrol \(8.6\%\) above, while the random adjacent probe (identical except that its cursor is memoryless) pays a factor \(2.0\) in error and, as Table 6 shows, an unbounded factor in age.

The footrule tells the same story in more humane units: under the cyclic patrol \(F^\ast/n \in [0.994, 1.007]\) for every \(n\) tested. A patrol-maintained board at unit drift is off by one position per entry, on average, at every scale. Against the Diaconis–Graham inequalities 1 the measured ratio \(F^\ast/K^\ast \approx 1.81\) sits near the upper end \(2\): equilibrium disorder is dominated by many small displacements rather than few large ones, which is precisely the regime certificates can afford to be tight in.

8.3 Approach to equilibrium and unattended decay↩︎

Figure 4 shows the two halves of the maintenance trade. Unattended, the estimate loses one pair per event essentially exactly as long as discordances are sparse (the envelope of Lemma 1 is tight to \(4\%\) at \(t = n/4\)), so every idle step has a known, linear price. Attended, the price stops accruing: from a cold sorted start the patrol’s error climbs for about three sweeps and then holds the equilibrium of Table 4 indefinitely. Equilibrium is reached at the speed of the budget, not of the mixing time.

8.4 The equilibrium audited from inside↩︎

The constant of Conjecture 11 is not audited by reading \(K^\ast\) off the board but by metering the queue that produces it. Because the relative order of a fixed pair changes only at drift events of that pair and at probe swaps of that pair, a ledger keyed by pairs records every birth and every death of a discordance exactly; the ledger size reproduces the Kendall distance at every checkpoint by construction, and the experiment asserts this identity rather than assuming it. Table 5 reports the flow at \(n = 4096\) over ten seeds and eighty measured sweeps per configuration.

The audit confirms the conjecture’s mechanism, not merely its number. At \(\alpha = 2^{-4}\) births occur at \(0.97\,\alpha\) per step, the mean lifetime is \(0.525\) sweeps against the ideal \(0.5\), \(97\%\) of discordances die on the first cursor visit, and the Little product matches the measured \(K^\ast\) to \(0.2\%\); the standing stock is \(0.508\,\alpha n\). As the rate grows the queue thickens in a specific, measurable way: by \(\alpha = 4\) only \(58\%\) of drift events create new discordances (the rest land on already-discordant locations and cancel), the mean lifetime stretches to \(0.93\) sweeps, the drift itself performs \(72\%\) of the removals, and the two distortions cancel almost exactly, holding \(K^\ast/(\alpha n)\) inside \([0.508,\, 0.554]\) across the grid, at \(n = 1024\) and \(n = 4096\) alike. Little’s law holds to three digits in every cell, which is the strongest internal-consistency check the model offers: the equilibrium is exactly a queue in balance, its inflow and sojourn measured separately and multiplying back to its size.

8.5 Ages, widths, coverage↩︎

Table 6 is the equity ledger. The patrols convert their deterministic cursor into a deterministic age, and the age into a uniform certified width: every entry of the board is certified to \(\pm 8\) positions at the \(95\%\) level, with realized widths \(\pm 6\), independent of \(n\) (Remark 17). Repeated insertion sort, the better error minimizer, has no deterministic age bound; its realized worst age is \(85\%\) larger. The random baseline decouples age from budget entirely and its widths grow without bound. Per-item probe load makes the same point in the language of fragile complexity [22]: the patrol caps every item’s comparison load at \(2\) per cycle by construction, while the baseline’s load is coupon-collector skewed.

Table 7 tests the promises. Motion-only coverage is \(1.000\) at every gap and level: Lemma 3 is sound with room to spare, and the room is the price of Freedman generality (the certified radius runs \(2.5\)–\(3\times\) the realized \(99\)th percentile). The operational rows close the loop on the full reported interval of Definition 3: with zero padding the patrol’s certificates already cover at \(99.7\%\) against a \(95\%\) nominal level, because the motion slack absorbs the residual estimate error (whose distribution at probe time has mean \(0.60\) and \(p_{99} = 4\)). The same slack buys robustness to rate misspecification: radii computed from an assumed rate \(\hat{\alpha} = \alpha/2\), half the truth, still cover at \(99.95\%\) on the bare drift process at gap \(g = n\), and overestimated rates only widen. The certificates are honest and modestly priced; nothing in them is asymptotic.

The two-part contract is audited by the split-seed protocol of Proposition 15. Fifteen calibration runs at \(n = 1024\), \(\alpha = 1\) set the padding to \(b = 4\) at target residual exceedance \(10^{-2}\) and estimate \(\hat{\varepsilon}_4 = 0.0048\); fifteen disjoint audit runs then measure held-out exceedance \(0.0046\) and composed-interval coverage \(0.99994\) at \(\delta = 0.05\). The finite-sample Hoeffding certificate at \(m = 15\) runs is \(\varepsilon_4 \le 0.32\) at confidence \(0.95\): loose, honest about its \(m^{-1/2}\) units, and irrelevant to the proven motion part, which needs no calibration at all.

8.6 Shock recovery and the rebuild crossover↩︎

Figure 6 runs Theorem 8 and Proposition 9 against the machine at \(n = 4096\): block reversals of width \(4\) through \(4096\) injected into a sorted board (quiet aftermath, \(\alpha = 0\)) and into the living equilibrium (\(\alpha = 1\)), with the pure patrol, the binary-insertion rebuild, and the swap-count hybrid racing to recover. At \(\alpha = 0\) the measurement is the theorem with the slack removed: the patrol recovers in exactly \(L\) sweeps at every width (\(3.0\), \(15.0\), \(63.0\), \(255.0\), \(1023.0\), \(4095.0\) against bounds \(L+1\)), the rebuild needs \(10.0\) to \(11.0\) sweeps regardless, the curves cross at \(L \approx 10 =\) the crossover of Theorem 8(iii), and the hybrid tracks the winner on both sides of the crossing, never exceeding its \(2\,\mathrm{min} + 2(n-1)\) budget: \(4.0\) sweeps at \(w = 4\), between \(22.0\) and \(23.0\) after switching. Nonlocal shocks make the case the locality model cannot: thirty-two random long-range exchanges produce \(L \approx 3544\), the patrol grinds for \(3544\) sweeps while the rebuild finishes in \(10.6\) (Table 8), a factor \(334\), and the hybrid pays only the \(T_0\)-cycle probation before switching.

Two honest boundaries emerge. The crossover and the hybrid’s competitive guarantee are quiet-aftermath statements, and the \(\alpha = 1\) panel shows both why they matter and where they stop: a rebuild that must comparison-shop against a moving truth publishes a stale board, so continuous repair wins every local contest under live drift, while a genuinely nonlocal shock still defeats any local cursor. The policy variable is therefore not the drift rate but the overstatement geometry of the change, which is observable: the swap counter detects that repair is not converging, and the displacement diagnostics of Section 8.10 estimate \(L\) directly from re-evaluation panels.

8.7 The frontier under drift↩︎

The frontier experiments run on the maintenance model directly, two drifting orders and two patrols, and share nothing with the evolutionary benchmarks: they are an algorithms experiment in their own right. They are designed to keep three different quantities from blurring into one another, and they are reported in that order: the safety certificate (the proven bound, evaluated on the same snapshots it protects), the empirical tightness (how far realized error sits below each bound, and how the gap moves with geometry), and the adversarial construction (the family on which the bound is attained, run rather than merely described).

Table 9 and Figure 7 put Theorem 19 in the plane. At equilibrium each patrol carries \(\approx 0.55\,n\) discordances, so the charging bound permits about \(2.3 \times 10^3\) frontier errors; the measured figure is \(0.48\) per snapshot, because the frontier of a random instance passes through \(\Theta(\log n)\) points and only discordances incident to that thin staircase can hurt it. The certificate is doing exactly its job (it is instance-wise, distribution-free, and met within its factor \(2\) on the antidiagonal family, where every point is on the frontier); the experiment quantifies the distance between that worst case and a generic one at three to four orders of magnitude. The snapshot makes the locality visible: two hundred discordances are in the picture and only two of them are anywhere the staircase can feel.

Table 10 is the tightness read, with the adversarial construction as its last row: it prices the localized bound of Theorem 20 across the geometric spectrum, the two coordinate orders coupled by a Gaussian copula from independence through the exactly antidiagonal family. The localized certificate \(2K_{\mathrm{loc}}\) tracks the realized frontier error within a factor of \(2.3\) everywhere: \(1.1\) against a realized \(0.49\) on independent orders, \(89.9\) against \(39.8\) on the antidiagonal family where every point is maximal, while the global budget \(2(K^x{+}K^y)\) stands fixed near \(2.3\times 10^3\) throughout. The refinement costs one pass over \(M \cup \widehat M\) to evaluate, is exactly as distribution-free as the original, and converts the frontier theorem from a safety statement that is loose by three to four orders of magnitude on generic instances into one that is loose by a factor near its own charging constant.

8.8 Selection under drift↩︎

Table 11 and Figure 8 run Section 7 against the machine. Three reads, in parallel with the frontier. First, boundary locality: the patrol misplaces \(0.5\)–\(1.2\) candidates per boundary across \(k = 4\) to \(512\), flat in \(k\) to within noise, while the transfer bound stands at \(46\); exactly as for the staircase, the bound spends a unit on every discordance and random instances put almost none of them where a boundary can feel it. Second, the price of generational re-evaluation: at the identical budget of one comparison per step, the re-sorter’s published board carries \(K^\ast = 2.05\,n\), a factor \(3.7\) over the patrol, because its information is on average half a generation stale; the factor passes through the tournament identity unchanged (\(4.0 \times 10^{-3}\) against \(1.08 \times 10^{-3}\) per duel) and shows up as a factor three to four in truncation error at every \(k\). Continuous certified maintenance beats periodic re-evaluation at equal cost, and the margin is the staleness. Third, certified elitism does what Proposition 25 promises and is not vacuous: with the uniform margin \(D + b \le 12\) the rule certifies \(50\%\) of the boundary capacity at \(k = 16\), \(88\%\) at \(k = 64\), and \(96\%\) at \(k = 256\), and across all \(559{,}800\) certified picks it commits one error. The guarantee costs the picks nearest the boundary and nothing else.

8.9 Non-Poisson drift, shocks, and frontier density↩︎

The baseline model is now stressed in four directions. A compound-Poisson process groups crossings into local bursts of mean six; a hot-spot process places \(90\%\) of events in an \(8\%\) band of rank locations; a regime process alternates rates \(1/8\) and \(4\) once per sweep; and explicit changes reverse a contiguous rank block or exchange random nonlocal positions. All continuous tests use \(n=4096\), thirty paired seeds, and the same mean unit drift budget. For shocks we record the immediate Kendall increase, the area above the pre-change equilibrium, and sweeps required to return within \(25\%\) of that equilibrium. A detected shock invalidates pre-change motion certificates; coverage is resumed only for candidates probed after the detector fired.

Figure 9 shows why a single scalar “drift rate” is insufficient. Concentrating crossings can reduce global Kendall error because the maintainer repeatedly revisits the damaged region, whereas alternating slow and fast regimes leave a larger residual stock. The shock inequality of Proposition 3 holds in every run, but recovery depends on where the inversions land. These experiments are intentionally outside the Poisson/uniform certificate theorem; they test graceful degradation, not nominal coverage.

The Pareto experiment independently varies geometric difficulty. The two coordinate orders are generated by a Gaussian copula with correlations \(0,-0.5,-0.9,-0.99\) and by the exactly antidiagonal construction. Negative correlation thickens the nondominated set from \(\Theta(\log n)\) toward all \(n\) candidates. This closes the gap left by the random snapshot: the charging theorem remains a safety certificate in every regime, while its empirical tightness rises as discordances become increasingly likely to touch the frontier. The fully antidiagonal family remains the adversarial endpoint.

8.10 Full dynamic evolutionary loops↩︎

We next place evaluation management inside an optimizer. Every claim in this subsection lives in one of the paper’s three layers, and each table names its register. Rank-process maintenance (Kendall disorder, ages, certified yield and precision) and selection-error transfer (tournament decision error, certified-pick precision) are the registers where the theory speaks and the conclusions are sharp. Optimizer performance (regret, recovery) couples the maintained ranking to the landscape and the variation operators; conclusions there are empirical by design, comparative, interval-bounded with paired tests and rank-biserial effect sizes, and never extrapolated beyond the two benchmark families. The common steady-state EA uses a population of \(\mu=512\), binary-tournament parent selection, bit mutation at rate \(1/d\) for Dynamic BitMatching, Gaussian mutation for Moving Peaks, and tournament replacement. Dynamic BitMatching uses \(d\in\{256,1024\}\) and target changes of \(1\%,5\%,20\%\); Moving Peaks uses five dimensions, ten peaks, and shift severities \(1,3,6\). Environments change every \(5000\) objective evaluations, either abruptly or progressively. Each run receives \(15{,}000\) evaluations, spanning three scheduled changes.

The main maintenance allocation is \(25\%\), with \(10\%\) and \(50\%\) sensitivity runs. Patrol pays two scalar evaluations for every comparison. Periodic full re-evaluation publishes after a complete pass; random partial and elite-first policies refresh one candidate at a time; the sentinel policy samples eight fixed candidates and launches a full pass after detecting a change; the no-re-evaluation policy spends the entire budget on offspring. The oracle refreshes the population without charge and is therefore an upper control, not a feasible competitor. All non-oracle policies share the same total objective-evaluation budget. A second policy set widens the comparison beyond re-evaluation scheduling to the classic dynamic-optimization responses, charged identically: random immigrants (diversity maintenance), triggered hypermutation, memory with reinjection of archived elites after a detected change, partial restart of the worse half, and the patrol+refresh hybrid of Proposition 9 lifted to the evaluation layer, which patrols continuously and answers a detected change with one full re-evaluation pass.

For every condition and seed we report time-averaged and \(90\)th-percentile regret, recovery evaluations, Kendall disorder, binary-tournament decision error, certified top-\(64\) yield and precision, and the exact number of maintenance and offspring evaluations. Means carry bootstrap \(95\%\) intervals. Patrol–baseline comparisons use paired Wilcoxon tests with Holm correction and matched rank-biserial effect sizes. The tests address evaluation management rather than claiming that this deliberately simple EA is competitive with specialized dynamic optimizers.

Finally, we audit the abstraction itself. On a fixed panel of \(512\) candidates, each environmental change is converted to its induced rank permutation. We measure Kendall burst size, the Fano factor across changes, the normalized entropy of affected rank locations, and the fraction of candidates moving more than one rank. Low-burst, local processes are the regime represented by the adjacent model. Large nonlocal fractions explain when a global re-evaluation pass can outperform local patrol despite having a worse age distribution. This diagnostic is the bridge from a concrete fitness landscape to the assumptions of the maintenance theory.

3.8pt

Table 12 rejects a simplistic winner narrative. At the main \(25\%\) allocation, patrol is slightly more accurate than no re-evaluation on Moving Peaks, but less accurate on the highly nonlocal BitMatching shocks; periodic, elite-first, and sentinel-triggered refresh are more accurate in both representative abrupt conditions. Meanwhile the evaluations spent on every maintenance policy reduce the number of offspring, so no re-evaluation and the free-refresh oracle attain lower regret here. The \(10\%/25\%/50\%\) sensitivity runs make the trade-off explicit: increasing patrol budget reduces its Kendall disorder and tournament error, but can increase optimization regret. Patrol is therefore useful when bounded per-item staleness and auditable recency are requirements, not as a universal replacement for allocating evaluations to search.

Table 13 explains the outcome, and the recovery theory now turns the explanation into a rule. Both benchmark panels produce high-entropy, predominantly nonlocal rank shocks, far outside a single adjacent event per evaluation; the displacement column makes the verdict quantitative. On a panel of \(\mu = 512\) the crossover of Theorem 8 sits at \(L^\ast = C_{\mathrm{rs}}(512)/511 - 1 \approx 7\): BitMatching changes displace the \(95\)th-percentile candidate by \(143\) ranks and Moving Peaks by \(21\), both far beyond \(L^\ast\), so the theory itself prescribes global refresh, or the hybrid, over pure patrol on these landscapes, and the regret table agrees. The prescription inverts where the diagnostic does: the maintenance-layer experiments of Section 8.6 sit below the crossover under gradual drift and local change, exactly where the patrol’s certified repair wins. The practical reading of the pair of tables is a three-way rule: measure the per-change displacement quantiles on a re-evaluation panel; below \(L^\ast\) run the patrol, far above it trigger a refresh, and in between, or when the regime is unknown, run the hybrid, whose probation cost is bounded by Proposition 9. In the reset experiment, serving pre-change motion certificates degrades coverage as shock size grows (to \(0.9695\) for the largest block), whereas withholding them until a candidate is re-probed restores measured motion coverage to \(1.000\) at the half-sweep checkpoint, with \(50\%\) yield. This is precisely the operational failure mode hidden by a homogeneous gradual-drift benchmark.

Table 14 widens the comparison to the standard dynamic-optimization responses, all under the same budget accounting: random immigrants, triggered hypermutation, memory with reinjection of archived elites, partial restart, and the patrol+refresh hybrid that patrols continuously, folds sentinel probes into its budget, and answers a detected change with one full re-evaluation pass. On raw regret the severity sweep orders the policies exactly as a budget argument predicts. At \(1\%\) severity every maintenance policy loses to spending nothing: no-re-evaluation wins outright, and the hybrid trails it with Holm-adjusted \(p = 8.9\times10^{-8}\) and rank-biserial effect \(1.0\), because ten flipped bits are cheaper to outrun with offspring than to audit. At \(20\%\) severity the ordering inverts: no-re-evaluation falls to the bottom third, partial restart and sentinel-triggered refresh lead, and the hybrid significantly beats periodic full refresh (\(p = 0.027\)). No search-side response separates from the simple sentinel elsewhere; the paired intervals overlap. Where the policies separate sharply is the selection layer: on BitMatching the hybrid cuts the patrol’s tournament decision error from \(0.155\) to \(0.121\), and on Moving Peaks from \(0.113\) to \(0.055\), matching periodic refresh while keeping bounded per-item staleness and the certificate interface between changes. This is the displacement rule read off the machine: both panels sit far above the crossover (\(p_{95}\) displacements of \(143\) and \(21\) against \(L^\ast \approx 7\)), so pure patrol is the weakest selection layer here, exactly as Theorem 8 prices it, and the value it retains is the part the regret column cannot see, namely certified, auditable selection between changes. The conclusion the table supports is the paper’s, not a stronger one: as an optimizer-side response the patrol is unremarkable, and as a certified selection-maintenance layer it is cheap, auditable, and composable with exactly the refresh mechanisms that dominate when changes are nonlocal.

3.8pt

Table 15 closes the protocol with ablations along the four axes a budgeted evaluation manager actually controls or suffers: change frequency (the interval between abrupt changes), the maintenance share of the evaluation budget, tournament selection pressure, and population size, each varied around the main setting on the representative BitMatching condition. Longer change intervals reduce both regret and decision error throughout the table. Increasing the maintenance share from \(0.10\) to \(0.50\) lowers decision error for every active maintenance policy but raises regret because fewer evaluations remain for offspring; the no-maintenance row is unchanged by construction. Larger tournaments improve regret for all four policies without uniformly improving decision error, while the smaller population improves regret at the fixed total evaluation budget.

4.5pt

9 Related work↩︎

9.0.0.1 Evolving data.

The model is the sorting side of the evolving data framework: Anagnostopoulos, Kumar, Mahdian, and Upfal [4] introduced sorting against one random adjacent swap per comparison, proved an \(\Omega(n)\) steady-state lower bound for adaptive algorithms, and gave an \(O(n \log\log n)\) maintainer; Besa, Devanny, Eppstein, Goodrich, and Johnson [21], [23] closed the gap by showing repeated insertion sort holds \(\Theta(n)\). Relative to that line, the present paper changes the deliverable: the maintained object is not a ranking but a ranking with promises, meaning deterministic ages, per-item certified intervals, per-item probe loads, exact stabilization and recovery laws, and transfer theorems into the frontier and into selection. The lower-bound side is re-proved twice in forms that yield explicit constants at every drift rate: by Poissonization and parity decoupling for the oblivious class (Theorem 4), and by a dead-zone argument for the location-oblivious class that contains the patrols themselves (Theorem 10), so the structure under study is squeezed between a proven floor and a conjectured ceiling whose constant the lifetime ledger measures from inside. Table 16 fixes the comparison against the reference points in one place.

4.0pt

9.0.0.2 Self-stabilization and queues.

Started from arbitrary corruption, the patrol converges to the legitimate state without intervention, the defining property of self-stabilizing protocols [7], and Theorem 7 pins its convergence time to within one cycle. The hybrid’s rent-or-buy structure is the elementary trade of competitive analysis [8], with the patrol renting, the rebuild buying, and the swap counter as the meter. The equilibrium audit treats the standing disorder as a queue and verifies \(L = \lambda W\) [9], [10] on exact birth and death records of individual discordances; we are not aware of a prior data-structure analysis run at this grain.

9.0.0.3 Noise versus drift.

In the noisy-comparison tradition [24] the ground truth is fixed and the oracle lies; repetition buys certainty. Here the oracle is exact and the truth moves; repetition buys nothing but recency, which is why ages, not error rates, are the structure’s currency.

9.0.0.4 Kinetic structures and patrols.

Kinetic data structures [13] maintain geometry under known motion plans and audit themselves with certificates that fail at predictable events. The displacement certificate of Section 5 is the statistical counterpart when no plan exists. The patrol itself is the maintenance-theoretic cousin of patrolling games [25] (a defender walking a cycle against a stochastic rather than strategic intruder), and the boustrophedon variant borrows its turning pattern from coverage planning [5].

9.0.0.5 Budgets per item.

Fragile complexity [22] bounds how many comparisons a single element may suffer in a static computation. The patrol’s per-cycle load of \(2\) per item is the dynamic analogue, and Table 6 measures what abandoning such a bound costs downstream of the data structure, in certificate width.

9.0.0.6 Evolutionary computation.

Dynamic optimization is a mature subfield of evolutionary computation [26], [27]: moving optima, change detection, and re-evaluation policies are its standard concerns. Dynamic BitMatching continues the theoretically studied dynamic OneMax line [17]; Moving Peaks is the standard continuous tracking benchmark [28], [29]. Runtime analysis of dynamic optimization studies how the frequency and magnitude of change govern trackability [18] and proves regime separations for concrete heuristics on dynamic fitness families [19]; the displacement diagnostics and the crossover of Theorem 8 supply, from the maintenance side, exactly the magnitude statistic that axis parameterizes, together with the per-decision selection error rates such analyses consume. Those literatures typically modify the search heuristic through memory, immigrants, diversity, or prediction. We instead isolate evaluation management inside an otherwise fixed EA and ask what a comparison-limited evaluator can certify about its fitness ranking. Theorem 22 and Propositions 24 and 25 are maintenance-layer guarantees for truncation, tournament, and elitist selection under drift, and Theorems 19 and 20 are the corresponding guarantees for the nondominated set that multi-objective methods of the NSGA line [20] carry as their elite. The theory of randomized search heuristics [30], [31] analyzes the same elementary mutation kernel as an optimizer; here it is the adversary, and Wilson’s mixing bound [3] calibrates how fast it forgets. The full loops of Section 8.10 compare continuous patrol with periodic, random, elite-first, and event-triggered re-evaluation, and with the field’s own response repertoire, random immigrants, triggered hypermutation, memory, and restart, at equal objective-evaluation budgets. The empirical rank diagnostics expose locality, burst size, and displacement quantiles as the variables determining which policy is appropriate, and Theorem 8 turns the displacement diagnostic into a crossover with a proof rather than a heuristic.

9.0.0.7 Adjacent context.

Selecting comparisons under a budget against drifting strengths is the maintenance face of dueling bandits [16], with the objective shifted from regret to structural error. Maxima under explicit updates go back to [1], [14], and sliding windows over data streams maintain skylines under visible arrivals and expiries [15]; the reduction of Theorems 19 and 20 needs no update stream at all, only the two Kendall distances, which is what separates this frontier layer from kinetic maxima (planned motion, event queues), from dynamic maxima under explicit insertions and deletions, and from streaming skylines (Remark 18). Adaptive sorting [32] bounds static sorting cost by the input’s existing disorder; the stabilization law of Theorem 7 is its maintenance-side analogue, with the overstatement \(L\) playing the role of the presortedness measure and the bound exact rather than asymptotic. Background on inversions and bubble passes is classical [6], and the metric inequalities are Diaconis–Graham [2].

10 Concluding remarks↩︎

Selection under drifting fitness has an information problem before it has a search problem, and the object that solves it is a data structure whose true output is trust: not the ranking, which is necessarily wrong somewhere, but exact statements about where and by how much. This paper builds that structure and closes its accounts. The lower bounds say what no schedule can avoid, twice: for oblivious probing by parity decoupling, and for the patrol’s own location-oblivious class by a dead-zone argument, so the measured equilibrium stands on a proven floor. The bump lemma gives the patrol an exact self-stabilization law, measured to within one probe of its prediction, and from it a recovery calculus whose crossover at \(L \approx \log_2 n\) decides, with a proof, when local repair should yield to a global rebuild; a swap-count hybrid obeys the decision without being told the shock. Certificates are served as a two-part contract that never mixes what is proven with what is calibrated, and the equilibrium constant that remains conjectural is audited at the level of individual discordance lifetimes, where Little’s law closes to three digits.

As the evaluation-management layer beneath rank-based selection, the structure carries its boundary conditions inside the theory rather than as caveats around it. Local gradual rank motion is the regime where certified continuous repair wins, and the displacement diagnostics locate any landscape relative to the crossover; the benchmark landscapes fall on the nonlocal side, where the same theorems prescribe refresh or the hybrid, and the equal-budget loops, now including random immigrants, hypermutation, memory, and restart, confirm the prescription in both directions. The resulting contribution is neither a universally superior optimizer nor a relabelled sorting algorithm: it is a certified maintenance layer with explicit floors, exact recovery laws, a falsifiable equilibrium constant, and a decision rule for its own retirement.

10.0.0.1 Reproducibility.

The ancillary directory anc/ contains the drift engines, maintainers, the inversion ledger, dynamic landscapes, full EA loop, selection layer, shock and hybrid policies, statistical analysis, and closed forms of every stated bound. Forty-two tests check engine invariants, rank orientation, deterministic theorems and tightness constructions, the bump lemma and stabilization windows, recovery and hybrid bounds, the equilibrium floor, ledger exactness, shock accounting, variable-rate certificates, evaluation budgets, selection-pressure replay, deterministic EA replay, and seeded stochastic guarantees. Raw and summarized CSV files, commands, source hashes, package versions, and platform information accompany a paper and a quick regeneration profile; README.md documents both.

References↩︎

---

1. Correspondence: alpay@lightcap.ai↩︎