The tiered canal of Nine Dragon Gorge was the most perilous water passage in the Great Liang Empire.

On either side, sheer granite cliffs pierced the clouds, while the river cascaded through the gorge with a drop of more than a hundred fathoms. To allow heavily laden cargo barges traveling between the northern salt flats and the southern tea hills to climb against the roaring torrent, the Ministry of Works had carved four colossal stone locks out of the living mountain rock—named from lowest to highest: Azure Dragon Lock, White Tiger Lock, Vermilion Bird Lock, and Black Tortoise Lock.

Each lock was commanded independently by a veteran lockmaster. The sluice gates were three feet thick, cast from solid pig iron; on either side of the lock basins stood colossal timber winches and stone mooring bollards as thick as ancient trees.

To prevent catastrophic flash floods and barge collisions, the founding masters had chiseled an iron law deep into the canyon wall: “Gate closed, vessel berthed, cables tied before winches turn; no forward gate shall lift until the vessel astern has cleared.”

In other words, for any cargo vessel to pass through a lock, it had to first lash its thick hemp hawsers securely to the bollards of its current basin, then request the towing cables from the winches of the next lock ahead. Only when the bow of the vessel had crossed entirely past the forward threshold could the mooring ropes in the basin behind be uncoupled.

For a hundred years, the four locks operated under strict local sovereignty. Each lockmaster needed only to watch the water in his own stone basin, and the river ran without flaw.

Until a morning when the autumn mist swallowed the gorge whole.

Dense river fog hung like wet fleece between the cliffs. Four heavily laden vessels entered different reaches of Nine Dragon Gorge almost at the exact same hour: Inside Azure Dragon Lock at the bottom, Master Zhao’s salt barge, massive as an iron fortress, had lashed its stern cables to the bedrock bollards and rested its bow against the current, waiting for White Tiger Lock ahead to raise its iron gate; Inside White Tiger Lock, Master Sun’s colossal timber raft spanned the entire basin, waiting for the heavy winches of Vermilion Bird Lock to hoist it uphill; Inside Vermilion Bird Lock, Merchant Qian’s grain barge, laden with ten thousand bushels of wheat, sat low in the churning pool, quietly waiting for Black Tortoise Lock at the summit to empty its water and vacate a berthing slot; And inside Black Tortoise Lock at the mountain crest, Helmsman Wu’s iron-clad patrol galley was prepared to descend the rapids, but by the laws of the gorge, navigating the violent descent required securing a heavy stern stabilization cable to the primary iron anchor bollard located at Azure Dragon Lock far below before its upper gates dared release the mountain waters!

The fog thickened.

The lockmaster of Azure Dragon Lock leaned on the iron balustrade, peering at the closed gate of White Tiger Lock through the steam of his tea. “Patience, Master Zhao,” he muttered. “Sun’s timber raft blocks White Tiger Lock. Once he moves, we open.” At White Tiger Lock, the operator tapped his pipe against the stone. “Vermilion Bird hasn’t freed its winches yet. What is the rush?” At Vermilion Bird Lock, the pilot leaned over the parapet toward Black Tortoise Lock: “The summit galley hasn’t dropped down. We can only wait.” And at Black Tortoise Lock, the old helmsman stared into the misty gorge: “My stern cable isn’t hitched to the bollard at Azure Dragon Lock. Who would dare run the rapids unanchored?”

An hour passed. Two hours passed.

A full day drifted by. Not a single argument broke out across the canyon. No hulls scraped; no timber splintered; no cables snapped. Every boatmaster sat courteously beneath his canvas awning sipping tea; every lockmaster rigorously obeyed the ancestral statutes.

The mountain river lapped gently against the dark granite walls, whispering in the quiet chill.

Yet the entire chain of four giant locks was utterly, completely, irrevocably frozen.

Not a single vessel could advance an inch. Not a single iron gate could open a crack. Four great ships and four massive locks had silently, politely locked themselves into an unbreakable circular knot.

Within days, merchant boats were backed up for thirty leagues along the riverbanks. When word reached the provincial governor, the newly appointed Transport Commissioner was incandescent with rage.

Priding himself on uncompromising decisiveness, the commissioner slammed his gavel and issued his first emergency decree—“The Incense Severance Edict”: “From the moment a vessel enters a lock, an incense stick shall be lit upon the lockmaster’s desk! If the incense burns to ash before the forward gate lifts, the ship shall be deemed obstructionist! River guards shall instantly sever its towlines with broadaxes, expelling it back to the river mouth to restart its journey!”

