Unix Tools and the FITO Category Mistake: Crash Consistency and the Protocol Nature of Persistence

Source: arXiv:2603.01384 · Published 2026-03-02 · By Paul Borrill

TL;DR

This paper critically examines the widely held assumption in Unix-like systems that filesystem operations exhibit instantaneous atomic state transitions, exposing this assumption as a fundamental category mistake the author terms Forward-In-Time-Only (FITO). Through exhaustive analysis of the entire storage stack—from high-level filesystem tools like ls and mv, through ext4 journaling, fsync semantics, NVMe device flush/FUA commands, down to CPU-level atomicity under Non-Maskable Interrupts—the work demonstrates that no syscall or hardware primitive uniquely defines a safe commit boundary under failure conditions. The paper formalizes this impossibility and shows how temporal assumption leakage occurs across layers, creating a recursive chain of non-atomic dependencies, whose apparent atomicity is mathematically impossible rather than merely engineering deficiency. An extensive appendix documents catastrophic real-world effects resulting from the mistaken FITO model, including massive cloud outages due to retry amplification, database corruptions, silent data corruption at industrial scale, and severe AI training inefficiencies.

Key findings

• No syscall-based persistence primitive, including fsync, can uniquely define commit boundaries under failure by observing return values alone (Section 11).
• ext4, XFS, and Btrfs filesystems can mark pages clean after fsync failures while data is not durable, violating clean(page) => durable(page) invariant (Section 11.1).
• NVMe Flush command can be effectively a no-op depending on device cache configuration, invalidating claims of durability from flush success (Section 12.1).
• x86-64 CPU’s SYSCALL instruction is not atomic with respect to Non-Maskable Interrupts, creating ambiguous kernel entry states (Section 13.1).
• Linux restartable sequences (rseq) implement atomicity as a retry protocol, not atomic execution, confirming atomicity as a protocol outcome (Section 13.2).
• Retrying fsync after failure is not sound recovery: subsequent fsync calls do not retry failed writes, so retries may silently fail (Corollary 1, Section 11).
• The storage stack forms a recursive chain of non-atomic dependencies from CPU through device drivers to filesystem layers, producing systemic uncertainty (Section 15).
• Real-world failures include multihour cloud outages at Google, AWS, Meta, Cloudflare; database corruptions in PostgreSQL, etcd, MySQL; silent corruption at CERN, NetApp, Meta; and AI training overheads consuming 12–43% of compute time (Appendix A).

Threat model

The adversary is any failure mode within the storage stack—from kernel bugs, delayed or out-of-order persistence, device cache volatility, power loss, to CPU-level interrupts—that breaks the assumption of instantaneous atomic state transitions. Adversaries may cause partial writes, reordered persistence, or inconsistent state propagation across layers. The adversary cannot violate hardware axioms, but exploits asynchronous caching and temporal mismatches in layered abstractions to cause uncertainty and crash inconsistencies. It is assumed that syscall return values and application-visible state cannot disambiguate the actual durable state in presence of failures.

Methodology — deep read

The core threat model implicitly involves adversarial or failure conditions in storage stacks—such as crashes, power loss, and system interrupts—that break assumptions of instantaneous atomic state changes. The adversary can manifest as hardware faults, kernel bugs, or device cache inconsistencies, but cannot restore instant atomicity or global consensus with mere read/write primitives.

Data provenance primarily comes from detailed literatures on Linux filesystems ext4, XFS, and Btrfs; NVMe device specifications; and published incidents from cloud providers and open-source DBMSes. Empirical failure scenarios like fsync page dirty bit clearing, NVMe flush no-ops, and CPU NMI behavior underpin the analysis. Real-world incident postmortems from Google Cloud, AWS DynamoDB, Meta, and Cloudflare provide corroboration.

The architecture examined corresponds to the full asynchronous persistence stack: Application-level syscalls like open, write, fsync; filesystem journaling layers (e.g., ext4’s JBD2); operating system page cache and block layer; device firmware implementing NVMe Flush and FUA mechanisms; and CPU features like restartable sequences and interrupt handling.

The paper formulates a formal causal/protocol model describing persistence as convergence of states (Si) across distributed protocol layers N = {App, KernelPageCache, FilesystemJournal, BlockLayer, ControllerCache, PersistentMedia}. Durability requires all layers to reach committed states. Definitions establish that syscall return observations cannot determine this causal convergence uniquely under failure.

The paper demonstrates a concrete impossibility lemma based on observed Linux filesystem semantics: fsync failures yield multiple divergent durable states with the same syscall return, invalidating fsync as a commit boundary. Corollaries detail retry non-soundness and epistemic ambiguity.

Evaluation is largely analytical and formal, synthesizing empirical observations with formal models and prior literature (Herlihy’s consensus impossibility, Linux kernel design discussions). Real-world impact is derived from industry outage postmortems quantitatively estimating outage durations, user impacts, and economic costs.

