1
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ Certainly, hypercubes have cycles but no leaves and trees have leaves but no cycles. But how is this related to message passing? Aren't you supposed to be making a distributed computation? $\endgroup$ – David Richerby Sep 22 '14 at 0:00
  • $\begingroup$ I just want to change STATE of the node or leaf according to topology. I am doing something wrong? $\endgroup$ – real1 Sep 22 '14 at 0:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've added pseudocode. $\endgroup$ – real1 Sep 22 '14 at 15:53
  • $\begingroup$ @real1 Implementing Peter's answer? That belongs here, then, not in your question. $\endgroup$ – Raphael Sep 22 '14 at 16:13
  • $\begingroup$ I want to be sure it is implemented in right way. $\endgroup$ – real1 Sep 22 '14 at 16:22
  • $\begingroup$ @real1: yes, implementing it that way is one way to do it. Please mark as answered if your question is resolved. $\endgroup$ – Peter Sep 28 '14 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.