Questions: Synchronous vs. Asynchronous Distributed Systems

Question 1

In a fully asynchronous distributed system, process A sends a message to process B and receives no response after waiting 10 minutes. What can A correctly conclude?

• A. Process B has crashed, since any working process would have responded by now
• B. The network is partitioned between A and B
• C. Nothing definitive — B may have crashed or may simply be very slow, since there is no upper bound on message delay or processing time
• D. B received the message but chose not to respond, indicating a Byzantine fault

Answer: (C)

This is the core hardness of asynchrony: crashed processes and slow processes are indistinguishable. An asynchronous system guarantees only that messages *eventually* arrive and processes *eventually* take steps — there is no upper bound. No matter how long A waits, it cannot rule out that B is merely slow. This indistinguishability is exactly the reason FLP impossibility holds: you can never safely declare a process dead without risking treating a slow-but-alive process as crashed.

Question 2

The FLP impossibility result proves that in a fully asynchronous distributed system, consensus is unsolvable. What is the core reason?

• A. Message loss is too frequent in asynchronous networks for any protocol to succeed
• B. Asynchronous systems cannot elect a leader, and consensus requires a leader
• C. A crashed process and a slow process look identical, so no algorithm can safely decide without risking being wrong when a 'dead' process is actually alive
• D. The theorem only applies when more than half of processes can fail

Answer: (C)

FLP holds even when only *one* process can crash. The impossibility comes from indistinguishability: in any protocol, there must be some state where the system is 'balanced' — one more message or step in either direction could produce a 0 or 1 decision. But because you cannot distinguish a crashed process from a slow one, you cannot force the system out of that balanced state without risking a safety violation. Options A and D misstate the theorem; option B is an incorrect reduction (Paxos has no permanent leader requirement).

Question 3

A synchronous distributed system requires that most messages arrive within one second to qualify as synchronous.

• T. True
• F. False

Answer: False

Synchrony requires that timing bounds *exist and are known* — not that they be small. A system where messages are guaranteed to arrive within 10 minutes is synchronous. A system where messages can be delayed for an arbitrarily long but unspecified time is asynchronous. The key property is whether you can set a timeout and trust it: in a synchronous system, a timeout lets you infer failure; in an asynchronous system, no timeout gives you that guarantee.

Question 4

Protocols like Paxos and Raft are designed for partial synchrony: they guarantee safety (no incorrect decisions) under fully asynchronous conditions, but only guarantee liveness (making progress) when the network eventually stabilizes.

• T. True
• F. False

Answer: True

This is the correct characterization of partially synchronous protocols. Safety — never committing conflicting values — holds even during network partitions and arbitrary delays. But progress — actually reaching a decision — requires that the system become 'synchronous enough' for a quorum to communicate without timeout interference. This design reflects the FLP result: you cannot guarantee both safety and liveness under full asynchrony, so these protocols sacrifice guaranteed liveness while preserving safety.

Question 5

Why does the asynchronous model make consensus provably impossible even if only one process might crash, while the synchronous model allows consensus to be solved?

Model answer: In an asynchronous system, there is no timeout that reliably distinguishes a crashed process from a slow one — both look like silence. Any consensus algorithm must at some point decide, but doing so risks incorrectly treating a slow process as dead, potentially violating agreement or validity. In a synchronous system, known time bounds let you detect failure definitively: if a process doesn't respond within the guaranteed bound, it has crashed. This makes failure detection reliable, which is what consensus algorithms need to safely coordinate.

FLP impossibility (Fischer, Lynch, Paterson 1985) formalizes this: every deterministic consensus protocol has a 'bivalent' state where both outcomes remain possible, and an adversarial scheduler can delay messages indefinitely to keep the system in that state. With synchrony, the scheduler is constrained by known bounds, allowing protocols to escape bivalent states safely.