High above the misty peaks of the Kunlun Mountains, nine Daoist sword pavilions stood nestled among the precipices, their disciples cultivating celestial arts across generations.

Though each pavilion practiced its own sword discipline, there existed only a single Flying Crucible in the mortal realm capable of refining heavenly elixirs. Suspended in a void formation at the mountain center, the crucible surged with primordial samadhi fire. The laws governing it were absolute: only one pavilion could ignite the crucible at any single moment. Should two pavilions inject their spiritual qi simultaneously, the conflicting astral energies would instantly shatter the furnace, triggering a catastrophic avalanche that would obliterate the mountain range.

In early eras, whenever a pavilion wished to borrow the crucible, its disciples were forced to dispatch messenger flying swords to every other pavilion. Before igniting the flame, the petitioner had to wait for unanimous written permits from all eight peaks, comparing intricate water-clock timestamps carved into parchment slips. Swords blotted out the sun as dozens crisscrossed the ravines. If two peaks happened to petition at the identical moment, they had to exchange further letters to establish precedence. Oftentimes, the crucible sat cold and idle for hours while missives spun aimlessly in blinding mountain blizzards.

Witnessing this exhaustion, a wandering sword immortal cast an ethereal talisman from celestial ore and suspended it above the peaks: the Gilded Tally.

The immortal decreed two foundational laws:

First, possession of the tally grants command of the flame. The world held but one crucible, and the void held but one Gilded Tally. Whichever pavilion held the tally possessed undisputed sovereign right to enter the crucible without uttering a single word to its brethren. When their batch was completed, if no other peak had requested the tally, it remained quietly on their stone dais. Should that same peak wish to refine another batch the following morning, they simply began anew—costing not a single flying sword across the skies.

Second, broadcast the call, but let the tally carry the scroll. If a peak required the crucible while the tally was elsewhere, they had no need to wander the valleys inquiring where it lay. They simply carved their pavilion crest and their cumulative petition count onto eight swift spiritual arrows, launching them simultaneously to every other peak.

Outside each pavilion stood a stone stele, quietly recording the highest arrow sequence number ever received from each fellow peak. Whenever a new arrow arrived, if its sequence exceeded the stele’s old carving, the stone was swept clean and engraved with the fresh number.

The current keeper of the Gilded Tally bore a special burden. Upon the reverse side of the golden talisman lay two mystical formations: a nine-grid jade matrix recording the exact count of completed elixir sessions granted to each peak throughout history, and a swirling mist groove acting as a living FIFO scroll of awaiting petitioners.

During a harsh winter solstice, the spiritual fires of the Third Pavilion waned, urgently requiring the crucible’s flame. But the Gilded Tally rested peacefully upon the quiet desk of the First Pavilion.

The head disciple of the Third Pavilion drew eight cloud-etched arrows, inscribed them with their seventh cumulative petition count, and loosed them into the storm. In a single breath, the arrows struck the remaining eight peaks. The Second, Fourth, through Ninth Pavilions noted the arrow, incremented their stone steles from six to seven for the Third Pavilion, and shut their gates, possessing no tally to bestow.

When the arrow reached the First Pavilion, its master had just retrieved their glowing celestial pill from the furnace.

Holding the Gilded Tally, the master prepared to set it down when the hovering arrow caught his eye, bearing the inscription: The Third Pavilion petitions for its seventh batch.

The master flipped the talisman and inspected its reverse jade matrix. There, the historical tally for the Third Pavilion remained at six.

“Seven is strictly greater than six,” murmured the master. “This is no stale echo of an old petition, but a fresh prayer for the flame.”

Inspecting the mist groove, the master saw no earlier petitioners waiting in queue, and promptly inscribed the crest of the Third Pavilion into the tally’s internal scroll. Having finished his own refinement, he uttered an incantation. The Gilded Tally uncoiled into a golden ray of light, streaking dozens of miles across the snowy chasm, settling directly upon the desk of the Third Pavilion.

Not a single return sword was dispatched by the First Pavilion; not a single extraneous word was spoken by the other seven peaks.

The sky remained quiet, serene, and unbroken.

By now you’ve probably recognized it: this is the classic distributed mutual exclusion protocol—the Suzuki-Kasami Algorithm.

What it is

