A Debt Loop Doesn't Get Stuck Because of the Numbers

In Moana, an entire ocean of dying islands is stuck because one small green stone hasn't completed its loop. Three friends owing each other $100 are stuck for the same reason.

Three people — A, B, and C — owe each other money in a loop. B owes A $100. C owes B $100. A owes C $100. A fourth person, D, walks up, hands $100 to A, and after a short sequence of payments, every debt is cleared and D walks out with their $100 back.

The first time I saw this, I treated it as a parlor trick: a single bill erased $300 of debt. That's the punchline most people remember. But the more I sat with it, the less interesting the money part felt — and the more interesting the stuckness became. If the debts already cancel on paper (they do — the math is trivial), why does the loop need an outside person at all?

That's where the puzzle stops being about money. Once you redraw the debts as a directed cycle in a graph, the riddle turns into something operating systems textbooks already named: a deadlock. D's $100 doesn't pay $300 of debt. It breaks a circular wait by passing one unit of motion all the way around the cycle.

The debts only look complicated until you draw them as a graph

A debt is a relationship between two people: who owes, who is owed, how much. The cleanest way to write that down is as a directed weighted graph — vertices for the people, directed edges for "owes," edge weights for the amount.

Aditya Bhargava's Grokking Algorithms defines a cycle in plain English: "you can start at a node, travel around, and end up at the same node." That's exactly what this is. Three vertices, three edges, one loop.

The first thing the graph reveals is that every person's net balance is zero.

Formally, this is a conservation law at every vertex — the same shape as Kirchhoff's current law in a circuit:

If everyone's net is zero, the whole system is in a conservation state. No real money has to move at all — in theory, the three of them could agree "we all owe each other the same amount, let's call it square" and walk away. Banks call this multilateral netting, and clearinghouses use it every day to compress millions of gross obligations into a small set of net positions.

The math cancels, but the loop stays stuck on liquidity

This is where the puzzle gets interesting. The math is fine. The graph is fine. But put yourself inside the loop for a second.

A is broke and won't pay C until B pays A first. B is broke and won't pay A until C pays B. C is broke and won't pay B until A pays C. Everyone is holding a claim. Everyone is waiting on someone who is also waiting. No one moves.

That pattern has a name. In operating systems, deadlock exists if and only if four conditions hold simultaneously — what Coffman called the conditions for deadlock. Drop any one of them and the cycle can't form:

Every one of those four conditions is satisfied here. The debts are exclusive (a dollar paid is a dollar moved, not duplicated). Each person is holding their claim while waiting on the next. No one can preempt — A can't reach into C's wallet. And the wait pattern is circular, which is the headline condition of deadlock.

The thing I liked about this framing is that it cleanly separates two questions that look like the same question. Can these debts be cancelled? — yes, the math says so. Will these debts be cancelled, on their own? — no, because the cycle is stuck on liquidity, not arithmetic. A net-zero balance sheet still needs someone, somewhere, to make the first move.

This isn't a metaphor — it's the same graph

It's fair to be suspicious at this point. Sure, debt loops and OS deadlocks rhyme. But debts are abstract bookkeeping and processes hold real resources. Isn't this just a cute analogy?

Back in CSE 120: Principles of Computer Operating Systems with Professor Geoffrey Voelker, the deadlock lecture defined something called a waits-for graph — a directed graph where an edge from P to Q means process P is waiting on a lock that Q currently holds. Swap "lock" for "liquidity" and "process" for "person" and that's the debt graph. Same nodes, same edges, same definition. The OS textbook didn't borrow this construct from finance; finance is just another place the construct shows up.

Voelker's example sealed it for me. He drew three single-instance resources and three processes in a cycle — P1 holds R1 and waits for R2, P2 holds R2 and waits for R3, P3 holds R3 and waits for R1. Three nodes, three edges, one circular wait. Then he added a fourth process P4 outside the cycle holding a second instance of one of the resources. When P4 releases that instance, the cycle unjams in one rotation. P4 is D. "An extra instance held outside the cycle" is D's $100. The OS textbook already drew this picture — the puzzle just paints it with money.

D's $100 isn't money — it's a token

Here's the part that reframed how I think about D. The puzzle calls D's contribution $100, and that's true on a receipt. But functionally, D's bill is a token — a single object that has to traverse the cycle exactly once for the whole thing to unjam.

Notice what happens at every node. The bill arrives, the obligation gets discharged, the bill keeps moving. No participant ends with extra cash. No participant pays more than they owed. The total money in the system is $100 — and that $100 is D's the entire time. They lent the system its first heartbeat, the cycle ran one rotation, and the heartbeat went home.

This is also why the order of payments looks "queue-like" rather than "everyone-at-once." Grokking Algorithms describes a queue as a FIFO — first in, first out — where you process in the order things were enqueued. D's bill is processed exactly that way: each holder receives it, uses it to settle one debt, and hands it on. One bill, one hop, one cleared edge.

Unequal debts don't break the trick — they just leave a residue

A reader could push back here. Sure, this works because every edge weighs $100. What if the debts aren't all equal? Doesn't the trick fall apart?

It doesn't, but the result is more honest. When the cycle has unequal weights, you can still cancel — you just cancel as much as the smallest edge allows. That smallest edge is the bottleneck, and the procedure is the cycle-cancellation algorithm, a building block of min-cost flow algorithms going back to Ford and Fulkerson's 1962 work on network flows:

