a graph whose edges have direction and which contains no cycles - the natural shape of history, derivation, and dependency, because effects cannot precede causes.
Four nodes, four typed edges, every arrow carrying the cid of what it cites.
Hand-authored SVG for this glossary, 2026. Node and edge types per W3C PROV-DM; cid-in-edge invariant per the paper's Section on the evidence object.
Etymology and backstory
pure graph-theory vocabulary that escaped into systems engineering. The acyclic constraint is what makes topological ordering possible - every DAG can be walked parents-first - and that is why build systems, schedulers, and version control all speak DAG natively.
Ecosystem
git commits form a DAG (merges give a node two parents). Airflow and Spark model computation as DAGs. IPFS generalizes content-addressed DAGs into IPLD. W3C PROV documents are DAGs of entities, activities, and agents.
In codexproof
the evidence bundle is a self-contained DAG of signed nodes where each typed link's 32-byte target is the parent's cid. Because the links carry digests, the DAG is simultaneously the lineage graph and the integrity commitment - the same walk that reads the history checks the bytes. Verification is linear in node count (~27us per node, measured through 512), and acyclicity is structural: a cid cannot reference a node that does not exist yet.