Count the Nodes of a Process Tree Using Only Asynchronous Messages

Every node of a rooted tree runs as its own process. The processes share no memory and can talk to each other only through two primitives: ```python send_async(to_id, message) # returns immediately; the message is delivered later receive() # blocks until a message arrives; returns (sender_id, message) ``` Write the code that runs on every node so that the root ends up knowing how many nodes the tree has. Then harden it against messages that are lost or delivered twice, and decide what structure the result should have when the caller needs more than a bare count. Assume each process knows its own id, its parent's id (none for the root) and the ids of its children, and nothing else about the tree. ### Clarifying Questions - Does each node know its parent and its children, or only the ids of its neighbors? - How does the computation start: does only the root receive a request from the caller, or do all processes start at the same time? - Are messages between one pair of processes delivered in the order they were sent? - Can `receive` time out, or does the code need a separate timer? - Can processes crash, or only messages go missing? ### Part 1 — Count the nodes Assume every message is delivered exactly once, after an arbitrary delay and in any order. Write the per-node logic and the root's result. ```hint Let each subtree answer for itself Think about what a node can report to its parent once it has heard from every one of its own children. ``` #### What This Part Should Cover - The messages each node sends and when it sends them - How a node knows it has heard from every child, without relying on message order - Why the root's total is correct - The number of messages and the time to finish, in terms of the number of nodes and the depth ### Part 2 — Lost and duplicated messages Now any message can be lost, and any message can be delivered more than once. Change the protocol so that the root still gets the right count. ```hint A retry must not change the answer Ask what happens if a node sees the same request twice or the same reply twice, and what the sender of a lost message can observe. ``` #### What This Part Should Cover - How duplicates are prevented from being counted twice - How lost messages are detected and resent, and which side resends - What a node does when it is asked again for an answer it has already sent - What happens when a subtree never answers ### Part 3 — The structure of the result The caller now wants a result with more structure than one integer. Decide what each node's reply should contain and what the root returns. ```hint Some summaries merge, some grow Compare a reply whose size stays fixed as it moves up the tree with one that carries every descendant. ``` #### What This Part Should Cover - A concrete result type and what each reply carries - How the size of messages grows with the size of the subtree - How the result reports a count that may be incomplete ### What a Strong Answer Covers - Settles what each node knows and how the computation starts before writing code - A correct convergecast in which each node replies once, after all of its children - Idempotent handling of duplicates keyed by sender, and request retries driven by timeouts - A result type whose message size is reasoned about explicitly - Message counts, latency in terms of tree depth, and the failure modes left open ### Follow-up Questions - Nodes know only their neighbors, with no parent or child labels. How do you build the counting tree on the fly? - A process crashes after receiving the request. How long does the root wait, and what does it return? - The tree is a path of a million nodes. How long does a count take, and can you make it faster? - The caller asks for the count repeatedly while the tree changes. How do you keep separate runs from mixing their messages?