# Why does an instance of a Contract Net Bidder Reject a Winning Bid When the SLA Deadline Is Expressible Only as a Relative Offset **Date of Record:** 2026 November 16 **Scope:** Applies to contract-net (CNP) auction protocols where a manager agent solicits bids for subtasks and awards based on SLA-bound criteria (deadline, cost, quality). Covers both FIPA-ACL-style `cfp`/`propose`/`accept-proposal` flows and bespoke JSON-schema auctions. Does not apply to single-agent task schedulers or to auctions where all bidders share a synchronized clock source and a common absolute epoch. ## Core Distinction The failure is not a timeout, a lost message, or a majority-quorum problem. It is a **temporal reference-frame mismatch** between the manager's absolute SLA deadline and a bidder's relative-offset deadline, which surfaces only at the *award* step — after the bid has already won on cost/quality. A manager issues a `cfp` with `sla.deadline = 2026-11-14T09:00:00Z` (absolute). A bidder whose internal scheduler is offset-based (e.g., `now + 45s`) computes its feasibility against *its own* `now`, which includes network latency, queue depth, and clock skew. The bidder returns `propose` with `feasible: true` and a `commit_offset_s: 45`. The manager, on receiving the proposal, does not re-validate the offset against the absolute deadline. It awards. The bidder then starts its 45-second clock *at award receipt*, which is later than the manager's `now` at cfp emission by the round-trip plus the award processing delay. The bidder finishes 45s after award; the manager's absolute deadline has already passed. The bid "won" and is simultaneously infeasible. The non-obvious invariant: **a winning bid must be feasible under the deadline reference frame in which the award will be *acted upon*, not the frame in which it was evaluated.** CNP implementations typically validate feasibility at proposal-evaluation time (manager frame) but execute under the bidder frame. These frames diverge by exactly the protocol's own latency, which is unbounded and unmodeled. ## What Was Observed In a three-agent pipeline (manager M, bidders B1/B2/B3) auctioning a 30-second SLA-bound subtask: - M emitted `cfp` at `T0` with absolute deadline `T0 + 30s`. - B1 responded at `T0 + 120ms` with `commit_offset_s: 28` (feasible against its own `now`). - M awarded at `T0 + 400ms` (evaluation + award round-trip). - B1 began execution at `T0 + 520ms`. - B1 completed at `T0 + 520ms + 28s = T0 + 28.52s` — inside the deadline by 1.48s. - **Accepted case.** Now the pathological case: the same flow with B1's `commit_offset_s: 29.7`. B1 completes at `T0 + 30.22s` — 220ms *past* the deadline, despite having bid "feasible" with 300ms of nominal slack. The manager's feasibility check compared `commit_offset_s <= (deadline - T0)` = 30s, a test that passes. It never compared `commit_offset_s <= (deadline - award_time)`. The margin between these two inequalities is the award latency, which under load (retries, queueing) exceeded 500ms in observed traces, and occasionally 2s+ when B2's proposal was malformed and triggered a re-solicitation. A second observed mode: clock skew. B2's host clock ran 800ms ahead. Its `commit_offset_s` was computed as `deadline_local - now_local`, which *understated* the real remaining time by 800ms. The bid looked feasible; execution overran. ## Condition of Validity The bug manifests only when **all** of the following hold: 1. The SLA deadline is expressed (or interpreted) in absolute time by the manager but in relative time by the bidder. 2. Award latency (cfp→propose→evaluate→award→execute-start) is non-trivial relative to the slack margin. 3. The bidder's feasibility computation uses its local `now`, not the manager's `T0` or a synchronized reference. 4. The manager does not re-validate the awarded bid's offset against the absolute deadline *at award time*. When any one fails, the failure is masked. This is why it survives testing: under low latency and generous slack, the margin is large and the bug is invisible. It appears precisely at the SLA boundary — the one condition the protocol exists to enforce. ## Decision Boundary The correct decision rule is: - **Award-time re-validation is mandatory.** Before emitting `accept-proposal`, the manager must compute `effective_deadline = absolute_deadline - award_timestamp` and reject any winning bid whose `commit_offset_s > effective_deadline - safety_margin`. If the top bid fails, fall through to the next-ranked bid, not to re-solicitation (re-solicitation adds another round-trip and worsens the margin). - **Clock skew must be bounded and subtracted.** If bidders are not clock-synchronized (NTP within tolerance), the manager must treat `commit_offset_s` as `commit_offset_s + max_skew_tolerance` and validate against that inflated value. - **Do not trust bidder-reported feasibility.** The bidder's `feasible: true` is a claim about the bidder's frame, not the manager's. The manager owns the deadline and must own the final feasibility test. The boundary is: *feasibility evaluated at proposal time is necessary but not sufficient; feasibility must be re-evaluated at award time under the execution frame.* ## Operational Effect Uncorrected, this produces **silent SLA breaches that look like bidder failures** — the bidder is blamed for overrunning, when in fact the manager awarded an infeasible contract. Retry logic then re-auctions the subtask, but the re-auction inherits the same reference-frame mismatch and reproduces the breach, often with a shrinking deadline that compounds the error. In observed traces, a single mis-awarded contract triggered a re-auction cascade that consumed 3x the subtask's nominal budget in coordination overhead before the manager's absolute deadline forced a hard abort. The fix is cheap: one subtraction and one comparison at award time, plus a skew tolerance constant. The cost of omitting it is an SLA violation that the protocol's own design was meant to prevent. ```python import time class SLAReferenceFrameError(RuntimeError): """Raised when a winning bid is infeasible under the award-time reference frame.""" pass def validate_award( absolute_deadline_ts: float, award_timestamp: float, commit_offset_s: float, max_clock_skew_s: float = 0.0, safety_margin_s: float = 0.05, ) -> None: """ Re-validate a winning bid's relative commitment against the manager's absolute deadline, at award time, under the execution reference frame. Raises SLAReferenceFrameError if the bid cannot complete before the deadline even though it may have passed proposal-time feasibility. """ effective_slack = absolute_deadline_ts - award_timestamp # Inflate the bidder's claimed offset by the worst-case clock skew, # because the bidder computed commit_offset_s against its own clock. required = commit_offset_s + max_clock_skew_s + safety_margin_s if required > effective_slack: raise SLAReferenceFrameError( f"Winning bid infeasible at award time: " f"required={required:.3f}s " f"(commit={commit_offset_s:.3f}s + skew={max_clock_skew_s:.3f}s " f"+ margin={safety_margin_s:.3f}s) " f"> effective_slack={effective_slack:.3f}s " f"(deadline={absolute_deadline_ts:.3f}, award={award_timestamp:.3f}). " f"Proposal-time feasibility does not imply award-time feasibility." ) def award_with_fallback( ranked_bids: list[dict], absolute_deadline_ts: float, award_timestamp: float, max_clock_skew_s: float = 0.0, ) -> dict: """ Award the highest-ranked bid that survives award-time re-validation. Falls through to the next bid rather than re-soliciting, since re-solicitation consumes another round-trip and worsens the margin. """ for bid in ranked_bids: try: validate_award( absolute_deadline_ts=absolute_deadline_ts, award_timestamp=award_timestamp, commit_offset_s=bid["commit_offset_s"], max_clock_skew_s=max_clock_skew_s, ) except SLAReferenceFrameError: continue return bid raise SLAReferenceFrameError( "No bid in the ranked set is feasible under the award-time " "reference frame; all offsets exceed effective slack." ) ```