1
$\begingroup$

I am dealing with the Shortest path tree problem in the specific synchronous environment.

In the following algorithm, initiator begin the execution calling primitives Construct. This primitive offers every neighbors but its father to be linked to the tree by a construction message cons.

Construct()
    Begin
        For all j in neighbor_i\{father_i}
        send_to(j,cons,distance+1));
    End For
End

Receiving a message, the site looks if the distance is the best put forward is better than the current distance. If it is the case, then it accepts the proposition and calls itself Construct to offer to its neighbors to become their father because it got closer to the root.

In a synchronous environment, the algorithm is the same but we have to notify that as far as the environment is synchronous, the first linking proposition is unavoidably the best.

  1. I don't understand this assumption.

  2. We notice that root is linked to pulse $0$, but I don't understand why sites at the distance $i$ are linked to pulse $i$.

Ask me if you need some more details.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.