Count a Distributed Tree with Nonblocking Messages

Problem Statement

You are tasked with designing a distributed protocol to count the total number of nodes in a network structured as a tree. Each node resides on a separate server and only knows its parent and its immediate children. The network is unreliable: messages can be delayed, lost, or duplicated, and nodes may crash or restart at any time.

Define a communication protocol where each node maintains a local state and a set of message handlers. Your goal is for the root node to eventually compute the total number of nodes in the entire tree.

Requirements

1. Define the message types exchanged between parent and child nodes.
2. Explain how a node distinguishes between new count requests and retransmissions (idempotency).
3. Describe the state machine for each node: How does a node track which children have responded?
4. What happens if a node receives a count request while it is still waiting for its own children to respond?

Constraints

• Nodes do not have a global view of the topology.
• Messages are asynchronous and non-blocking.
• A node may receive multiple 'count' requests from a parent due to network retries; it should only initiate one aggregation process per request ID.

Example

• Tree: A (root) -> {B, C}, B -> {D}
• Protocol: A sends 'COUNT_REQ(id: 101)' to B and C. B sends 'COUNT_REQ(id: 101)' to D.
• D responds to B with 'COUNT_RES(id: 101, val: 1)'. B aggregates and responds to A with 'COUNT_RES(id: 101, val: 2)'.
• C responds to A with 'COUNT_RES(id: 101, val: 1)'. A sums {1, 2, 1} (itself + 2 children) = 4.

Deliverables

• Describe your message schema and the local state maintained by a node.
• Sketch the logic for the onReceiveRequest(request_id) and onReceiveResponse(request_id, child_count) functions.