Deep within the Zhongnan Mountains, nine sword pavilions rose into the azure mist. Arranged in three vertical ranks and three horizontal tiers along the sheer precipices, they formed an ancient formation known as the Grid of Nine Groves.

In the abyssal chasm cradled at the center of the nine peaks hung the Great Primordial Bell, cast by the founding patriarch from meteoric iron. When struck, its sonorous resonance swept through the valleys, washing impurities from a swordsman’s spirit and enabling breakthroughs across martial boundaries. Yet the stone vault was narrow and the bell’s reverberations ferocious: under heaven and earth, no two mallets could ever strike the bronze chime at the same moment. Should two pavilions strike in unison, the intersecting harmonics would tear through the gorge, collapsing the cavern into oblivion (the mutual exclusion guarantee).

In former years, to ensure only one swordsman entered the vault, the peaks relied on the “Decree of the Central Pivot.”

The Grand Elder of the central Tian-Shu Pavilion held sole custody of the bell’s admittance tablet. Any pavilion wishing to strike the bell had to dispatch swift couriers to Tian-Shu Peak to petition for the token. But as decades passed and the Grand Elder grew frail, petitions piled like hills outside his hermitage, turning the central pavilion into the greatest bottleneck in the mountains. During one harsh winter, an avalanche severed all mountain paths to Tian-Shu for three months; the entire range was paralyzed, and not a single soul could approach the sacred bell (a single point of failure and bottleneck).

Later, the sword alliance discarded the central arbiter in favor of the “Universal Consent of the Peaks.”

The new rule ran thus: whoever wished to ring the bell had to loose eight white-feathered hawks across the sky, one to each of the other eight pavilions. Only when all eight master seals had been gathered could a swordsman step into the cavern with mallet in hand. At first, with only nine pavilions, each turn demanded sixteen hawks; but when thirty-six cloisters eventually joined the mountain covenant, every chime required seventy messengers darting across the clouds. The skies darkened beneath beating wings, courtyard gates echoed with endless squawking, and if an elder in some remote outpost fell into prolonged meditation, the entire alliance froze in indecision ($O(N)$ message explosion and extreme vulnerability).

In the late autumn of that year, Elder Maekawa came stepping upon the misty clouds.

Gazing down from the highest peak upon the vast chessboard of stone towers, he brushed his wide sleeves and smiled: “To grant one swordsman exclusive access to the chime, why must we agitate every bird under heaven? And why must we prostrate before a single master?”

Unfurling a scroll of pure silk, Elder Maekawa laid out the nine pavilions in a three-by-three lattice: Pavilions 1, 2, and 3 formed the first tier; Pavilions 4, 5, and 6 formed the second tier; Pavilions 7, 8, and 9 formed the third tier.

Thereupon, he established the Covenant of Lattice Rings:

First, Intersecting Quorums of Five. A pavilion desiring the chime need not petition the entire world. It had only to seek bronze tallies from those pavilions sharing its own rank and its own file (in a three-by-three grid, including itself, a voting quorum of five pavilions). Elder Maekawa traced his brush across the silk: “Pick any two pavilions, no matter how distant their peaks. Their respective ranks and files must intersect at one or two shared pavilions! Pavilion 1 gathers tallies along its row and column; Pavilion 6 gathers tallies along its own. Their circles of allies are destined to meet at the crossing stones.”

Second, One Tally Shall Not Serve Two Masters. Within each pavilion, the Keeper of the Seal guarded exactly one bronze tally representing that pavilion’s solitary vote. The law of the peaks was unbending: once a Keeper had lent out his bronze tally, he could not bestow it upon another until it was safely returned!

Hearing this, the mountain masters struck their palms in delight: brilliant! Because every pair of quorums intersected, any two petitioners would inevitably collide before at least one shared Keeper. And because that Keeper held only one tally, he could never grant his vote to both contenders at once. It was mathematically impossible for two pavilions to simultaneously collect all five tallies! Mutual exclusion stood as solid as bedrock. Furthermore, the flock of messenger birds required for each chime plummeted from dozens to a mere handful ($O(\sqrt{N})$ complexity).

Yet within exquisite elegance lay a slumbering peril.

On the dawn of the Spring Equinox, three chief disciples—from Pavilion 1, Pavilion 6, and Pavilion 8—simultaneously felt the spark of epiphany and sought the sanctuary. Pavilion 1 loosed its hawks and secured the tallies of its row, yet sat waiting for the column shared with Pavilion 6; Pavilion 6 gathered its row, yet waited in vain for the column crossing Pavilion 8; Pavilion 8 held its column, yet languished waiting for the crossing of Pavilion 1!