The Suzuki-Kasami Algorithm (introduced by Ichiro Suzuki and Toshimi Kasami in 1985) is a seminal token-based broadcast algorithm for distributed mutual exclusion.

In decentralized systems without a coordinator, algorithms for mutual exclusion typically fall into two fundamental paradigms:

1. Permission-based: Such as Ricart-Agrawala or Maekawa’s algorithm, where a candidate node must gather explicit permissions from peer nodes or quorum intersections before entering a critical section ($O(N)$ or $O(\sqrt{N})$ network overhead).
2. Token-based: A single unique logical token circulates through the system. Only the node holding the token is permitted to execute inside the critical section.

Suzuki-Kasami is the gold standard of token-based protocols on broadcast networks:

• Broadcast Request: When a non-holder node wishes to enter the critical section, it increments its local monotonic request counter and broadcasts a REQUEST(node_id, seq) message to all other $N-1$ nodes.
• Local Request Array ($RN$): Every node maintains an array $RN[1..N]$, tracking the highest sequence number observed from every other node. Upon receipt of a request, it updates: $RN[j] = \max(RN[j], seq)$.
• Token Internal State: The token is not an opaque boolean flag; it carries two critical data structures:
  1. $LN[1..N]$: An array recording the request sequence number of node $j$’s most recently executed critical section entry.
  2. $Q$: A FIFO queue containing IDs of nodes waiting for the token.
• Token Transfer Logic: Upon leaving the critical section, the token holder sets $LN[i] = RN[i]$. It then iterates over all nodes $j$: if $RN[j] == LN[j] + 1$ and $j \notin Q$, node $j$ is appended to $Q$. Finally, if $Q$ is non-empty, the token (along with $LN$ and $Q$) is transmitted point-to-point directly to the node at the head of $Q$.

Why it matters

1. Optimal $N$ Message Bound: Compared to permission-based algorithms like Ricart-Agrawala which require $2(N-1)$ messages per critical section entry (requests to all peers plus replies from all peers), Suzuki-Kasami slashes this to at most $N$ messages ($N-1$ broadcast requests plus $1$ point-to-point token transfer). Furthermore, if a node makes multiple consecutive requests while still retaining the token, the synchronization message cost is 0.

2. Differentiating Fresh Petitions from Stale Network Delays: In asynchronous networks, old messages can be delayed arbitrarily. Suzuki-Kasami solves message replay vulnerability through algebraic comparison between the token’s $LN$ array and the node’s local $RN$ array ($RN[j] == LN[j] + 1$). If $LN[j] \ge RN[j]$, the holder provably knows the request has already been satisfied and safely ignores it, preventing duplicate executions and deadlocks.

3. State-Carrying Capability Model: Unlike naïve Token Ring protocols where an idle token cycles continuously through nodes wasting network bandwidth, Suzuki-Kasami moves the token strictly on-demand. By embedding the waiting queue $Q$ and execution log $LN$ directly inside the capability token, it pioneered the pattern of state-carrying distributed tokens, which heavily influences modern lock migration, distributed lease handoffs, and concurrent task scheduling systems.

Metaphor mapping

• Nine Daoist sword pavilions in Kunlun → Autonomous nodes in a distributed system (Distributed Nodes)
• Flying Crucible in the central void → Shared exclusive resource / critical section (Critical Section)
• Catastrophic explosion rule if two pavilions ignite → Mutual exclusion safety invariant (Mutual Exclusion / Safety Invariant)
• Ethereal talisman “Gilded Tally” → Exclusive privilege token (Privilege Token)
• Stone steles outside pavilions recording arrow numbers → Local request array tracking highest seen sequence numbers ($RN$ Array)
• Eight spiritual arrows broadcast to all peaks → Broadcast request messages sent to all other nodes ($N-1$ Request Broadcast)
• Nine-grid jade matrix on the reverse of the tally → Array within token recording sequence numbers of served requests ($LN$ Array)
• Swirling mist groove inside the tally → FIFO queue of waiting nodes maintained within the token (Token Queue $Q$)
• Checking “seven is strictly greater than six” → Evaluating $RN[j] == LN[j] + 1$ to verify true request freshness
• Golden ray flying directly to the Third Pavilion → Unicast point-to-point transfer of the token (Point-to-Point Token Transfer)
• Reusing the tally the next morning with zero arrows → Zero message overhead for consecutive entries by the same node