The LATEX-based build system example illustrates cross-layer temporal assumption leakage leading to downstream failure unrelated to compiler bugs.

No code artifacts or datasets are released; the analysis is conceptual, formal, and empirical based on public documentation, hardware specs, and incident reports.

End-to-end, the paper follows a canonical Linux write path example, analyzing behavior from syscall return, page cache marking, fsync invocation, block layer queuing with FUA flag, NVMe device flush semantics, and persistence guarantees, showing how no single instant or syscall observation guarantees persistence under failure.

The study also relates CPU kernel entry atomicity failures at microarchitecture level to the same protocol-driven view of atomicity established for filesystem and device layers.

Overall, the methodology is a multi-layer cross-stack systems analysis from abstract theory and formal causality to concrete real-world failures, combined with analogies drawn from CPU instruction atomicity to validate the pervasive nature of the FITO mistake.

Technical innovations

• Formal proof that no syscall return value can define a persistence commit boundary under failure in Linux filesystems, due to multiple indistinguishable durable states observed at syscall boundary.
• Identification and formalization of cross-layer temporal assumption leakage as a structural mechanism propagating the FITO category mistake through storage stack layers.
• Demonstration that CPU atomicity failures under Non-Maskable Interrupts and Linux restartable sequences extend the FITO mistake to the hardware layer, blurring the boundary between software/hardware atomicity assumptions.
• Conceptual reformulation of durability as an emergent causal convergence property of distributed persistence protocols, rather than an instantaneous temporal event.
• Detailed taxonomy and synthesis of real-world consequences (e.g., retry amplification leading to planetary scale outages) as arising directly from incorrect FITO assumptions driving recovery protocol design.

Baselines vs proposed

• fsync failure observed behaviors on ext4, XFS, Btrfs filesystems: corrupted durability convergence states despite identical syscall failure return values; retry behavior that does not converge (Section 11).
• NVMe device Flush success with/without volatile write cache: Flush command may be no-op or effective, depending on hardware config (Section 12).
• Restartable sequences (rseq) vs naive atomic execution: rseq achieves atomicity only via detection and retry protocol, confirming absence of instantaneous atomic CPU sequences (Section 13).

Limitations

• Paper is largely analytical with no new empirical dataset or benchmark evaluations; relies on documented behaviors and secondary data from prior work and incident reports.
• Focuses on Linux ext4/XFS/Btrfs and NVMe devices, limiting generalization to other OSes, filesystems, or storage technologies with differing guarantees.
• Does not propose or evaluate concrete new mechanisms or implementations to enforce atomic persistence beyond prior reversible protocols references.
• Assumes adversary/failure conditions but no active adversary model (e.g., malicious fault injection) is explored explicitly.
• Formal models assume full observability of protocol state unreachable to userspace applications; practical implications hinge on incomplete observability.
• Recovery strategies alternative to FITO model like reversible subtransactions are mentioned but not developed or experimentally validated.

Open questions / follow-ons

• How can new filesystem or hardware primitives be designed to provide observable, reliable persistence commit boundaries compatible with failure and retry semantics?
• What formal models and verification frameworks can be developed to systematically represent protocol-level convergence in distributed storage stacks?
• Can reversible subtransaction protocols be practically implemented in mainstream filesystems or databases to circumvent FITO assumptions and their systemic retry amplification?
• How might new CPU architectural features or extensions (like Intel FRED or AMD Supervisor Entry Extensions) fundamentally alter atomicity guarantees for persistence primitives?

Why it matters for bot defense

Bot-defense and CAPTCHA engineers often rely on assumptions that underlying storage and system state transitions are atomic and consistent, especially in systems that track session state, token validity, or rate limits persistently. This paper exposes deep systemic failures in those atomicity assumptions under realistic failure conditions, implying that relying on filesystem- or syscall-level persistence guarantees may lead to state inconsistencies and unexpected failures in security protocols. The identification of retry amplification mechanisms is especially relevant, as bot mitigation systems that use persistent counters or logs may inadvertently trigger cascading failure modes at scale.

Practitioners should be wary of assuming immediate durability or atomic commits from filesystem or OS primitives like fsync, and consider the protocol nature of persistence when designing failover, retry, and consistency mechanisms. Explicit acknowledgment of protocol convergence rather than instantaneous state transitions could guide the design of more robust security infrastructure. Furthermore, understanding the cross-layer temporal assumption leakage problem can guard against subtle bugs when deploying CAPTCHA services over cloud or eventually consistent storage backends.

Cite

@article{arxiv2603_01384,
  title={ Unix Tools and the FITO Category Mistake: Crash Consistency and the Protocol Nature of Persistence },
  author={ Paul Borrill },
  journal={arXiv preprint arXiv:2603.01384},
  year={ 2026 },
  url={https://arxiv.org/abs/2603.01384}
}

Read the full paper

• arXiv:2603.01384 (abstract)
• arXiv:2603.01384 (PDF)