A soup, before any symbols

Tonight's plan is vegetable soup. Chop the vegetables. Boil the broth. Combine them and simmer.

Two of those steps don't care about each other. You can chop first, boil first, or — if a friend helps — do both at once, and the soup comes out identical. But no cook on earth can do the combining first: there is nothing to combine yet. The steps have an order, and the order isn't a line — it's looser than a line. Some pairs of steps are ordered ("boil before combine") and some aren't ("chop" vs. "boil").

You already know this structure so well you never think about it. Recipes, furniture assembly, getting dressed (socks before shoes, but socks and shirt in either order), a morning routine — all of them are sets of steps where some orderings are mandatory and the rest are free. All this chapter does is draw that structure, name it, and then show you that three of the most important pieces of software ever written are built on exactly it.

Draw the arrows, drive the graph

Draw each step as a dot, and draw an arrow from each step into every step that needs its output. Chop → combine. Boil → combine. Nothing points into chop or boil (they start from raw ingredients), and nothing prevents them from happening side by side.

Here is that soup, live. The dots on the left are ingredients, the middle dots are work, the right dot is dinner. Click any node and watch what turns stale downstream — everything that transitively needed it. Click chop and notice, just as important, what doesn't light up.

That ripple you just watched has a name in every serious software system: the invalidation cone — the set of things that must be redone because something they depended on changed. Your hands now know the two rules the rest of this chapter is built on: change flows only along arrows, and things with no arrow between them are free — free to run in any order, free to run in parallel, free to not care about each other.

Two dishes, one broth

Now the interesting night: soup and risotto. Both recipes call for boiled broth.

No cook boils broth twice. You make one pot and both dishes draw from it. Obvious in a kitchen — but pause on what made it possible: both recipes named the same thing. Not "the broth from the soup recipe" or "the broth from the risotto recipe" — just boiled broth, a name that depends only on what it is, not on who wants it.

Before you drive it, commit to a prediction.

Now watch the graph agree with you. One broth node, two dishes hanging off it. Click broth.

One node, two parents. That little diamond-ish shape — work flowing apart and meeting again — is the whole difference between a tree (where every node has exactly one parent, like a family tree of steps) and the structure we're actually holding. Trees can't share. This can.

Naming the structure

You have now done everything the formal definition asks. Time to collect the vocabulary — each term is just a name for something your hands already did.

The dots-and-arrows picture is a directed graph: directed because each arrow has a direction (broth flows into soup; soup does not flow into broth). And ours has one more property, so natural in a kitchen you never noticed it: following arrows can never bring you back to where you started. No step is, however indirectly, its own ingredient. A directed graph with no round trips is a directed acyclic graph — a DAG.

Why is "acyclic" the load-bearing word? Imagine the broth needed the soup and the soup needed the broth. Neither can be made first: dinner is not late, dinner is logically impossible. A cycle in a dependency graph isn't a longer to-do list — it's a contradiction. The absence of cycles is exactly what guarantees the to-do list can be written at all: there is always some valid order to do the work in (do anything whose inputs are all ready; repeat). Such an order is called a topological order, and "acyclic" is precisely the promise that at least one exists.

But “reject every cycle” is sometimes too crude. Suppose parser imports syntax, syntax imports token, and token imports parser. From any one of those modules, arrows lead to the other two and back. They are not three independently schedulable jobs. They are one tangle wearing three filenames.

The precise name is a strongly connected component: a largest group of nodes in which every node can reach every other. Collapse each such group to one super-node. The surprising result is that the graph of super-nodes can never contain a cycle. If it did, all super-nodes on that cycle could reach one another and should have been one component.

That sentence turns a defect report into a repair strategy. A compiler can report the smallest mutually dependent import group. A deadlock analyzer can isolate the locks participating in a wait cycle. A build tool can schedule the condensation DAG even when the original graph is not acyclic—provided it knows how to process each knot as one unit.

