The invention is directed to techniques for maintaining a map of node relationships for a network of nodes (e.g., network of computers). In one example, the map of node relationships represents relationships overlaying and typically different from the network of physical connections among the nodes. Each child node periodically checks in with its parent nodes, and the parent nodes can thus determine when a child node has terminated a relationship with the parent or created a new relationship with a new parent. Changes in relationships propagate upward through the network of nodes so that each node maintains a map of the relationships among the descendants of that node. A root node receives the propagated change relationship information and maintains a map of the entire network and valid pathways through the network. The root node can use the map when responding to a request from a client to receive services from a node in the network and redirects the client to attach to a node in the network that has a valid path to the root node. The root node can then broadcast data (e.g. a stream of video data) throughout the network, which is received by all the clients attached to nodes in the network.