Impossibility Under Asynchrony: What Consensus Cannot Promise · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

What async consensus cannot promise

Computing · Networks & Security · ages 22-23
Name ______________________   Date ____________

  1. Which two properties cannot both be guaranteed there?

    • Speed and elegance
    • Logging and metrics
    • Agreement and finishing

  2. What model does the impossibility result assume?

    • Synchronous rounds with no failures
    • Async messages with one allowed crash
    • A single computer with no network

  3. In this model a slow process and a failed process can always be told apart.

    Circle one:   True   False

  4. What is a timeout standing in for?

    • A faster network cable
    • A failure detector
    • A bigger hard drive

  5. A node waits for a reply that never comes. What is the dilemma?

    • Waiting forever may never finish, deciding may agree wrongly
    • The network cable colour is wrong
    • The log file is too short

  6. A timeout fires on a node that was merely slow. What went wrong?

    • Nothing, timeouts are infallible
    • The node broke the timeout
    • The detector suspected wrongly, which timeouts can do

  7. Your system must keep agreeing despite slow networks. Which concession fits?

    • Give up guaranteed termination and use timeouts
    • Give up agreement whenever waiting hurts
    • Ban all timeouts as unreliable

  8. A vendor promises guaranteed agreement plus guaranteed finish under asynchrony with crashes. How do you answer?

    • Reject, the impossibility result forbids exactly that
    • Accept, vendors test thoroughly
    • Accept if the price is low
LightMySky · lightmysky.comW1-mt_le54TNOeiR-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

What async consensus cannot promise W1-mt_le54TNOeiR-s1

  1. Agreement and finishing · That pair is exactly what the result puts in conflict.
  2. Async messages with one allowed crash · Unbounded delay plus one crash is the fatal combination.
  3. False · Silence fits both stories with no delay bound.
  4. A failure detector · No news after the wait counts as failed.
  5. Waiting forever may never finish, deciding may agree wrongly · Both horns of the dilemma follow from indistinguishability.
  6. The detector suspected wrongly, which timeouts can do · Timeout suspicion is a guess, not knowledge.
  7. Give up guaranteed termination and use timeouts · Working systems relax finishing and detect failure by timeout.
  8. Reject, the impossibility result forbids exactly that · The claim contradicts the proven clash.
Worksheet · LightMySky