In notation, for a cycle C in the graph G, the update rule for each edge weight is:

Each new weight on the cycle drops by exactly the bottleneck. At least one edge becomes zero (the bottleneck itself), and that edge gets removed.

Say B owes A $100, C owes B $80, A owes C $60. The bottleneck is the smallest of those — $60. Subtract that from every edge in the cycle:

What's left is no longer a cycle. B still owes A $40 and C still owes B $20 — a directed acyclic graph, which can be settled linearly without any deadlock at all. The equal case isn't a coincidence; it's just the case where the residual graph is empty.

Cycles in directed graphs aren't decoration — they're where flow gets trapped

Once you start looking for this pattern, you find it everywhere flow has to keep moving. CHIPS — the Clearing House Interbank Payments System — runs about $1.8 trillion in daily payments through a patented multilateral netting algorithm where $1 in funding supports up to $29 in settled value. That 1-to-29 ratio is the same trick D pulls with the $100: a small unit of liquidity discharges a multiple of itself when the obligation graph has cycles to net through. Payment networks do the same with a small float of liquidity bridging "circular IOUs." Even traffic deadlocks at four-way intersections look like this: each car holds a position, waits on another, and a single confident driver moving first is the $100 bill of the situation.

The reason BFS shows up nearby is the same. Grokking notes that BFS works on unweighted graphs "to find the shortest path," radiating outward one degree at a time, processed in the order added — a queue. Our token doesn't compute distances, but it borrows the same shape: visit nodes in the order they're reached, never revisit, complete the traversal, and stop. The whole resolution is one BFS-style sweep around a single cycle.

This is also why Dijkstra's algorithm, which Bhargava introduces right after BFS, avoids cycles instead of using them: in a shortest-path search, going around a cycle just adds positive weight without changing your destination. But in a settlement problem, going around the cycle is the whole point — you're not trying to minimize distance, you're trying to discharge each edge.

Four ways to deal with a stuck cycle

Voelker's lecture lists four canonical strategies for handling deadlock. Each one already has a real-world analogue in how systems handle stuck money:

Pick any stuck flow system you've watched up close — a supply-chain freeze, a paycheck cascading late through a startup, a group dinner no one wants to settle — and you'll find people quietly picking one of these four. Knowing which one is being used is most of the diagnosis.

Try it tonight

Open Splitwise on your phone and toggle "Simplify debts." That toggle is running cycle-cancellation on the debt graph between you and your roommates — the exact algorithm in this post, on a smaller graph. Settle a group dinner this week and you're a Ford-Fulkerson user.

Bitcoin's Lightning Network runs into the same problem at internet scale. When liquidity gets trapped on one side of a payment channel, operators run "circular rebalances" — a payment the node sends to itself through a circular path of other channels. Same move as D, with cryptography instead of cash.

One thing to take from this

Two algorithms that look almost identical on the surface — both walk edges in a directed weighted graph — treat cycles as opposites. Dijkstra avoids cycles because they only add weight to a shortest path. Settlement walks the cycle on purpose because the cycle is the discharge mechanism. Same data structure, opposite semantics. The next time you see a graph algorithm, the question worth asking first isn't how does it work — it's what is the walk for.

Sources

• Aditya Y. Bhargava, Grokking Algorithms, Second Edition — Used for: the working definitions of cycles, weighted vs. unweighted graphs, BFS, queues as FIFO, and Dijkstra's relationship with cycles in shortest-path problems (the chapter on graph algorithms is what made the cycle vs. shortest-path distinction click for me)
• Coffman, E. G., Elphick, M., Shoshani, A. (1971), "System Deadlocks", ACM Computing Surveys — Used for: the four conditions of deadlock (mutual exclusion, hold and wait, no preemption, circular wait) referenced in the deadlock framing
• Ford, L. R., Fulkerson, D. R. (1962), Flows in Networks — Used for: the network-flow lineage of the cycle-cancellation algorithm; the procedure of subtracting the bottleneck along a cycle is the same primitive that later min-cost-flow algorithms (Klein 1967, Goldberg–Tarjan) built on
• Geoffrey M. Voelker, CSE 120: Principles of Computer Operating Systems, UC San Diego, Lecture 8 (Scheduling and Deadlock) — Used for: the waits-for graph definition, the three-process / three-resource cycle that mirrors A-B-C, the multi-instance escape (P4 holding an extra resource instance) that maps directly onto D's $100, and the four-strategies framework (ignore / prevention / avoidance / detection-and-recovery)
• The Clearing House, CHIPS — Clearing House Interbank Payments System (theclearinghouse.org/payment-systems/CHIPS; see also PYMNTS coverage of the CHIPS liquidity algorithm) — Used for: the daily ~$1.8 trillion volume and the $1-supports-$29 multilateral netting efficiency ratio
• Splitwise, "What does the Simplify Debts setting do?" (feedback.splitwise.com); algorithm walkthrough by Mithun Mohan K on Medium — Used for: the consumer-app instance of cycle-cancellation that readers can run on their phone tonight
• Lightning Network, Managing Liquidity (docs.lightning.engineering) and the Circular rebalancing plugin — Used for: the modern crypto example of "circular rebalance" — a node sending a payment to itself through a circular path, structurally identical to D's $100