# Count Machines and Recover a Distributed Tree Topology A cluster's machines form a rooted tree. Design a protocol that returns the number of machines and, as a follow-up, reconstructs the tree topology without relying on a central inventory. ### Constraints & Assumptions - Practice assumption: every machine knows its own unique ID, parent, and immediate children. - Parent-child channels are bidirectional; messages may be delayed, duplicated, or retried. - Membership is stable during one requested snapshot. - A coordinator can contact the root but cannot directly query every machine. - A failed or unreachable machine must not be silently counted as a successful response. ### Clarifying Questions to Ask - Is the tree guaranteed to be valid, connected, and acyclic? - Is an exact point-in-time snapshot required? - What timeout and partial-result behavior should callers see? - How large and deep can the tree be? ### Part 1: Distributed Count Specify request, response, correlation, deduplication, aggregation, timeout, and retry behavior for counting every reachable machine exactly once. #### Hints - Each subtree can summarize itself. - A retry should not start an unrelated logical count. #### What This Part Should Cover - Termination and aggregation - Idempotent message handling - Explicit incomplete-result semantics ### Part 2: Tree Topology Extend the protocol to return all nodes and edges. Explain representation, memory and message costs, validation, and handling of duplicate or inconsistent child reports. #### Hints - A parent can combine child summaries without knowing the whole cluster beforehand. #### What This Part Should Cover - Unambiguous topology representation - Validation of tree invariants - Complexity and payload-size trade-offs ### Part 3: Dynamic or Failing Cluster Explain what changes when membership can change during the operation or a subtree is unavailable. #### Hints - Define the consistency guarantee before selecting a mechanism. #### What This Part Should Cover - Snapshot or version strategy - Partial failure behavior - Operational observability ### What a Strong Answer Covers - A correlation-bound convergecast protocol - Idempotency, termination, and honest failure semantics - Topology validation and O(n) cost reasoning - A defensible consistency model for dynamic membership ### Follow-up Questions - How would you avoid recursion limits on a very deep tree? - How could the root stream a huge topology rather than buffer it? - How would you detect an accidental cycle? - What if only an approximate count is needed continuously?