When Legal Completion Reordering Breaks QoS: Risk Cliffs in NVMe Scheduling

Modern NVMe stacks permit legal completion reordering, yet the QoS impact of this within-spec scheduling freedom is rarely evaluated systematically. We present NVMe-lite, a de- terministic model of an NVMe-like host–device protocol that isolates completion scheduling from protocol state to enable reproducible exploration. We treat the schedule as a second input and parameterize reordering freedom with a bound 𝑘, sweeping 𝑘 across FIFO, Random, Batched, and Adversarial policies, and considering fault modes (NONE, TIMEOUT, RESET). Our results show risk cliffs, beyond policy-specific thresholds, small increases in 𝑘 trigger abrupt transitions into a high-tail state. We quantify realized reordering via a normalized inversion metric (RD) and report p95 latency in scheduler steps. Finally, we extract top-𝐾 poison schedules as deterministic traces for replay and regression testing, and validate a subset differentially against an independent C im- plementation. NVMe-lite enables systematic QoS robustness validation of host–device stacks