A Directed Acyclic Graph (DAG) is a data structure made of nodes connected by edges that have a direction and never form loops. If you start at any node and follow the edges forward, you can never return to where you started. DAGs are fundamental in computer science. Git uses a DAG to represent commit history, where each commit points to its parent. Build tools like Make and Bazel use DAGs to model task dependencies, launching jobs only after their prerequisites complete. Because there are no cycles, the scheduler can guarantee that no job waits forever. In blockchain, some networks (like IOTA and Hedera Hashgraph) use DAGs instead of linear chains, allowing multiple transactions to be processed in parallel rather than sequentially. In machine-learning pipelines, DAGs order data transformations to ensure each step receives the correct input. The acyclic constraint makes reasoning about dependencies straightforward and prevents deadlocks.
Back to Glossary