Consensus looks almost trivial when everyone behaves and every message arrives on time. The interesting part begins when we remove those assumptions one by one.
"Explore reliable networks, crash failures, Byzantine faults, synchrony, and the FLP impossibility result to understand what consensus algorithms really assume."
Several processes need to make one decision.
Proceed or abort.
Commit or roll back.
Who enters the critical section.
Which message comes first.
Whether a spacecraft lands or gives up the attempt.
Different systems, same uncomfortable requirement:
Independent processes must eventually behave as though one decision was made.
This is ✨consensus✨
The word sounds almost social. Everyone proposes something, the group talks, and eventually everybody agrees.
In distributed systems, agreement has a stronger flavour.
It is not enough for Process A to know the answer.
Process B must know it too.
And if their future behaviour depends on the decision, they need compatible knowledge of that decision.
That gives us a deceptively simple problem:
Give each process a proposed value.
Exchange those values.
Choose one.
Done.
Under the right assumptions, it really is almost that easy.
So naturally, the useful story begins by taking those assumptions away.
First, Let Everyone Behave
Assume there are N processes.
None can fail.
Communication is reliable.
Every process reliably multicasts its proposed value to everyone else.
Then each process waits until it has collected all N proposals.
Suppose the proposed values are:
P1 → proceed
P2 → proceed
P3 → abort
Every process sees the same set: { proceed, proceed, abort }
Apply the same deterministic function everywhere: majority(proceed, proceed, abort)
and everybody chooses: Proceed
We could use another deterministic function too.
Minimum.
Maximum.
Some agreed rule appropriate to the values.
The exact function is less interesting than the reason this works.
Everyone receives the same information.
Everyone applies the same rule.
So everyone reaches the same answer.
Consensus needs three important properties.
- Termination: every correct process eventually decides.
- Agreement: all correct processes decide the same value.
- Integrity: if all correct processes propose the same value, the decision respects that value.
Our easy algorithm gets these properties because the environment is doing an extraordinary amount of work for us.
Nobody crashes.
Messages arrive reliably.
Nobody lies.
Nobody waits forever.
Under those conditions, consensus has excellent vibes.
Then we remove one assumption.
Two Armies Discover the Last Acknowledgement Problem
Imagine two blue armies separated by territory controlled by their enemy.
They can defeat the enemy only if they attack together.
One army attacking alone loses.
So General A sends a messenger to General B:
Attack at dawn.
The messenger arrives.
General B agrees and sends a reply.
Agreed. Dawn.
Excellent.
Except B now has a concern.
B knows the original message arrived.
But B does not know whether the acknowledgement reached A.
If it did not, A may believe B never agreed and refuse to attack.
So A sends another acknowledgement:
I received your reply. We are ready.
That arrives.
Surely The Origami Software Engineer is done now.
Not quite.
A knows B knows about the attack.
B knows A received B’s response.
But B does not know whether A’s latest acknowledgement reached B
well, B received it, obviously.
The problem is now A’s uncertainty about whether B knows that A knows.
So another confirmation helps.
Then that confirmation itself may be lost.
So perhaps we acknowledge the acknowledgement of the acknowledgement.
And now we can all see where this cursed little staircase goes.
There is always a last message.
If the communication channel can lose that last message, one side cannot know for certain whether the other side received it.
No finite chain of acknowledgements removes that uncertainty.
The problem is not that the generals have not exchanged enough messages.
The problem is that the communication channel cannot guarantee the piece of knowledge their coordinated action requires.
Lamport later described the related two-generals setting as two parties trying to reach common agreement through messengers that might never arrive.
This is the first major lesson:
Correct processes are not enough.
Two completely honest participants can still fail to reach guaranteed agreement when communication itself is unreliable.
Communication Failure Changes What Silence Means
This sounds familiar because distributed systems keep making silence ambiguous.
Suppose Process P is waiting for Process Q.
Nothing arrives.
What happened?
Maybe Q never sent anything.
Maybe Q sent the message and the network lost it.
Maybe Q is temporarily unreachable.
Maybe the message is delayed.
Maybe Q crashed.
From P’s point of view, these very different realities can look identical: ...
Nothing.
That is a brutal information problem.
Consensus algorithms need to make decisions based on what processes know.
Failures remove knowledge.
Unreliable communication removes knowledge.
Delays make missing knowledge difficult to interpret.
The system is not merely trying to calculate a value.
It is trying to calculate a value while never having a perfect view of the other participants.
So let us make life easier again.
Assume communication has known timing bounds.
Now silence can mean something.
A Synchronous System Lets Timeouts Test Reality
In a synchronous system , we assume useful upper bounds exist.
A process cannot take arbitrarily long to perform an operation.
A message cannot take arbitrarily long to arrive.
That means a timeout can carry information.
If a correct process should respond within at most T , and nothing arrives after T , another process can reasonably conclude that something failed.
This is a remarkably powerful assumption.
Now suppose up to f processes may crash.
Processes can exchange values in rounds.
Each process starts with its proposed value.
During each round, it sends newly learned values to the others.
Receivers add those values to what they already know.
After: f + 1
rounds, each correct process applies the same decision function, such as choosing the minimum value it has received.
Why f + 1?
Because at most f processes can crash.
A process might fail after forwarding a value to only some participants.
The next round lets those participants propagate that value farther.
Another process might then crash.
Another round propagates again.
With at most f crashes, f + 1 rounds ensure there is eventually a round in which no new crash can keep a value permanently confined to only part of the surviving group.
The algorithm is not magically overcoming failure.
It is using bounded time and bounded failures as structure.
The design works because we can say things like:
That round is over.
That process should have replied by now.
Only f processes are allowed to fail.
Take those statements away and the algorithm starts losing its footing.
But before we remove timing, there is another assumption worth ruining.
So far, a failed process merely stops.
What if it keeps talking?
Crash Failure Is Almost Polite
A crashed process is inconvenient.
It can fail to send a value.
It can disappear midway through a round.
It can leave other participants waiting until their timeout expires.
But once it has crashed, it is at least no longer inventing new stories.
There is a much nastier failure mode.
A process can remain active while behaving arbitrarily.
It may send incorrect values.
It may send contradictory values.
It may cooperate with other faulty processes.
It may tell P2:
The commander said attack.
and tell P3:
The commander said retreat.
This is a Byzantine failure.
Now the problem changes fundamentally.
With a crash, the question is:
Did this process participate?
With Byzantine behavior, the question becomes:
Can I trust what this process told me about its participation?
Silence was difficult.
Contradictory speech is worse.
One Commander, Three Generals, Two Realities
Consider the Byzantine Generals problem.
There is a distinguished process: the commander.
It proposes a value.
The lieutenants must agree on what to do.
The requirements are similar to ordinary consensus:
- Termination: every correct lieutenant eventually decides.
- Agreement: all correct lieutenants decide the same value.
- Integrity: if the commander is correct, the correct lieutenants decide the value the commander proposed.
Now imagine only three generals:
P1
Commander
/ \
/ \
P2 -------- P3
Suppose P1 is faulty.
It tells P2: Attack
and P3: Repeat
P2 and P3 exchange what they heard.
P2 sees:
- Commander told me attack.
- P3 says commander told them retreat.
P3 sees:
- Commander told me retreat.
- P2 says commander told them attack.
Who is lying?
The commander?
The other lieutenant?
Neither correct process has enough information to distinguish the possibilities.
And that indistinguishability matters.
A correct lieutenant cannot simply trust whichever story feels nicer.
The system needs enough independent participants for correct processes to outvote the contradictory realities introduced by faulty ones.
Four Generals Finally Give the Truth Somewhere to Stand
Add another lieutenant.
Now imagine four generals with at most one Byzantine failure.
The commander sends its value to each lieutenant.
Then every lieutenant tells the others what value it received from the commander.
A correct lieutenant now collects several reports.
If one process lies, the correct participants still have enough consistent information to make the lie the minority.
For unsigned messages in this synchronous Byzantine setting, tolerating f arbitrary failures requires at least: 3f + 1 processes.
So: f = 1 requires: 4 Processes
Lamport, Shostak, and Pease’s classic formulation develops the general 3f + 1 structure for agreement in the presence of Byzantine participants.
That number is not random redundancy.
It exists because Byzantine participants can create different apparent realities for different correct processes.
The correct participants therefore need enough overlap that incompatible stories cannot each persuade separate groups.
This is a very different use of replication.
We are not keeping extra machines merely because hardware might die.
We need extra independent participants so truth can survive misbehavior.
Agreement Gets Expensive Because Knowledge Has to Be Cross-Checked
Notice how the communication pattern changed.
When everybody was correct, each process could simply tell everyone its value.
Easy.
When processes could crash, values had to propagate across several rounds so a partially forwarded value would not disappear with the process that carried it.
When processes can behave Byzantine, a process cannot merely ask:
What value did you receive?
It also needs information equivalent to:
What did everyone else claim to receive?
Now participants cross-check one another.
Messages are not merely carrying proposals.
They are carrying claims about other claims.
This is the cost of removing trust.
The process cannot inspect another process’s internal state.
It only sees messages.
So every Byzantine-tolerant algorithm has to create enough communication structure that correct processes can derive one compatible decision despite potentially incompatible reports.
This is why Byzantine agreement feels dramatically harder than crash-tolerant agreement.
A crashed process removes information.
A Byzantine process can manufacture information.
The first creates holes.
The second creates alternate realities.
So Far, Time Has Quietly Been Saving Us
There is another assumption hiding inside all of this.
Rounds.
Round 1.
Wait.
Round 2.
Wait.
After a bounded period, conclude that a missing message is not coming.
Even the Byzantine algorithm can use timeouts: if a process fails to send the expected value before the known deadline, substitute some default such as null and continue.
That sounds like a minor implementation detail.
It is actually carrying enormous theoretical weight.
A timeout lets us transform:
I have not heard from P.
into:
P has failed to respond within the allowed time.
Without a timing bound, those are not equivalent.
So now remove synchrony.
Messages are still reliable.
Correctly sent messages will eventually arrive.
Processes can still make progress.
But there is no known upper bound on how long either one might take.
Now Process P waits for Q.
Nothing arrives.
Has Q crashed?
Or is Q just very slow?
There is no deadline after which P is entitled to know.
The two realities are observationally indistinguishable.
And this is where consensus runs into one of its most famous walls.
FLP Removes Almost Everything We Were Blaming
The Fischer-Lynch-Paterson result is uncomfortable partly because of how generous its assumptions already are.
Consider an asynchronous distributed system.
Messages are reliable.
They are not corrupted.
They are not duplicated.
They will eventually be delivered to correct processes.
There are no Byzantine participants sending malicious contradictions.
Only one process may crash.
Surely consensus should still be guaranteed.
FLP says no.
For every deterministic consensus protocol under that model, there exists an admissible execution in which the system never reaches a decision, even though at most one process fails. The original result describes consensus as agreement among reliable processes in an asynchronous system and proves that every protocol has a possible nonterminating execution with only one faulty process.
Notice what remains.
The network is reliable.
The processes are not malicious.
Only one process can stop.
And consensus still cannot be guaranteed.
That last word matters.
“Impossible” Does Not Mean “Nobody Ever Agrees”
FLP is easy to over-dramatize.
It does not say:
Distributed systems can never reach consensus.
Clearly they do.
It does not say:
Every execution fails.
It does not even require the network to lose messages.
The result is more precise:
Under complete asynchrony, no deterministic consensus algorithm can guarantee both correctness and eventual decision in every admissible execution when even one process may crash.
There may be executions where everyone reaches agreement immediately.
There may be executions where the system behaves beautifully for years.
The impossibility result says there is always some allowed timing of messages and process steps that can keep the algorithm from being forced into a decision.
The FLP authors make the critical asynchronous assumption explicit: there are no bounds on relative process speeds or message delays, no synchronized clocks that make timeouts authoritative, and therefore no general way to distinguish a dead process from one that is merely running very slowly.
That ambiguity is the knife edge.
The Slow Process and the Dead Process Wear the Same Costume
Suppose consensus needs a response from Process Q.
P waits.
Q may be dead.
If so, waiting forever destroys termination.
So perhaps P should stop waiting and decide without Q.
Except Q may merely be slow.
Its message could still arrive later with information that matters.
If P decides too early, another correct process with a different view might decide something incompatible, threatening agreement.
So P has two dangerous choices.
Wait indefinitely:
Maybe protect agreement, but risk termination.
Stop waiting:
Maybe protect termination, but risk deciding without enough information.
In a synchronous system, the timeout resolves this tension.
After the known deadline:
Q is not merely slow. Something has failed.
In a fully asynchronous system, the deadline does not exist.
Any message that has not arrived yet may still arrive later.
The network sits there with an infuriatingly calm expression saying:
Maybe tomorrow.
The algorithm cannot distinguish the histories based on silence alone.
That is not poor implementation.
It is missing information.
Every Solution Has Been Buying an Assumption
Now the progression becomes visible.
The easy majority algorithm worked because:
- Processes did not fail,
- Communication was reliable,
- Everybody eventually received the same proposals.
The crash-tolerant synchronous algorithm worked because:
- The number of failures was bounded,
- Communication happened in rounds,
- Timeouts could distinguish missing responses from merely pending ones.
The Byzantine solution needed more:
- Enough processes to overwhelm faulty participants,
- Multiple rounds of communication,
- Cross-checking between correct participants.
Then FLP removed timing bounds while allowing one crash.
The old mechanisms lost the assumption that made silence interpretable.
This is the deeper model:
Consensus algorithms do not manufacture certainty from nothing.
They transform assumptions into guarantees.
Reliable communication is an assumption.
Bounded delay is an assumption.
A maximum number of faulty processes is an assumption.
Authentication can be an assumption.
Majority overlap can be an assumption.
Randomness can be introduced.
Failure detectors can supply additional information.
Real systems find ways forward by strengthening the model somewhere.
Not because the theoreticians gave up.
Because some information has to enter the system before the uncertainty can be reduced.
Consensus Is Really About What Everyone Can Know Together
At the beginning, agreement looked like a voting problem.
Collect the values.
Pick the majority.
Done.
Then the communication channel became unreliable, and acknowledgements could not create certainty.
Processes started crashing, so missing information had to propagate around them.
Processes became Byzantine, so messages themselves became evidence that needed corroboration.
Timing guarantees disappeared, and now silence could no longer distinguish failure from delay.
Each step removed one comfortable assumption.
Each step exposed another thing the previous algorithm had quietly depended on.
That is why consensus keeps appearing in places that look unrelated.
Mutual exclusion.
Totally ordered multicast.
Electronic money transfer.
Transaction commit.
Replicated state.
Control systems.
All of them eventually need several independent processes to cross the same boundary:
We each know only part of what happened, but we must still behave as though one decision exists.
The algorithms matter.
The impossibility results matter more than they first appear to, because they tell us what the algorithms must be allowed to assume.
Agreement was never just about everybody choosing the same value.
It was about creating enough shared knowledge that choosing the same value becomes safe.
The more assumptions we remove, the less shared knowledge the system gets for free.
And the harder agreement becomes.
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)