There is another boundary worth recognizing. Remove the arrowheads and ask only whether the graph is connected. If $n$ nodes are connected by exactly $n-1$ edges, the shape is forced: it is a tree. Why? Begin with one node. Each new edge can connect at most one previously unconnected node without forming a cycle, so reaching all $n$ nodes needs at least $n-1$ edges. If a connected graph has exactly that many, not one edge is spare. Adding any edge creates a cycle; removing any edge disconnects it.

This rigidity explains both the beauty and the limitation. A directory tree gives every child one path from the root, so navigation is unambiguous. The shared-broth graph cannot be a tree: broth feeds two dishes. When a network has redundant links, choosing a spanning tree temporarily removes cycles while keeping every machine reachable.

The second idea — one broth pot, two dishes — also has a name. When two recipes wrote "boiled broth" they were naming the step by its content: the name captured what the thing is (these inputs, this operation) and nothing about who wanted it or where it sits. Give identical work identical names, and the graph cannot help but share: two nodes with the same name are one node.

Software makes this precise with a hash: a short fingerprint computed from data, built so that the same data always produces the same fingerprint, and different data essentially never collides. Name every node by the hash of its content — and, for a step, by the hashes of its inputs plus the operation — and "same work" and "same name" become the same sentence. Computer scientists call the technique hash-consing when it's used to share identical subterms of a structure, and a DAG whose node names are hashes that include their children's hashes is a Merkle DAG, after Ralph Merkle, who introduced hash trees in 1979.

The Merkle construction buys one more thing, and it's the quiet superpower: because a node's name includes its children's names, a change anywhere below changes every name above it — and only those. Rename nothing: the unchanged parts keep their old names, byte for byte. The name at the top of the graph is a tamper-evident summary of everything underneath. Compare two roots: same name, provably same everything; different name, walk downward and the first differing names point you straight at the change. The invalidation cone you clicked through in the soup isn't a metaphor for this — it is this, run upward through the names.

One caution your kitchen already taught you: sharing only happens if the two recipes spell the name identically. "Boiled broth" and "broth, boiled" are the same dish and different strings. Content-addressing inherits exactly this: the content must be put in a canonical form — one agreed spelling — before hashing, or identical things get different names and the sharing silently evaporates.

Before the famous systems, make the picture yours. The analyzer below speaks the bounded step language — one step per line, soup: chop, broth — and computes everything this chapter has claimed: a valid cooking order (the topological schedule), the longest chain of forced waiting (the critical path), and, when you click any node, the exact invalidation cone. Paste your morning routine, your build, your deploy pipeline. Try writing a cycle and read what it tells you.

The same picture, three famous times

Everything above is a complete description of three systems you may use every day. The labels change; the shape does not.

Git. The Pro Git book opens its internals chapter with the thesis, verbatim:

Git is a content-addressable filesystem. Great. What does that mean? It means that at the core of Git is a simple key-value data store.

Every file snapshot (blob), directory listing (tree), and commit is stored under the hash of its content. A commit names its tree and its parent commits — hashes naming hashes: a Merkle DAG. That is why two branches containing the same file store it once; why history cannot be quietly rewritten (every descendant name would change); and why git status can know what changed without reading your whole project — same name, same content, skip.

Build systems. A compile step is a soup step: inputs in, operation, output out. Bazel and Ninja hold the whole build as a DAG of such steps, and Bazel keys its caches on a hash of each action's inputs and command line — content-addressed cooking. Touch one source file and the invalidation cone you clicked in the soup figure is precisely what rebuilds: everything downstream, nothing else. The promise that a build's cost tracks the size of the change rather than the size of the project rests entirely on these two ideas.

Docker and IPFS. A Docker image is a stack of layers, each named by a digest of its content; ten images built on the same base share those layers on disk and over the network, because same name is same bytes. IPFS generalizes the move to a global file network: content addresses instead of locations, so any copy of the data, anywhere, is the data.

