Count the Nodes in a Tree of Servers
Servers are arranged in a tree: each knows its children and can send them asynchronous messages, and messages may be delayed, lost or delivered twice. Design a protocol by which the root learns how many servers are in the tree.
Describe the messages, what each server stores while a count is in progress, how retries work without double counting, how a server with a crashed child completes, and how a second count can start while the first is still finishing.
Hints
Hint 1
Two message types: a count request flowing down and a count reply flowing up. A leaf replies 1; an inner node replies 1 plus the sum of its children's replies.
Hint 2
Give every count a request id. A node remembers the id and its partial sums, so a duplicate request is answered from memory and a duplicate reply from a child is ignored.
Hint 3
Retry a child that has not replied, with a timeout; after enough retries, report the child as unreachable in the reply rather than hanging the whole count.
Asked at
Sign in to talk to the interviewer — ask what's in scope, what scale to design for, or for a nudge when you're stuck. Conversations save to your account.