Each pavilion held half the needed tokens; each arbiter at the crossroads held firm to the command: “Never grant a loaned tally to another.” Hawks wheeled fruitlessly above the sea of clouds; the heavy bronze portal remained barred. Pavilion 1 could not retreat, Pavilion 6 could not advance, and Pavilion 8 was paralyzed. A suffocating deadlock gripped the mountain (deadlock via circular wait)! The great bell stood mute, while tension between the factions threatened to shatter the alliance.

At that fateful moment, Elder Maekawa descended upon the bell tower, struck a jade chime beside the water clock, and proclaimed the Three Decrees of Yielding:

First, Order by the Water Clock. Whenever a pavilion dispatched hawks to petition for tallies, it had to stamp each parchment with the exact mark of the mountain water clock. When claims clashed, the earlier water-tally held precedence; the later yield to the elder.

Second, The Inquiry (Inquire). If a Keeper had already lent his tally to a later petitioner, and a request arrived from an earlier petitioner bearing greater seniority, the Keeper could not sit idle. He had to shoot a golden arrow of inquiry (Inquire) to the junior petitioner: “My tally rests in your hands, but have you assembled your full five tokens and entered the sanctuary? If not, remember the order of the clock!”

Third, Resignation (Failed) and Yielding (Yield). If that junior petitioner had already encountered locked doors elsewhere—receiving a letter of refusal (Failed) proving it could not possibly complete its set—the arrival of an Inquire forbade all stubborn hoarding. The junior petitioner had to bow, draft a message of surrender (Yield), and immediately return the borrowed tally to the Keeper!

Upon receiving the yielded tally, the Keeper instantly bestowed it upon the senior petitioner. With all five tallies finally assembled, the senior swordsman strode serenely into the sanctuary, striking the Great Primordial Bell until dragon chants echoed across the peaks! When the meditation ended, the swordsman departed, releasing all five tallies (Release) back to their home peaks. Only then did the Keeper grant his tally once more to the junior aspirant.

That night, the bell resonated like the rising tide, and all nine peaks bowed in reverence. No congestion of a lone tyrant, no wasteful squawk of universal broadcasting, and no unyielding deadlock of stubborn contenders. By dividing the peaks into intersecting lattices and answering contention with courteous yielding, the Primordial Bell sang through the ages.

— By now you’ve probably recognized it: the mountain sanctuary and the iron rule forbidding concurrent chimes represent the shared critical section (Critical Section) requiring mutually exclusive access; the aging elder of Tian-Shu Peak represents a centralized lock manager (Centralized Lock Manager) with its inevitable single point of failure and bottleneck; the universal broadcast to all eight peaks represents the classical Lamport or Ricart-Agrawala algorithms with their linear $O(N)$ message explosion; and Elder Maekawa’s lattice of intersecting quorums coupled with courteous yielding to avert deadlock is one of the most celebrated milestones in distributed systems theory: Maekawa’s Algorithm.

What it is

Maekawa’s Algorithm is a distributed mutual exclusion protocol published in 1985 by Mamoru Maekawa in the ACM Transactions on Computer Systems (TOCS), titled “A $\sqrt{N}$ Algorithm for Mutual Exclusion in Decentralized Systems.” It pioneered the use of quorum-based subsets to achieve distributed synchronization without a central coordinator.

Prior to Maekawa’s work, permission-based distributed mutual exclusion algorithms (such as Lamport’s Bakery / Logical Clocks and the Ricart-Agrawala algorithm) relied on universal consensus: a node wishing to enter a critical section had to broadcast a request to all other $N-1$ nodes and await unanimous approval. This imposed a message complexity of $2(N-1)$ per critical section invocation, scaling linearly ($O(N)$) and rendering the system vulnerable to any single node’s slowdown or crash.

Maekawa made a profound mathematical breakthrough: to guarantee mutual exclusion, unanimous consent is entirely unnecessary; one only requires that any two candidates’ permission sets share at least one common arbiter.

1. Quorum Construction (Voting Sets):
   • The $N$ distributed nodes are logically arranged in a $\sqrt{N} \times \sqrt{N}$ matrix (or mapped onto finite projective geometries like the Fano Plane).
   • Each node $i$ is assigned a voting set $S_i$. In the grid construction, $S_i$ consists of all nodes in node $i$’s row and all nodes in its column, resulting in a quorum size of $K \approx \sqrt{N}$ (more precisely $2\sqrt{N}-1$; symmetric projective geometry can reduce this to $\approx \sqrt{N}$).
   • The Intersection Property: For any two distinct nodes $i$ and $j$, $S_i \cap S_j \neq \emptyset$. Any pair of candidate quorums is guaranteed to overlap at one or more arbiter nodes.
