Implement a layered breadth first search algorithm for a network of N
nodes. The underlying graph G=(V,E) is a connected undirected graph
and there is a distinguished source node i0. The problem is to find
a breadth first spanning tree rooted in the node i0.
Algorithm
The algorithm works as follows:
The spanning tree is constructed in layers, where each layer k consists
of the nodes at depth k in the tree. The layers are constructed
in a series of phases, one per layer, all coordinated by the node
i0.
Phase 1 - Process i0 sends search messages to all of its
neighbors and waits for acknowledgements. After the first phase all processes
at depth at most k=1 know their parent, and each process at depth
at most k-1=0 (i0) knows its children.
Phase k+1 - We assume k phases have been completed, that
is each process at depth at most k knows its parent and each process
at depth at most k-1 knows its children. Moreover, the source i0
knows that all these have been accomplished. In order to construct the
k+1 layer the source i0 broadcasts a newphase message
allong the branches of the already constructed spanning tree. When a process
on the layer k receives a newphase message, it sends search
messages to all its neighbors except its parent and waits to receive acknowledgements.
When a process receives a search message:
If it is for the first time then it designates the sender as the parent
and returns positive acknowledgement,
else return negative acknowledgement.
When a depth k process receives a positive acknowledgement then
the sender is added to the set of children. When it receives all acknowledgements,
it sends up to the process i0 the information that it has completed
the phase and a bit saying whether new children have been discovered in
the k+1 phase.
The process terminates when no new nodes are discovered.
Remarks
The information send from the k layer nodes up to the source can
be positive/negative acknowledgement if there were/were not new children
discovered.
When a node has received negative acknowledgements from all the children
or neighbors it knows that the subtree rooted in it was constructed, so
it can send back negative acknowledgements to subsequent newphase
messages received.
Program
You should see a button labelled "Press Me" embedded below. If you do not
see this button but the string "Please enable Java!" instead, you must
enable Java on your Web browser and then reload the page.