Pandemonium ensued.

The very next afternoon, a massive imperial silver transport barge, fighting the fierce alpine current with thousands of stone of bullion, was slowly being winched against the roaring cascade. Just as the three-inch incense stick crumbled into gray ash, the silver vessel was a mere three fathoms from the threshold. The river guards showed no mercy. Broadaxes flashed in the sun! Hawsers as thick as a man’s thigh snapped like dry twigs. The great vessel was cast adrift in the boiling foam, careening down the rapids like a wild beast, smashing three fishing sampans and dumping countless chests of silver into the abyss.

Crude timeout timers were blind: they could not distinguish between a fatal circular deadlock and an honest, heavy ship moving naturally slowly against an alpine current. Innocent heavy carriers were repeatedly cut adrift; rather than clearing the waterway, the river was engulfed in panic and fury.

Unwilling to admit defeat, the commissioner erected a towering three-story pavilion on the cliffside—“The Grand River Sluice Registry”.

He decreed that whenever a ship moored, requested a winch, or waited for a gate, the lockmasters had to write a dispatch and dispatch a red-flag courier on horseback galloping along the precipitous plank roads to the pavilion. Inside, thirty scribes worked on a thirty-foot scroll, painting real-time maps of ship positions and winch dependencies so the commissioner himself could judge who should yield.

Yet mountain paths were treacherous, and fog swallowed the cliffs. By the time a breathless courier reached the summit, fifteen minutes had slipped away. When the scribes finally brushed a stroke showing “Ship A waits for Ship B,” Ship B had already transferred its cable; when they assumed Ship C was sailing freely, Ship C had already docked to wait for a winch. Parchment stacked to the rafters, stained with frantic ink. Couriers broke horse hooves against the mountain stone; thirty clerks coughed blood from exhaustion; yet Nine Dragon Gorge froze just as frequently as before. The Grand Registry had become the single most swollen, fragile bottleneck on the river.

In the third month, Elder Boatmaster Shen, retired Chief Surveyor of the Southern Canals, arrived by imperial commission.

Wearing a simple coarse robe and straw sandals, Master Shen set up no commanding pavilion and summoned no galloping messengers. He walked directly to Azure Dragon Lock, stood beside Master Zhao’s stalled salt barge, and drew from his sleeve a small brass bell sealed inside a light bamboo cylinder.

Carved upon the bamboo was a clean inscription: [Initiator: Zhao Barge; Sender: Azure Dragon Lock; Receiver: White Tiger Sun Raft].

Elder Shen handed the cylinder to Master Zhao and smiled: “Do not sit in silent despair, nor send couriers to the mountain heights. From this day forward, let there be one lightweight rule: Whenever you have waited beyond a modest span of patience without the forward gate lifting, cast this ‘Ripple-Chasing Bell’ to the ship you are waiting upon.

“If that forward ship is actively sailing, let them drop the bell into the riverbed and pay it no mind. But if that ship is likewise blocked and waiting on another, they must not hoard the bell; they must append their own heading and forward the cylinder along the very cable of the vessel they await!”

Master Zhao obeyed. He tied the bamboo cylinder to a throwing grapple and hurled it across the churning foam, landing squarely upon Master Sun’s timber raft at White Tiger Lock.

Master Sun picked up the cylinder. Brooding over his delay at Vermilion Bird Lock, he slid out the parchment, saw that the inquiry came from Zhao astern, and noted that he was waiting on Merchant Qian ahead. Sun immediately dipped his brush, added his entry, and slid the cylinder along the taut winch cable to the grain barge at Vermilion Bird Lock.

Merchant Qian received it, saw he was waiting on Black Tortoise Lock, and cast it forward to Helmsman Wu’s patrol galley.

At Black Tortoise Lock, Helmsman Wu caught the cylinder. He looked down at the massive stern cable in his hands, which stretched miles down the canyon to the bedrock mooring bollard of Azure Dragon Lock. Then his eyes fell upon the red vermillion heading at the top of the parchment: [Initiator: Zhao Barge].

Helmsman Wu gasped. He looked down through the misty chasm. Far below in the deep gorge, the great salt barge holding that very bedrock bollard was none other than the ship that had sent this bell!