2. Vote Exclusivity and Safety Guarantee:
   • Each node possesses exactly one vote and can grant it to only one contender at any given time.
   • When node $i$ seeks entry to the critical section, it sends Request messages only to members of its own subset $S_i$ and waits until all members have granted their vote.
   • Because every pair of voting sets shares at least one arbiter, that arbiter cannot grant its single vote to two contenders concurrently. Thus, no two nodes can simultaneously hold all votes from their respective quorums. Mutual exclusion (Safety) is mathematically guaranteed.
3. Deadlock Prevention via Preemptive Messages: Because nodes petition only local subsets, concurrent requests can easily produce circular wait conditions (e.g., node A holds vote 1 and waits for 2; node B holds vote 2 and waits for 3; node C holds vote 3 and waits for 1). Maekawa resolved this by combining Lamport logical timestamps with three auxiliary control messages:
   • Inquire: When an arbiter has already granted its vote to node A, and subsequently receives a request from node B with an earlier timestamp (higher priority), the arbiter sends an Inquire message to A, asking whether it has already entered the critical section.
   • Failed: When a candidate node receives a rejection indicating its request was preempted or queued behind a higher-priority rival, it records a failure state, knowing it cannot currently assemble a full quorum.
   • Yield: When node A receives an Inquire and realizes it has not yet secured all required votes (specifically if it has received a Failed message from elsewhere), it must yield by sending a Yield message back to the arbiter, relinquishing the vote. The arbiter immediately reassigns the vote to the higher-priority node B. Once B exits and sends Release, the arbiter returns the vote to A.

Why it matters

Maekawa’s Algorithm occupies a foundational position in distributed systems architecture:

1. Sub-linear Communication Complexity ($O(N)$ to $O(\sqrt{N})$): In a thousand-node cluster, Ricart-Agrawala demands approximately 2,000 network messages per lock acquisition; Maekawa’s algorithm slashes this to $3\sqrt{N} \sim 5\sqrt{N}$, requiring merely dozens of messages. It proved that decentralized mutual exclusion does not demand global broadcast, enabling synchronization to scale sub-linearly.

2. Theoretical Genesis of Quorum Systems: Maekawa established the foundational paradigm of using overlapping quorums to balance consistency and availability. The core premise—that intersecting subsets guarantee invariant safety without full cluster coordination—directly inspired grid quorums, hierarchical quorums, and the read/write quorum mechanics powering modern distributed databases such as Apache Cassandra and Amazon Dynamo.

3. Decentralized Deadlock Resolution Philosophy: While many distributed systems resort to centralized deadlock detectors or ungraceful timeouts, Maekawa’s algorithm offers an elegant, decentralized protocol of voluntary deference. Through priority-based inquiries (Inquire) and introspective concessions (Yield), autonomous peers untangle complex circular deadlocks using only local timestamp evaluations and cooperative contracts. This principle of gracefully yielding uncommitted locks remains a gold standard in modern high-concurrency distributed resource scheduling.

Metaphor mapping

• Nine sword pavilions in Zhongnan Mountains → Autonomous peer nodes in a distributed system (Distributed Nodes)
• Central cavern sanctuary and the Great Primordial Bell → Shared resource or exclusive critical section (Critical Section)
• Ancient law forbidding simultaneous bell strikes → Mutual exclusion safety invariant (Mutual Exclusion / Safety Invariant)
• Grand Elder of Tian-Shu Peak and the winter avalanche → Centralized lock coordinator with its single point of failure and bottleneck (Centralized Lock Manager / SPOF)
• Universal dispatch of hawks to all eight pavilions → Full broadcast consensus in Lamport / Ricart-Agrawala ($O(N)$ message overhead)
• Three-by-three lattice and five-pavilion alliances → Maekawa’s grid-based quorum voting sets (Grid Quorums / Voting Sets $S_i$, size $K \approx \sqrt{N}$)
• Any two alliances intersecting at a crossing pavilion → Pairwise quorum intersection property ($\forall i, j: S_i \cap S_j \neq \emptyset$)
• Keeper of the Seal lending only one bronze tally at a time → Exclusive single-vote rule per node (Vote Locking)
• Three pavilions holding partial tallies in a stalemate → Circular wait deadlock in uncoordinated quorum acquisition (Deadlock via Circular Wait)
• Water-clock timestamp carved on parchment → Monotonic logical clocks establishing global priority (Lamport Timestamps)
• Golden arrow asking if the petitioner has entered the sanctuary → Preemptive status inquiry sent by an arbiter (Inquire message)
• Letter of refusal received from a contested peak → Notification of contested vote preventing immediate quorum (Failed message)
• Junior petitioner bowing and returning the bronze tally → Cooperative concession releasing an uncommitted vote (Yield message)
• Returning all tallies after the bell strike ends → Final broadcast releasing votes upon critical section exit (Release message)