Chapter 3 Quiz: Distributed Systems Fundamentals
Multiple Choice Questions
Question 1
The CAP theorem states that a distributed system cannot simultaneously guarantee all three of which properties?
A) Consistency, Atomicity, Partition Tolerance B) Consistency, Availability, Performance C) Consistency, Availability, Partition Tolerance D) Concurrency, Availability, Partition Tolerance
Answer: C
Explanation: The CAP theorem (Brewer's theorem) states that a distributed data store cannot simultaneously provide Consistency (every read receives the most recent write), Availability (every request receives a non-error response), and Partition Tolerance (the system continues operating despite network partitions). Since network partitions are unavoidable in real distributed systems, the practical choice is between consistency and availability during partitions.
Question 2
A PBFT system with 10 nodes can tolerate at most how many Byzantine faults?
A) 2 B) 3 C) 4 D) 5
Answer: B
Explanation: PBFT requires n >= 3f + 1 nodes to tolerate f Byzantine faults. With n = 10: 10 >= 3f + 1, so 9 >= 3f, giving f <= 3. The system can tolerate at most 3 Byzantine faults. This is because the protocol needs a 2/3 supermajority of honest nodes to reach agreement even when Byzantine nodes send contradictory messages.
Question 3
Which of the following correctly describes the FLP impossibility result?
A) No consensus protocol can work in any distributed system B) No deterministic consensus protocol can guarantee termination in a fully asynchronous system with even one crash failure C) Byzantine fault tolerance is impossible with fewer than 4 nodes D) No consensus protocol can achieve both safety and liveness simultaneously
Answer: B
Explanation: The Fischer-Lynch-Paterson (FLP) result proves that in a fully asynchronous system, no deterministic consensus protocol can simultaneously guarantee agreement, validity, and termination if even one process can crash. The key qualifications are "deterministic," "fully asynchronous," and "one crash failure." Randomized protocols, partially synchronous networks, and probabilistic guarantees are all valid ways to circumvent FLP.
Question 4
What is the fundamental innovation of Nakamoto consensus compared to PBFT?
A) It achieves faster transaction throughput B) It requires fewer network messages per round C) It enables permissionless participation by replacing identity with computational work D) It provides stronger finality guarantees
Answer: C
Explanation: Nakamoto consensus's paradigm shift was solving the Sybil problem for open-membership BFT. PBFT requires a known, fixed set of participants, making it inherently permissioned. Nakamoto consensus ties voting power to computational resources (Proof of Work), allowing anyone to participate without identity verification. This came at the cost of throughput (option A is wrong — PBFT is faster) and finality strength (option D is wrong — PBFT provides deterministic finality vs. Nakamoto's probabilistic finality).
Question 5
In the context of distributed systems, what is the difference between safety and liveness?
A) Safety means the system is secure; liveness means it is responsive B) Safety means nothing bad happens; liveness means something good eventually happens C) Safety refers to data encryption; liveness refers to node uptime D) Safety is about crash tolerance; liveness is about Byzantine tolerance
Answer: B
Explanation: In distributed systems theory, safety properties specify that "nothing bad ever happens" — for example, agreement (all correct nodes decide the same value) and validity (the decided value was actually proposed). Liveness properties specify that "something good eventually happens" — for example, termination (every correct node eventually decides). This distinction is critical because many protocols guarantee safety unconditionally but guarantee liveness only under certain network conditions.
Question 6
Which of the following is true about crash fault tolerance vs. Byzantine fault tolerance?
A) CFT requires 3f + 1 nodes; BFT requires 2f + 1 nodes B) CFT handles nodes that lie; BFT handles nodes that crash C) CFT requires 2f + 1 nodes to tolerate f faults; BFT requires 3f + 1 nodes D) CFT and BFT require the same number of nodes but different protocols
Answer: C
Explanation: Crash fault tolerance requires 2f + 1 nodes (a simple majority) because crashed nodes merely stop participating — they never send misleading messages. Byzantine fault tolerance requires 3f + 1 nodes because Byzantine nodes can actively send contradictory messages to different parts of the network, requiring a 2/3 supermajority of honest nodes to outvote the liars in the worst case.
Question 7
A blockchain that always accepts transactions and produces blocks, even during a network partition, but may experience temporary forks, is best classified as:
A) CP (Consistent and Partition-tolerant) B) AP (Available and Partition-tolerant) C) CA (Consistent and Available) D) CAP (all three simultaneously)
Answer: B
Explanation: This describes an AP system like Bitcoin. During a partition, both sides of the network continue accepting transactions and producing blocks (availability), and the system operates across the partition (partition tolerance), but the two sides may diverge (sacrificing consistency). When the partition heals, the shorter chain is abandoned, restoring consistency. The system prioritizes availability over consistency during partitions.
Question 8
The Raft consensus protocol was designed primarily to improve upon Paxos in which way?
A) Higher throughput B) Byzantine fault tolerance C) Understandability D) Support for permissionless networks
Answer: C
Explanation: Raft was explicitly designed "In Search of an Understandable Consensus Algorithm" (the title of Ongaro and Ousterhout's 2013 paper). It achieves the same safety guarantees as Multi-Paxos but decomposes the protocol into distinct, intuitive subproblems (leader election, log replication, safety). Raft does not add BFT (option B), does not support permissionless networks (option D), and has comparable throughput to Paxos (option A).
Question 9
Bitcoin's probabilistic finality means:
A) Transactions are confirmed randomly B) The probability of a transaction being reversed decreases exponentially with each additional confirmation C) Miners randomly decide which transactions to include D) There is always a 50% chance that any transaction can be reversed
Answer: B
Explanation: In Nakamoto consensus, once a block containing a transaction is buried under additional blocks, the probability of an attacker building a longer alternative chain (and thus reversing the transaction) decreases exponentially with each new block. After 6 confirmations (about 60 minutes in Bitcoin), the reversal probability is less than 0.1% under standard assumptions. This is probabilistic finality — never absolutely certain, but approaching certainty asymptotically.
Question 10
The PACELC framework extends the CAP theorem by addressing:
A) The tradeoff between performance and cost B) The tradeoff between latency and consistency when there is no partition C) The tradeoff between security and decentralization D) The tradeoff between throughput and fault tolerance
Answer: B
Explanation: PACELC stands for "if Partition, choose Availability or Consistency; Else, choose Latency or Consistency." The CAP theorem only describes behavior during partitions, but distributed systems face tradeoffs even during normal operation. A system might prioritize low latency (returning responses quickly, possibly with stale data) or consistency (waiting for all replicas to agree, increasing latency). PACELC captures both the partition-time and normal-operation tradeoffs.
Question 11
Which of the following is NOT a valid way to circumvent the FLP impossibility result?
A) Assuming partial synchrony instead of full asynchrony B) Using randomized consensus algorithms C) Adding more nodes to the network D) Accepting probabilistic finality guarantees
Answer: C
Explanation: FLP proves that deterministic consensus is impossible in a fully asynchronous system with even one crash fault, regardless of the number of nodes. Adding nodes does not help — the impossibility is fundamental to the model, not a resource limitation. Valid circumventions include assuming partial synchrony (A), using randomization (B), and accepting probabilistic guarantees (D), each of which relaxes one of FLP's core assumptions.
Question 12
Why is a 51% attack on Bitcoin considered economically irrational rather than technically impossible?
A) The Bitcoin protocol cryptographically prevents any entity from acquiring 51% of hash power B) The cost of acquiring and operating sufficient mining hardware exceeds the potential profit from an attack, especially since a successful attack would devalue the attacker's own holdings C) Mining pools automatically prevent any single entity from exceeding 50% D) The Bitcoin software limits each entity to a maximum percentage of network hash power
Answer: B
Explanation: There is no technical mechanism in Bitcoin that prevents a single entity from acquiring 51% of hash power (options A, C, and D are all false). The defense is economic: the hardware, electricity, and operational costs of mounting a 51% attack on Bitcoin would be enormous (billions of dollars), and a successful attack would likely crash Bitcoin's price, devaluing the attacker's own equipment and any Bitcoin holdings. The attack is technically possible but economically self-defeating for large networks.
Short Answer Questions
Question 13
Explain why the shift from deterministic finality to probabilistic finality was considered a paradigm shift in distributed systems. What did it enable, and what did it sacrifice?
Model Answer: Classical distributed systems required deterministic finality: once a decision is committed, it is permanent and irreversible. This limits participation to known, trusted nodes because the protocol must guarantee that committed values are never overturned. Probabilistic finality was a paradigm shift because it relaxed this requirement — a decision becomes increasingly certain over time but is never absolutely final. This relaxation enabled permissionless participation (anyone can join without identity verification), Internet-scale deployment (no O(n^2) message rounds), and tolerance of a dynamic membership set. The sacrifice was certainty: transactions can theoretically be reversed, especially shortly after confirmation, and the system provides no hard guarantee about when finality is "good enough." For financial systems where irreversibility matters, this requires users to wait for multiple confirmations.
Question 14
A student claims: "The CAP theorem is irrelevant to single-node databases because they do not have partitions." Evaluate this claim.
Model Answer: The claim is largely correct but requires nuance. A single-node database has no network partitions (there is no network between nodes), so partition tolerance is not a concern. Such a system can provide both consistency and availability — it is a CA system. However, single-node databases sacrifice fault tolerance entirely: if that single node fails, the system is completely unavailable. The CAP theorem becomes relevant the moment you replicate data across multiple nodes for fault tolerance, because replication introduces the possibility of network partitions between replicas. So the student is technically correct that CAP does not constrain single-node systems, but this is because single-node systems have already made the worst possible tradeoff: zero fault tolerance.
Question 15
Compare and contrast the communication complexity of PBFT and Nakamoto consensus. How does each approach scale, and what are the implications?
Model Answer: PBFT has O(n^2) message complexity per consensus round — each of the n nodes must communicate with every other node during the prepare and commit phases. This means doubling the number of nodes quadruples the message count, making PBFT impractical beyond roughly 20-50 nodes. Nakamoto consensus has O(n) communication per block — the block is simply broadcast to all nodes in the network via gossip protocol. This makes it far more scalable in communication cost. However, the tradeoff is time: Nakamoto consensus requires minutes (Bitcoin's ~10-minute block time) versus PBFT's milliseconds-to-seconds. Additionally, Nakamoto consensus has enormous computational cost (Proof of Work) that does not appear in the message complexity analysis. So PBFT is communication-expensive but time-efficient, while Nakamoto consensus is communication-cheap but time-expensive and computationally expensive. The implications are that PBFT is suited for small, permissioned networks requiring fast finality, while Nakamoto consensus is suited for large, permissionless networks where participation is more important than speed.