Determining on whether topology is a tree or a hypercube Assume that the nodes know that the topology G is either a hypercube or a
tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to reach terminal state TREE if G is a tree, terminal state HYPERCUBE if instead it is a hypercube. Let n be the number of nodes and m the number of edges, you would like to exchange O(m) messages in the worst case.

I will use DFS until I either:


reach a leaf or 
a node that has been visited before.


In the first case it is a tree and in the second one it is a hypercube. How does this sound?

In the below code, I assume every the graph is tree. But If I see cycle, I change the STATE to HYPERCube. This happens when a node gets the token twice.

Sample Pseudocode

Initiator
    Spontaneously
    begin
        Unvisited:= N(x);
        initiator:= true;
        VISIT;
    end

IDLE
    Receving(T)
    begin
        entry = sender;
        unvisited:= N(x) - {sender};
        VISIT;
        STATE = "TREE"; 
    end

VISITED
    Receiving(T)
    begin
        STATE = "HYPERCUBE"
    end

    Receiving(R)
    begin
        VISIT;
    end

Procedure VISIT 
begin
    if Unvisited =! 0 then
        next = Unvisited
        send(T) to next;
        become VISITED
    else
        if not (initiator) then send(Return) to entry endif
        become DONE;
    endif
end
As you have noticed, a simple solution is to generate a token at the initiator and then forward the token through the network using a DFS strategy.

If this token encounters a node that is a leaf, the node will record this information in the token before it is sent back. So when the token has completed the DFS, it will have returned to the initiator who then inspects the token to check if it has encountered any leaf.

The O(m) message complexity follows from the message complexity of DFS, and to show this it's sufficient to prove that the token is sent a constant number of times over each edge.