Giving one process authority makes coordination easy. Then that process fails, and the system has to coordinate before it has anyone left to coordinate it.
"Explore distributed mutual exclusion, Ricart-Agrawala, Bully, and Ring leader election algorithms, and discover how distributed systems coordinate when authority can fail."
Two processes want the same resource.
Only one of them may use it at a time.
On one machine, this is a familiar problem. We reach for a lock, semaphore, monitor, or some other mutual-exclusion primitive.
One process enters the ✨critical section✨
Everyone else waits.
It leaves.
The next process enters.
The operating system has shared memory and a central place from which to enforce the rule, so the mechanism feels almost mundane.
Then the processes move onto different machines.
There is no shared memory.
There may be no operating-system kernel overseeing all of them.
The machines communicate through an asynchronous, failure-prone network.
Our lock has nowhere obvious to live.
And yet the requirement has not changed:
At most one process may use the shared resource at a time.
That is the distributed mutual-exclusion problem.
The lock did not become conceptually difficult.
Ownership of the lock did.
Mutual Exclusion Needs More Than “One at a Time”
Before choosing an algorithm, it helps to be precise about what success means.
A mutual-exclusion mechanism needs safeness.
Two processes must never be inside the critical section simultaneously.
It needs liveness.
A process requesting access should not wait forever while the system is otherwise able to make progress.
There is also ordering , a fairness concern.
If several processes request the resource, how should those requests be prioritized?
And then there is efficiency.
How many messages does entry require?
How long must a process wait?
How much communication happens between one process leaving and the next entering?
These requirements pull the design in different directions.
The safest solution might communicate too much.
The simplest one might fail badly.
The most decentralized one might require everybody to participate in every decision.
So we begin with the design that makes the fewest changes to our old mental model.
We invent a lock manager.
Give One Process the Key
Choose one process as the central server.
Anyone who wants the resource sends it a request.
If the critical section is free, the coordinator grants permission.
If somebody else is using it, the request waits.
When the holder exits the critical section, it sends a release message.
Simple.
The coordinator becomes the one authority capable of saying:
You may enter.
That immediately gives us safeness.
There is only one grantor.
If the coordinator hands the resource to one process at a time, competing processes cannot independently decide that they own it.
Liveness can also be satisfied while the coordinator and network remain healthy.
And the communication cost is pleasantly small:
- request permission,
- receive permission,
- release the resource.
Two messages to acquire it and one to release it.
The whole distributed problem has been reduced to asking one machine nicely.
This is attractive because centralized authority removes ambiguity.
There is one queue.
One decision-maker.
One version of who owns the critical section.
For a moment, coordination feels local again.
Then the coordinator disappears.
The Coordinator Became Part of the Critical Resource
The shared resource may be perfectly healthy.
Every client process may be healthy.
The network between most machines may be healthy.
But if the coordinator fails, nobody can obtain permission.
We solved mutual exclusion by creating a single point of failure.
That is the obvious problem.
There is a subtler one too.
Ordering is not automatically fair simply because requests reached one central server.
Network delay can reorder what the coordinator sees.
Process A may request access before Process B, yet B’s request may reach the coordinator first.
The central server knows the order in which messages arrived.
That is not necessarily the same thing as the order in which requests were originally made.
So even our beautifully simple authority has inherited the network’s imperfect view of reality.
And there is latency.
Every entry into the critical section requires at least a network round trip.
The coordinator also becomes a bottleneck as more processes compete for the resource.
The mechanism works.
The problem is that we have placed a large amount of responsibility onto one process:
Safety, Progress, Arbitration, and Availability.
Perhaps the obvious repair is to stop trusting one coordinator.
Fine. Have Several Coordinators
Instead of one authority, use several.
Replicate the resource or the coordinators responsible for granting access.
Now a process requesting entry sends messages to multiple coordinators and waits for a majority vote.
If enough coordinators grant permission, it proceeds.
This removes the uncomfortable dependency on one machine.
One coordinator can fail without necessarily stopping the system.
That sounds like progress.
And it is.
But distributing authority does not remove contention.
It redistributes it.
Imagine two processes trying to enter simultaneously.
Each collects some votes.
Neither collects enough.
Now both back off.
Then both retry.
Under high contention, utilization can become disappointingly low because permission is spread across multiple authorities that competing requesters can partially acquire.
The single coordinator was fragile because authority lived in exactly one place.
The decentralized version is harder because authority now has to be assembled from several places.
So perhaps permission itself is the problem.
What if ownership were represented by one physical idea instead?
Pass the Token
Create a logical ring of processes.
Place one token in that ring.
The rule becomes wonderfully clean:
Whoever has the token may enter the critical section.
No voting.
No central permission server.
No ambiguity about ownership.
The token itself is permission.
When a process finishes, the token continues around the ring.
Safeness becomes almost tangible.
As long as exactly one token exists, only one process can possess it.
Liveness follows if the token continues circulating and processes remain reachable.
This is controlled coordination through ownership rather than repeated negotiation.
It is elegant.
It also has opinions about fairness.
Suppose Process 5 requests the resource first, but the token is currently moving toward Process 2.
Process 2 may receive access first simply because of its position in the ring.
The ordering follows ring order , not necessarily request order.
And the worst-case waiting time grows with the number of processes.
With N processes, the token may need to travel through much of the ring before reaching the requester.
The token removed a coordinator.
It did not remove coordination cost.
It moved that cost into token movement and topology.
And of course the token itself has now become something rather important not to lose.
Distributed systems have a talent for turning whatever represents authority into the next thing we need to protect.
What If Nobody Owns the Decision?
There is another possibility.
No central coordinator.
No unique token.
Every process participates directly.
When Process P wants to enter the critical section, it sends a request to the other processes.
Those processes decide whether P should be allowed to proceed.
Only after the required replies arrive may P enter.
Now control is fully distributed.
Lamport showed how logical timestamps and a total ordering of events could be used to construct distributed mutual exclusion, using mutual exclusion as an illustration of what event ordering makes possible.
Ricart and Agrawala later refined this style of algorithm.
A process sends a timestamped REQUEST to every other process.
Each receiver compares the request with its own competing request.
If the requester has priority, it replies immediately.
Otherwise, it postpones its reply until after leaving its own critical section.
The requesting process enters only after every other process has granted permission.
The algorithm uses: 2(N - 1)
Messages per critical-section entry:
N - 1 REQUEST Messages + N - 1 REPLY Messages
Ricart and Agrawala’s original algorithm was explicitly designed for machines that communicate only by messages and do not share memory, and its 2(N - 1) message cost was a central result.
This feels like distributed coordination in its purest form.
Nobody owns the lock.
Agreement among the participants creates the lock.
Decentralization Sends Everyone the Invoice
The fully distributed approach satisfies some things beautifully.
Safeness can be maintained.
Liveness can be maintained under its assumptions.
Timestamp-based priority can provide ordering.
There is no central server through which every request must pass.
Excellent.
Now count the dependencies.
Before one process can enter the critical section, it needs replies from all the other participating processes.
Every process is part of the permission mechanism.
Which means every process is also somewhere the protocol can get stuck.
If one participant fails and its reply is required, what happens?
The requester waits.
A system that removed one point of failure can end up with N points whose failure matters.
And every process handles requests from all the others.
We removed one bottleneck and produced many smaller ones.
This is one of those distributed-systems moments that feels unfair until the underlying constraint becomes visible.
Coordination work does not vanish when the coordinator disappears.
Somebody still has to decide who goes first.
Somebody still has to maintain safeness.
Somebody still has to ensure progress.
Somebody still has to answer to The Origami Software Engineer.
If there is no designated authority, that responsibility falls onto the participants collectively.
Decentralization changes who pays for coordination.
It does not make coordination free.
Then We Discover That We Actually Wanted a Coordinator
Here is where the story bends back on itself.
Many distributed algorithms genuinely benefit from one process acting as a coordinator or initiator.
Maybe it assigns work.
Maybe it maintains some shared responsibility.
Maybe it orchestrates the next phase of an algorithm.
Centralized authority was not foolish.
Sometimes it is exactly what the system wants.
The problem was assuming that the coordinator would exist forever.
Suppose the coordinator crashes.
The surviving processes can continue computing.
But they now face a peculiar question:
Who is the coordinator?
We cannot ask the old coordinator.
That is rather the point.
We cannot simply let every process independently appoint itself either, because then we have traded no coordinator for several competing coordinators.
The surviving processes have to collectively agree on one new coordinator.
That is leader election.
And the irony is excellent.
The system needs a leader to coordinate activity.
But when the leader fails, there is no leader available to coordinate the selection of the next leader.
So the participants need an algorithm that coordinates them before coordination authority exists.
Hence the title.
First, Give Everyone a Rank
Leader-election algorithms usually need some structure.
Assume every process has a unique identifier.
It could be related to a network address or simply be some unique number.
Also assume that a process does not initially know with certainty which other processes are alive and which have failed.
The objective is not merely:
Somebody becomes leader.
That would be easy.
Every process could choose itself and go home happy.
The real requirement is:
Once the election completes, the surviving processes agree on the same coordinator.
That agreement is the important part.
The algorithms differ mainly in how they discover the surviving participants and determine which one should obtain authority.
One approach is beautifully unsubtle.
It is literally called the Bully algorithm.
The Bully Algorithm Asks, “Anyone Stronger?”
Suppose Process P notices that the current coordinator is no longer responding.
P starts an election.
It sends an ELECTION message to every process with a higher identifier.
Then it waits.
If nobody higher replies, P has learned something useful:
Among the processes I can reach, nobody with a higher number is alive.
So P wins.
It becomes the coordinator and announces that fact.
But suppose a higher-numbered process replies with OK.
P steps aside.
The higher process now takes responsibility for continuing the election, asking processes ranked above it whether any of them are alive.
The questioning climbs upward.
Eventually the highest-numbered surviving process encounters silence above it.
That process wins.
This is why the algorithm feels like a bully.
A higher-ranked process can effectively tell a lower-ranked candidate:
Thanks. I’ll take it from here.
Garcia-Molina’s original work on elections framed leader selection as the first step in reorganizing a distributed system after failures so that the surviving nodes could continue useful work.
The algorithm is not discovering who is the wisest process.
The unique numbers give everyone a deterministic rule for answering:
If several candidates survive, which one wins?
Without such a rule, multiple survivors could make equally reasonable but incompatible choices.
Recovery Makes the Bully Even More Opinionated
Now suppose the old high-numbered process had crashed.
A lower process became coordinator.
Everything has been working.
Then the high-numbered process recovers.
The Bully algorithm does not politely say:
I see you already filled the position. Carry on.
It starts an election.
If it is now the highest-numbered running process,
it becomes coordinator again.
The recovered process may need to reconstruct relevant state and prepare to continue the coordinator role before announcing itself with a COORDINATOR message.
This behaviour follows directly from the algorithm’s invariant.
The chosen coordinator is not merely some live process.
It is the highest-numbered live process.
That deterministic rule makes convergence possible.
It also means recovery itself can trigger another leadership transition.
The leader is not a permanent identity.
It is a role derived from the current membership state.
Or Let the Ring Discover Who Survived
The ring election algorithm takes a different route.
Arrange processes in a logical ring.
Each process knows its successor.
When Process P detects that the coordinator is no longer responding, it creates an ELECTION message containing its own identifier and sends it to the next live process in the ring.
That process adds its own identifier.
Then forwards the message.
And so on.
If a successor has failed, the algorithm skips over it and continues to the next reachable member.
Eventually the message returns to the process that initiated the election.
Now the election message contains the identities of the processes encountered around the ring.
The highest identifier becomes the new coordinator.
Then a COORDINATOR message travels around the ring so everyone learns the result.
When that announcement returns to its origin, the election is complete.
Same problem.
Different structure.
The Bully algorithm searches upward through process identifiers.
The ring algorithm lets information circulate through topology until the group has accumulated enough knowledge to make one deterministic choice.
Neither algorithm makes leadership appear by magic.
Both turn distributed uncertainty about who is alive into shared knowledge about who should lead.
The Coordinator Was Never the Real Problem
Look back at the progression.
We needed mutual exclusion.
We gave one server authority.
Simple.
Then the single point of failure became uncomfortable.
We distributed the authority among several coordinators.
Now permission required majority agreement.
We represented authority with a token.
Now ownership depended on token circulation.
We removed explicit ownership entirely and asked every process.
Now every process participated in every permission decision.
We admitted that some distributed activities genuinely benefit from a coordinator.
So when that coordinator failed, the processes had to elect another.
Every design moved authority somewhere.
A server.
A majority.
A token.
A total order of distributed requests.
An elected leader.
The interesting lesson is not that centralized coordination is bad and decentralized coordination is good.
That distinction is too easy.
The deeper question is:
Where does the authority to make one exclusive decision come from?
If one process holds it, failure of that process matters.
If several processes share it, agreement matters.
If a token represents it, the token’s location matters.
If every process participates, communication and participant failures matter.
If leadership is temporary, election matters.
Authority never disappeared.
It only changed representation.
Coordination Is the Art of Agreeing Who Gets to Decide
Distributed systems are made of independent processes.
Independence is useful.
It is also exactly why coordination has to exist.
Two processes cannot safely enter the same exclusive critical section just because both independently believe it is free.
Two partitions cannot safely invent different coordinators if the rest of the system requires one authority.
A failed leader cannot nominate its successor after it has failed.
So the system needs rules that turn independent local observations into one compatible decision.
Sometimes those rules are centralized.
Sometimes they are distributed.
Sometimes they travel around a ring.
Sometimes they are encoded in timestamps.
Sometimes they choose the highest surviving process and call it a day.
The algorithm changes.
The constraint does not.
Whenever several independent machines must behave as though one decision was made, something has to coordinate that decision.
And when the thing doing the coordinating disappears, the surviving machines have to temporarily become their own coordinators long enough to decide who should stop being one.
That’s not failure.
That’s evolution.
The “I liked this” Starter Pack:
Don’t let your fingers get lazy now.
- Like : It tells me this was worth writing.
- A Comment: Tell me your thoughts, your favorite snack, or a better title for this blog.
- Boost it: Especially with that one developer who definitely needs this.
Thanks for being here. It genuinely helps more than you know!
— Aaroophan Varatharajan
Find me elsewhere:
- Professional stuff: linkedin.com/in/Aaroophan
- Code stuff: github.com/Aaroophan
- UI stuff: aaroophan.dev/Aaroophan
- Life stuff: instagram.com/Aaroophan
Top comments (0)