# Why does an instance of a "best" selector silently return a stale or wrong element under mutation

**Date of Record:** 2026 November 8

**Scope:** Applies to any routine that selects a "best" element (max/min by key, top-k, argmax, best-fit) over a *live* collection that may be mutated concurrently or re-entered between comparison and return. Does not apply to selection over an immutable snapshot or to pure functions over value copies.

## Core Distinction

There are two different questions a "best" selector can answer, and they are not the same:

1. **"Which element is best?"** — a predicate over the current state of the collection.
2. **"Give me the best element."** — a reference/handle to an object that is still best *at the moment the caller uses it*.

A selector implemented as a scan-and-return answers (1). Callers almost always want (2). The gap between them is the boundary condition: the scan observes a sequence of states, the return hands back a handle, and the collection may change between the observation of the winning element and the caller's first use of it. The selector is *correct as a predicate* and *wrong as a delivery mechanism*.

The non-obvious part: the failure is not a race on the comparison itself. Even a fully serialized, lock-protected scan fails this way, because the lock is released before the caller acts. The invariant that breaks is **"the returned element is the maximum over the collection as observed by the caller"** — an invariant no scan-based selector can guarantee without extending the critical section through the caller's use.

## What Was Observed

A task scheduler selected the next job by scanning a priority queue for the least-loaded worker and returning that worker handle. Under load testing with worker churn (workers joining/leaving, load counters updating), the scheduler occasionally dispatched two jobs to the same worker while another worker sat idle, and occasionally dispatched to a worker that had already been deregistered.

Instrumentation showed the scan was internally consistent: at scan time, the returned worker genuinely had the minimum load. The break was downstream. Between `select()` returning and `dispatch()` acquiring the worker, the worker's load had risen (another dispatch) or the worker had been removed. The selector had answered question (1) correctly; the caller consumed the answer as if it were question (2).

A second, subtler observation: when the collection was a `dict` being mutated during iteration, the scan sometimes raised `RuntimeError: dictionary changed size during iteration`, but more often it silently returned a *stale* winner because the comparison loop had already captured a key whose value was updated after comparison but before return. The stale-return case is the dangerous one — no exception, wrong answer.

The same pattern appears in: `max(collection, key=...)` over a shared list; top-k heaps drained while producers append; best-fit allocators returning a block that a concurrent allocator has since claimed; and "pick the healthiest replica" logic where health is recomputed asynchronously.

## Condition of Validity

The scan-and-return selector is valid only when **all** of the following hold:

- The collection is immutable for the entire interval from the first comparison to the caller's last use of the result, **or**
- The caller re-validates the returned element under the same lock/epoch that guarded the scan, **or**
- The result is treated as a *hint* and the consumer is prepared to retry on rejection.

It is **invalid** when the caller assumes the returned handle is still best without re-validation, which is the common case. Note that "the selector holds a lock during the scan" does *not* satisfy the condition — the lock must extend to the consumer's decision point, which a library selector cannot know.

## Decision Boundary

The operational fork is:

- If the consumer can **reject and retry** cheaply (e.g., `try_claim(worker)` returns false and the scheduler re-scans), keep the scan-and-return selector and make the retry loop explicit and bounded. Document that the return is a hint.
- If the consumer **cannot** retry (the decision is committed, e.g., a write is dispatched), the selection and the claim must be a **single atomic operation** — `claim_best()` that scans and marks under one lock, or a compare-and-swap on a version/epoch field. Returning a handle and separately claiming it is the anti-pattern.
- If neither is possible, **version the collection** and have the selector return `(element, version)`; the consumer verifies the version is unchanged before use and treats a mismatch as "reselect."

The boundary is crossed the moment the return value escapes the critical section that produced it. There is no configuration of a scan-based selector that avoids this; it is structural.

## Operational Effect

Teams that miss this boundary see intermittent, load-dependent misdispatch that is invisible in unit tests (immutable fixtures) and rare in staging (low churn), then frequent in production under churn. The symptom is *not* an exception — it is duplicated work, idle capacity, or a dispatch to a dead handle, which surfaces as downstream timeouts far from the selector. Debugging typically chases the consumer, because the selector "looks correct" in isolation and, as a predicate, it is.

The fix is to make the hint/commit distinction explicit in the API and to enforce it at the call site with a version check or an atomic claim. The following guard encodes the invariant that a returned best-element must carry the version it was selected under, and refuses to hand it to a consumer that cannot confirm the version is still current.

```python
from dataclasses import dataclass
from typing import Callable, Generic, Iterable, Optional, TypeVar

T = TypeVar("T")


class StaleSelectionError(RuntimeError):
    """Raised when a 'best' element is consumed after the collection changed."""


@dataclass(frozen=True)
class Selection(Generic[T]):
    element: T
    version: int


class VersionedBestSelector(Generic[T]):
    """
    Selects the best element over a versioned collection and binds the
    result to the collection version observed at selection time.

    The returned Selection is a HINT. It is only safe to consume if the
    caller confirms the version is unchanged (see consume()).
    """

    def __init__(self, key: Callable[[T], float]) -> None:
        self._key = key
        self._items: list[T] = []
        self._version = 0

    def add(self, item: T) -> None:
        self._items.append(item)
        self._version += 1

    def remove(self, item: T) -> None:
        self._items.remove(item)
        self._version += 1

    @property
    def version(self) -> int:
        return self._version

    def select_best(self) -> Optional[Selection[T]]:
        # Snapshot the version BEFORE the scan so any mutation during the
        # scan invalidates the result rather than silently staling it.
        observed = self._version
        if not self._items:
            return None
        best = min(self._items, key=self._key)
        return Selection(element=best, version=observed)

    def consume(self, selection: Selection[T], use: Callable[[T], None]) -> None:
        """
        Consume a selection only if the collection has not changed since
        selection. This is the atomic-claim boundary: selection and use
        must be validated against the same version.
        """
        if selection.version != self._version:
            raise StaleSelectionError(
                f"selection made at version {selection.version}, "
                f"collection is now at version {self._version}; reselect"
            )
        use(selection.element)


# --- Example: scheduler dispatch that must not double-dispatch ---
def dispatch_next(selector: VersionedBestSelector[str],
                  dispatch: Callable[[str], bool]) -> None:
    sel = selector.select_best()
    if sel is None:
        return
    try:
        selector.consume(sel, dispatch)
    except StaleSelectionError:
        # Retry once against the fresh version; bounded by caller policy.
        sel = selector.select_best()
        if sel is None:
            return
        selector.consume(sel, dispatch)  # may raise again; caller decides
```