Design a Distributed Tree Node Counter
You are tasked with designing a distributed system to count the total number of nodes in an N-ary tree. Each node in the tree represents a machine running a single process. Nodes communicate exclusively via asynchronous message passing.
System Description
- Tree Structure: An N-ary tree where each node knows its parent (if any) and its list of children.
- Communication: Asynchronous message passing. The runtime invokes
call(Node from, Message message)on a node when a message arrives. - Initiation: Any node can initiate the counting protocol locally via a
startCount()method.
Goal
The primary goal is to design the per-node logic such that when any node initiates a count, the protocol computes the total number of nodes in the entire tree and returns this count to the initiator.
Constraints & Requirements
- Message Types: Exactly two message types must be used:
REQUEST_COUNTandREPLY_COUNT. - Node Contribution: Each node must contribute exactly once to the total count. No double counting is allowed.
- Concurrency: Critical sections must be protected to ensure correctness.
Deliverables
Specify the following aspects of your design:
- Message Format: Define the format and fields for both
REQUEST_COUNTandREPLY_COUNTmessages. - Per-Node State: Describe the local state each node maintains to support the protocol.
- Propagation and Aggregation: Detail how a node propagates requests to its neighbors (parent/children) and aggregates replies.
- Duplicate Request Prevention: Explain how to prevent duplicate propagation when a node receives multiple requests for the same traversal.
- Initiator Termination: Describe how the initiator node detects that the global count is complete and can return the final result.
- Assumptions and Complexity: State your assumptions regarding concurrency and message delivery (e.g., out-of-order messages, at-most-once vs. at-least-once delivery). Analyze the time and message complexity of your proposed approach.
AI interview prep
Core dilemma
Coordinating distributed state updates and ensuring robust termination detection for an aggregation task in an asynchronous, message-passing N-ary tree, while strictly adhering to message type and exactly-once contribution constraints, especially under concurrent initiation.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design a Distributed Tree Node Counter
You are tasked with designing a distributed system to count the total number of nodes in an N-ary tree. Each node in the tree represents a machine running a single process. Nodes communicate exclusively via asynchronous message passing.
System Description
- Tree Structure: An N-ary tree where each node knows its parent (if any) and its list of children.
- Communication: Asynchronous message passing. The runtime invokes
call(Node from, Message message)on a node when a message arrives. - Initiation: Any node can initiate the counting protocol locally via a
startCount()method.
Goal
The primary goal is to design the per-node logic such that when any node initiates a count, the protocol computes the total number of nodes in the entire tree and returns this count to the initiator.
Constraints & Requirements
- Message Types: Exactly two message types must be used:
REQUEST_COUNTandREPLY_COUNT. - Node Contribution: Each node must contribute exactly once to the total count. No double counting is allowed.
- Concurrency: Critical sections must be protected to ensure correctness.
Deliverables
Specify the following aspects of your design:
- Message Format: Define the format and fields for both
REQUEST_COUNTandREPLY_COUNTmessages. - Per-Node State: Describe the local state each node maintains to support the protocol.
- Propagation and Aggregation: Detail how a node propagates requests to its neighbors (parent/children) and aggregates replies.
- Duplicate Request Prevention: Explain how to prevent duplicate propagation when a node receives multiple requests for the same traversal.
- Initiator Termination: Describe how the initiator node detects that the global count is complete and can return the final result.
- Assumptions and Complexity: State your assumptions regarding concurrency and message delivery (e.g., out-of-order messages, at-most-once vs. at-least-once delivery). Analyze the time and message complexity of your proposed approach.