Computer Science
Grade 12
20 min
The Birthday Party Plan
Breaking down planning a birthday party into smaller tasks (invitations, cake, games).
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Analyze the 'Birthday Party Plan' as an analogy for distributed consensus problems.
Define and differentiate between centralized, decentralized, and distributed systems.
Explain the core principles of a consensus algorithm using the party planning analogy.
Model the communication and state-machine replication challenges in a distributed system.
Evaluate the trade-offs between consistency, availability, and partition tolerance (CAP Theorem) in the context of the party plan.
Design a simple protocol for a multi-agent system to agree on a single value, such as a party date.
How do you get 10 friends to agree on a single time and place for a party using only text messages, especially when some messages might get lost? 🥳
This lesson uses the '...
2
Key Concepts & Vocabulary
TermDefinitionExample
Distributed SystemA network of autonomous computers (nodes) that communicate and coordinate their actions by passing messages to one another to achieve a common goal.The friends planning the party are individual 'nodes' in a distributed system. They operate independently but must communicate via text messages to coordinate the plan.
ConsensusThe process of achieving agreement among a group of distributed nodes on a single data value. This is challenging because nodes can fail or messages can be lost.All friends finally agreeing that the party will be on Saturday at 8 PM. If even one friend thinks it's at 7 PM, consensus has not been reached.
Node (or Agent)An individual participant or computer in a distributed system that has its own memory and process...
3
Core Syntax & Patterns
Two-Phase Commit (2PC) Protocol
Phase 1 (Voting): A coordinator proposes a value and asks all nodes to vote 'commit' or 'abort'. Phase 2 (Commit): If all nodes vote 'commit', the coordinator broadcasts a 'commit' message. If any node votes 'abort' or fails to respond, it broadcasts an 'abort' message.
Used to ensure all nodes in a distributed system either commit to a transaction or all abort, guaranteeing atomicity. In our analogy, one friend (the coordinator) proposes 'Saturday at 8 PM' and waits for everyone to reply 'Yes'. If even one person says 'No', the plan is aborted and a new proposal is needed.
Leader Election Algorithm
A process for dynamically choosing one node to act as a co...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
The Two-Phase Commit (2PC) protocol is often called a 'blocking' protocol. How does this characteristic relate to the CAP theorem when a network partition separates the coordinator from some participants that have already voted 'VOTE-COMMIT'?
A.It shows 2PC prioritizes Availability, as the non-partitioned nodes can still get a response.
B.It shows 2PC prioritizes Consistency over Availability; the blocked nodes become unavailable to ensure they don't create an inconsistent state.
C.It shows 2PC is not subject to the CAP theorem because it guarantees all three properties.
D.It shows 2PC prioritizes Partition Tolerance above all else, causing nodes to block to handle the partition.
Challenging
The leader failure example relies on timeouts to detect a dead leader. A friend, Bob, is in an area with very poor cell service, causing his 'heartbeat' messages to be severely delayed but not completely lost. How could this scenario compromise the system, and what is a potential protocol modification to improve resilience?
A.Delayed heartbeats could cause a false positive, triggering an unnecessary and disruptive leader election. A potential fix is to require multiple missed heartbeats before declaring failure.
B.Delayed heartbeats would cause the entire system to slow down to match Bob's speed, which is an intended feature.
C.The system would correctly identify Bob as a failed node and eject him from the group, which is the desired behavior.
D.This scenario is impossible; TCP/IP guarantees message delivery, so delays are not a factor in protocol design.
Challenging
Imagine modeling the party plan with a consensus algorithm like Raft, where the leader maintains a replicated log of all decisions (e.g., 'Entry 1: Theme=Pizza', 'Entry 2: Time=8PM'). How does this log-centric approach solve the problem of a newly elected leader not knowing the most recent state of the plan?
A.The new leader simply starts the plan over from scratch, asking everyone for new proposals.
B.The new leader is always the node that was most recently in contact with the old leader.
C.The new leader is chosen randomly, and its plan becomes the new official plan.
D.The election protocol ensures that only a node with the most complete and up-to-date log can become the new leader, thus preserving all past decisions.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free