More Hints for Question 1
The root processor sends a message to its neighbours in the first round asking them to be its
children. When a processor receives a reques for adoption from a neighbour:
Note A processor should note send requests for adoption to its parent or to any other
processors that have sent it requests for adoption.
- the request will be declined if the processor already has a parent.
A negative acknowledgement must be sent to the neighbour.
- the request might be accepted if the processor does not yet have a parent. The processor
will temporarily accept the request by setting its parent variable to the ID of the neighbour
that sent the request. Note that if the processor receiving the message has an odd ID then
it will accept the request only if a processor with even ID agrees to be one of its descendants
(its child or the child of one of its children, or the child of a child of one of its children, or ...), otherwise the processor cannot be part of the multicasting tree and the request must
To make the decision of whether an odd ID processor will be part of the multicasting tree, the
processor needs to wait until it has received replies from all its neighbours about the
requests that it send them.