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. In an asynchronous system where one process may crash, which two properties can no deterministic algorithm both guarantee?

    • Encryption and authentication
    • Low latency and high throughput
    • Agreement and finishing

  2. What model does the FLP impossibility result for consensus assume?

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

  3. With no bound on message delay, a slow process and a crashed 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 may never finish; deciding may disagree
    • Its silence proves a crash, so it must stop the cluster
    • Its own clock is wrong, so it must reset before waiting

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

    • The timeout proved the node crashed, so nothing went wrong
    • 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's tests never saw its deterministic consensus algorithm fail, so it promises guaranteed agreement and guaranteed finish under asynchrony with one possible crash. How do you answer?

    • Reject: no deterministic algorithm can promise both
    • Accept, since enough testing can show the promise holds
    • Accept, if the tests ran on more than three machines
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 · The result assumes unbounded message delay and one possible crash.
  3. False · Silence fits both stories with no delay bound.
  4. A failure detector · No news after the wait counts as failed.
  5. Waiting may never finish; deciding may disagree · Silence fits both a slow node and a crashed one, so each choice carries a risk.
  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: no deterministic algorithm can promise both · The result rules out any deterministic algorithm guaranteeing both in this model. Passing tests cannot prove a guarantee that must hold for every possible delay.
Worksheet · LightMySky