Count Machines and Recover a Distributed Tree Topology

Problem Statement

In a distributed cluster, machines are organized in a hierarchical tree topology without a centralized inventory service. A designated root node must initiate a discovery protocol to count all reachable machines and reconstruct the topology (nodes and directed edges).

Implement the TopologyScanner class that executes this discovery for a given snapshot_id.

You are provided with a NetworkTransport interface with the following method:

• network.get_children(target_node: str, caller_node: str, snapshot_id: str) -> list[str]: Queries target_node for its downstream child IDs. This call may raise a TimeoutError on transient network partitions or machine crashes.

Your discovery protocol must satisfy:

1. Snapshot Correlation & Idempotency: All network queries must include snapshot_id. Stale responses or duplicate visits should not corrupt the aggregate.
2. Retries & Fault Isolation: When querying a child candidate, retry up to max_retries times on TimeoutError. If all retries fail, mark that endpoint as unreachable and do not explore further down that branch. A failed peer should not abort the entire discovery process.
3. Topology Validation: Verify whether the discovered reachable topology forms a valid directed tree rooted at root_id. If any cycle or cross-edge (a node with multiple parents) is encountered, is_valid_tree must be set to False.
4. Recovery Results: Return a DiscoveryResult containing the total count of reachable nodes (including root_id), the list of directed edges (parent, child), the list of unreachable node endpoints encountered, and the boolean is_valid_tree.

Class Interface

from dataclasses import dataclass

@dataclass
class DiscoveryResult:
    node_count: int
    edges: list[tuple[str, str]]
    unreachable_nodes: list[str]
    is_valid_tree: bool

class TopologyScanner:
    def __init__(self, network, max_retries: int = 2):
        self.network = network
        self.max_retries = max_retries

    def discover(self, root_id: str, snapshot_id: str) -> DiscoveryResult:
        pass

Constraints

• Number of nodes N <= 5,000.
• Maximum tree depth <= 100.
• Node identifiers are non-empty strings of alphanumeric characters.
• The root machine itself is local and always reachable.

Example

# Topology:
#        "node-0"
#       /        \
#   "node-1"    "node-2" (fails all retries)
#      |
#   "node-3"

scanner = TopologyScanner(network=mock_network, max_retries=2)
result = scanner.discover("node-0", "snap-101")

# Expected result:
# result.node_count == 3  # [node-0, node-1, node-3]
# result.edges == [("node-0", "node-1"), ("node-1", "node-3")]
# result.unreachable_nodes == ["node-2"]
# result.is_valid_tree == True