## Count a Distributed Tree with Nonblocking Messages A tree's nodes run as independent processes on different machines. A node knows only its own ID, its parent, and its direct children. It has a provided asynchronous primitive `sendAsync(toNode, message)` and must implement `receive(fromNode, message)` without blocking. Design the message protocol and per-request state so the root can obtain the total number of nodes in its tree. Then extend it for duplicate requests, duplicate replies, and lost messages. Assume the topology is static during one count unless you explicitly define different semantics. ### Part 1 — Define Messages and Local State Specify count-request and count-report messages, request identity, sender validation, and the state one node keeps while a count is active. #### What This Part Should Cover - A unique count ID carried by every message. - Expected child IDs, received-child tracking, and accumulated subtotal. - Whether the node counts itself and how the root receives the final result. - State isolation for concurrent or repeated count requests. ```hint Store contributors, not only a number A subtotal alone cannot reveal whether the same child's report was applied twice or which children are still missing. ``` ### Part 2 — Handle Requests and Reports Without Blocking Give event-handler pseudocode for receiving a count request from a parent and a count report from a child. Cover leaves, internal nodes, the root, unexpected senders, and completion. #### What This Part Should Cover - Leaves immediately reporting a subtotal of one. - Internal nodes sending requests to all children and returning only after every child reports. - Idempotent handling of a repeated request while work is active or completed. - No thread waiting synchronously for child responses. ```hint Completion is a state transition When the set of reporting children equals the expected set, emit one parent report and mark that count request complete. ``` ### Part 3 — Survive an Unreliable Network Add retry, duplicate suppression, timeout, and cleanup behavior. Explain which guarantees are possible if a node is permanently unreachable and how late messages are handled. #### What This Part Should Cover - Retransmission keyed by the same count ID rather than a new logical request. - Cached completed replies for duplicate parent requests. - Deduplication of child reports by child ID and request ID. - An explicit failed, partial, or retrying result when progress cannot be proven. ```hint Retry the same operation identity At-least-once delivery is useful only when both request and report handlers recognize a replay of work already seen. ``` ### Part 4 — Test and Operate the Protocol Describe state-machine tests and production metrics for leaf, chain, wide tree, reordering, duplication, loss, and process restart. #### What This Part Should Cover - Deterministic message simulation without real sleeps. - Invariants that each reachable node contributes once per count ID. - Bounded retention for active and completed request state. - Metrics for completion latency, retries, duplicates, timeouts, and pending children. ```hint Control the network in tests A fake transport can deliver, drop, duplicate, and reorder specific messages while the node logic remains unchanged. ``` ### What a Strong Answer Covers - Models each node as an asynchronous state machine rather than a recursive blocking call. - Produces exactly one contribution per node under duplicate delivery. - Distinguishes temporary packet loss from permanent node failure. - States topology and restart assumptions instead of hiding them. ### Follow-up Questions 1. How would a node recover active request state after restarting? 2. What changes if children may be added during a count? 3. How would you cancel an in-progress count and clean up descendants? 4. Can the root report a useful partial result without misrepresenting it as exact?