Impossibility Under Asynchrony: What Consensus Cannot Promise

With no bound on message delay and one process allowed to fail, no deterministic algorithm is guaranteed both to agree and to finish. Real systems live with this by giving up guaranteed termination and leaning on timeouts, which are a failure detector under another name.

ages 22 to 238 practice questionsvideo included

What a learner can do afterwards

State the two properties the impossibility result puts in conflict and the model it assumes
Say which property practical systems relax, and what a timeout is standing in for
Explain why a slow process and a failed process cannot be told apart in this model

1 · Read

With no bound on message delay and one process allowed to crash, no deterministic algorithm guarantees both agreement and finishing. Agreement is the safety property and finishing is the progress property from the consensus topic. That clash is the impossibility result, often called FLP after Fischer, Lynch and Paterson. Its model assumes crash failures and fully asynchronous messages.

Try it together

A process goes silent. It may have crashed, or its messages may just be slow, and nothing in the model tells the two apart. Waiting forever risks never finishing, while deciding without it risks agreeing wrongly.

Practical systems relax guaranteed finishing, also called termination, and lean on timeouts instead. A timeout says no news after some wait counts as failed, which makes it a failure detector under another name. It can wrongly suspect a merely slow process.

State the price precisely: asynchrony plus one crash means agreement and guaranteed finish cannot both hold. Then say which guarantee your system gives up.

With no delay bound, silence leaves two choices, and each has a risk.

Async plus one crash forbids promising both agreement and finish, so systems trade finish for timeouts.

Original instructional content authored for os-taxonomy.

2 · Watch

En anglais

Take it off screen

Print a worksheetA4 with an answer key page for grown-ups. No screen, no internet.

Where it sits

Learn first

Consensus and Why Agreement Is Hard Clocks, Ordering and Happens-Before

Optional connections

Failure Models and Replication

This opens up

Raft: Leader Election and Log Replication

Then practise

8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.

Spotted a problem on this page? Tell us