Wu lashed the cylinder to a whistling signal arrow, drew his bowstring to his ear, and let fly. With a piercing shriek, the arrow cut through the canyon mist, thudding with precision into the cedar mast of Master Zhao’s salt barge at Azure Dragon Lock!

The brass bell swung in the alpine breeze, chiming with a crisp, unmistakable ring.

Master Zhao pried the arrow loose and unrolled the parchment. Every sailor on the deck stood frozen in astonishment: the parchment had traversed Azure Dragon, White Tiger, Vermilion Bird, and Black Tortoise, stamped by every lock in sequence—and the token that had returned to his fingers was his very own seal!

The loop had closed. The proof was absolute.

No mountain pavilion had been consulted; no broadaxes had severed lines in haste. Master Zhao looked at the chiming bell and burst into hearty laughter: all this time, while cursing the stubborn gates ahead, he had never realized that his own heavy stern cable was the very anchor pinning the summit galley in place!

With the circle laid bare, the deadlock dissolved in minutes. Master Zhao immediately ordered his crew to slacken the bollard line, easing his salt barge back into a sheltered eddy beside the lock. Instantly, the tension on Black Tortoise Lock’s stern cable vanished. Helmsman Wu’s patrol galley plunged through the upper gates; Qian’s grain barge glided into Black Tortoise Lock; Sun’s timber raft surged into Vermilion Bird Lock; and Zhao’s salt barge was pulled smoothly into the cleared basin. The gorge, silent for days, erupted with the roar of cataracts, the creak of winches, and the triumphant songs of a thousand boatmen as the river rushed into boundless life!

—By now you’ve probably recognized it: this is the celebrated foundational algorithm in distributed transaction processing and concurrency control—the Chandy-Misra-Haas Algorithm (Chandy-Misra-Haas Distributed Deadlock Detection / Edge Chasing).

What it is

In distributed databases (such as Google Spanner, CockroachDB, and Vitess), multi-shard transaction processors, and distributed schedulers, transactions frequently acquire exclusive locks (2PL / Two-Phase Locking) across independent physical nodes.

When multiple concurrent transactions compete for distributed resources, distributed deadlocks become inevitable: Transaction $T_1$ on Node A holds resource $R_1$ and waits for resource $R_2$ on Node B (held by $T_2$); Transaction $T_2$ on Node B holds resource $R_2$ and waits for resource $R_3$ on Node C (held by $T_3$); Transaction $T_3$ on Node C holds resource $R_3$ and in turn waits for resource $R_1$ on Node A (held by $T_1$).

Here, the system forms a cyclic dependency chain across the physical network:

No single node possesses a global view of the Wait-For Graph (WFG). Each node only sees its local slice (for instance, Node A only knows that $T_1$ waits for $T_2$). Every transaction waits politely and legitimately; without external intervention, the distributed system freezes permanently.

Traditional remedies suffer from severe operational flaws:

1. Static Lock Wait Timeouts: Setting a hardcoded deadline where transactions that fail to acquire locks are summarily aborted. Like the “Incense Severance Edict,” it cannot tell whether a delay is caused by temporary network jitter, an expensive analytical batch, or a true circular deadlock. Legitimate long transactions are repeatedly slaughtered (false aborts), creating catastrophic retry storms.
2. Centralized Deadlock Detection: Directing every node to periodically ship its local dependency graph via RPC to a central coordinator. Like the “Grand River Sluice Registry,” network latency causes the centralized graph to suffer from stale anomalies and “phantom deadlocks,” while the central coordinator becomes a severe scalability bottleneck and a Single Point of Failure (SPOF).

In 1983, computer scientists K. Mani Chandy, Jayadev Misra, and Laura M. Haas published their landmark paper introducing Edge Chasing (Probe Computation), achieving completely decentralized distributed deadlock detection without global snapshots:

1. Probe Messages: The algorithm defines a lightweight probe message triplet:

   \[\text{Probe}(i, j, k)\]

   where $i$ is the initial transaction that initiated the deadlock detection (Initiator), $j$ is the transaction/node transmitting the probe (Sender), and $k$ is the blocked-on transaction/node (Receiver).