Three domains — version control, compilation, distribution — and one data structure, arrived at independently, because the two underlying ideas compose so well: the DAG says what depends on what, and content-addressing says what is identical to what. Dependencies plus identity: that is the shape of memory.

Where the shape runs out

Honesty about the boundaries, because every one of them is a real engineering headache somewhere:

• The world has cycles. Two source files that import each other, a spreadsheet cell referring to itself, mutually recursive functions. A DAG cannot represent them; systems must reject the cycle (most build systems fail loudly), break it by hand, or bundle the cycle into one bigger node and lose sharing inside it.
• Content names can't say "latest." A content address names one frozen value forever; it can never mean "whatever the newest version is." Every content-addressed system smuggles mutability back in as a small mutable layer of references — Git's branch names are exactly this: a human name pointing at a hash, and the only part of Git that changes in place.
• Hashing isn't free, and canonical forms are work. Every byte must be fingerprinted, and equal-but-differently-spelled content (an unsorted vs. sorted list, a timestamp in a file header) must be normalized first or sharing quietly fails. Reproducible-builds work is, in large part, a war against accidental non-canonical bytes.
• Not every equality is byte equality. Two functions can compute the same result with different code; content-addressing will never see them as one. It shares spelling, not meaning — deciding semantic equality is, in general, impossible (a cliff this trip walks up to properly in a later chapter).

Lessons

• A dependency structure where some orders are forced and the rest are free is a directed acyclic graph; you operate several before lunch.
• "Acyclic" is the guarantee that the work can be ordered at all: no cycles, therefore a topological order exists.
• A cyclic graph is still a DAG at a coarser scale: collapse each strongly connected component, and its condensation is acyclic.
• A connected undirected graph with $n$ vertices and $n-1$ edges is forced to be a tree. A spanning tree preserves reachability with the minimum number of edges.
• Change propagates only along arrows — the invalidation cone — so the cost of a change tracks the change, not the system.
• Name work by its content and identical work gets identical names: sharing and change-detection stop being features and become arithmetic.
• Merkle naming (hashes of hashes) makes one root name pin down — and tamper-evidence — an entire structure.
• The boundaries are real: cycles must be rejected or broken, "latest" needs a mutable reference layer, and sharing lives or dies by canonical form.

Practice

The next question is about recombination

A graph tells a scheduler which branches are independent. It does not yet justify splitting one calculation across those branches. Suppose four workers count four regions of a log and return four partial totals. May the scheduler combine the left pair first today, the right pair first tomorrow, or merge results as they arrive? For addition, yes. For subtraction, no.

The graph has exposed the freedom. The next chapter names the law that makes exercising that freedom safe.

References

1. Chacon & Straub. “Pro Git, ch. 10: Git Internals — Git Objects.” 2014. — read this next if Git is your fastest route to caring — the content-addressable store, hands on, in about twenty minutes
2. “Directed acyclic graph.” — and topological sorting — the reference definitions, with the standard algorithms (Kahn's, DFS)
3. Cormen, Leiserson, Rivest & Stein. “Introduction to Algorithms, 4th ed..” MIT Press, 2022. — ch. 20, elementary graph algorithms — read when you want the proofs: DFS, topological sort, strongly connected components
4. Merkle. “Secrecy, Authentication, and Public Key Systems.” Stanford PhD thesis, 1979. — the thesis that introduced hash trees — the origin of "one root name pins down everything below"
5. “Hash consing.” — the sharing technique beyond storage systems — language runtimes and proof assistants
6. “Artifact-based build systems.” Bazel docs. — the build-system half of this chapter in the system's own words; pairs with the Ninja manual for a minimal, readable contrast
7. “Docker build cache.” Docker docs. — and IPFS: Merkle DAGs — content addressing at distribution scale, this chapter's ideas in a different accent
8. Graham, Knuth & Patashnik. “Concrete Mathematics.” Addison-Wesley, 1994. — for the counting-and-recurrences muscle this trip builds toward; ch. 1–2 pair well with the coming chapters