2. Edge Chasing Propagation Rules:
   • Initiation: When transaction $T_i$ blocks on a lock held by $T_j$ and remains blocked beyond a reasonable grace period (preventing probe spam for sub-millisecond lock contention), $T_i$ generates and sends an initial probe $\text{Probe}(i, i, j)$ along the wait-for edge.
   • Forwarding: When a transaction or node $T_k$ receives $\text{Probe}(i, j, k)$:
     • If $T_k$ is actively executing (not blocked), the wait chain is broken. There is no deadlock; the probe is discarded immediately.
     • If $T_k$ is also blocked waiting for locks held by a set of transactions ${T_m}$, the node updates the probe to $\text{Probe}(i, k, m)$ and forwards it along all outgoing local wait-for edges to ${T_m}$.
3. Loop Closure and Resolution: The probe traverses physical nodes strictly along active dependency edges. If a probe originating from transaction $T_i$—namely $\text{Probe}(i, *, i)$—eventually circles back and arrives at $T_i$ itself: A directed cycle in the global wait-for graph has been mathematically proven! A distributed deadlock exists! Without any central coordinator, the system deterministically selects a victim transaction (e.g., the youngest transaction, lowest-cost query, or the initiator $T_i$) and aborts it. Breaking this single edge releases the contested locks, and the entire distributed cluster resumes progress instantaneously.

Why it matters

The Chandy-Misra-Haas edge-chasing algorithm is a foundational pillar of modern distributed relational databases and consensus engines:

1. Complete Decentralization and Zero Single Point of Failure: The algorithm runs purely through point-to-point peer messages along dependency paths. When locks are released normally, probe messages vanish naturally into thin air; only true circular knots cause probes to loop back. Without a central lock coordinator, the system scales horizontally to thousands of nodes without coordination bottlenecks.
2. Elimination of False Aborts and Retry Avalanches: Unlike crude timeout mechanisms, edge chasing is deterministic and sound. A loop closure proves beyond doubt that a deadlock exists. Long-running analytical batches and heavy data migrations are never killed needlessly due to temporary network blips, eliminating wasted work and cascading retry avalanches.
3. Minimal Network Overhead: Probes travel only along edges where active waiting occurs. In a cycle of $N$ transactions, finding the deadlock requires only $O(N)$ messages, avoiding $O(N^2)$ global broadcasts. Probes are tiny metadata packets, dispatched only by blocked processes on demand, imposing virtually zero overhead on high-throughput OLTP workloads.

From multi-shard distributed SQL query planners to microservice saga orchestration, that nimble brass bell traveling along the mooring lines continues to dissolve the most treacherous circular knots in distributed systems with mathematical elegance and minimal footprint.

Metaphor mapping

• Tiered stone locks and narrow basins of Nine Dragon Gorge → Physical database shards and distributed partitions (distributed partitions / shards)
• Merchant vessels (Zhao’s salt barge, Sun’s timber raft, Qian’s grain ship, Wu’s galley) → Concurrent distributed transactions competing for resources (distributed transactions)
• Mooring bollards and iron sluice gates in each basin → Exclusive locks and critical section resources held by transactions (exclusive locks / critical sections)
• Strict local statutes locking all four ships into silent paralysis → Distributed deadlock forming a circular wait in the global wait-for graph (distributed deadlock in global wait-for graph)
• Transport Commissioner’s crude Incense Severance Edict chopping cables → Hardcoded lock wait timeouts that falsely abort innocent heavy transactions (lock wait timeouts & false aborts)
• Towering cliffside Grand River Sluice Registry with galloping couriers → Centralized deadlock detector suffering from stale graphs and coordinator bottlenecks (centralized deadlock detector & SPOF)
• Sealed bamboo cylinder recording Initiator, Sender, and Receiver → Probe message triplet $\text{Probe}(i, j, k)$ (probe message tuple: initiator, sender, receiver)
• Dropping the bell in the riverbed if the forward ship is actively sailing → Immediate probe termination when reaching an active non-blocked transaction (probe discarded at active non-blocked transaction)
• Passing the bamboo cylinder along the forward towline if blocked → Forwarding probe messages along outgoing wait-for edges (forwarding probe along wait-for edges)
• Whistling arrow returning Zhao’s own bell with a crisp chime → Probe looping back to initiator $\text{Probe}(i, , i)$ proving cycle closure (probe loop closure confirming cyclic dependency*)
• Zhao slacking his stern cable to unfreeze the gorge → Deterministic victim selection and transaction rollback to break the deadlock (victim selection & transaction abort to resolve deadlock)