Layered Breadth First Search
This program visualizes the steps needed to find the shortest path to each
node of a network given a distinguished root node. (In this program the
root node will ever be node 0, however the network will change randomly,
sometimes there are many edges from node 0 to other nodes, sometimes there
are only few.) The shortest path to all nodes will guarantee the fastest
information transport in the network from the root node to the others,
under the assumption that all channels (edges) need the same amount of
time for transmitting information.
Because we want to see something on the screen, some assumptions must be
made. In theory, the number of processors is not limited to a certain number,
however I had to choose a fixed number of processors. I decided for 8 processors
because this makes the problem complex enough to show that this algorithm
is valid for more processors, on the other hand one can easily follow the
different steps of execution. Execution happens in so-called phases, and
a number of 8 processors imply between 3 and 5 phases, one phase consisting
of several transmissions. One can easily decide for another number of processors
with setting NOPROCS appropriately and providing a nice placement of the
processors on the screen. The placement which is now implemented arranges
all processors in a circle.
Another restriction I made for simplicity reasons (in order that the
network does not get too complicated) is that I did not implement any other
messages (often referred as msgs) than the absolutely necessary ones.
The following program description is a slightly modified version of the
description given in Nancy A. Lynchs Book "Distributed Algorithms":
The BFS 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 process i0 .
In the first phase, process i0 sends search messages to
all of its neighbors and waits to receive acknowledgements. A process that
receives a search message at phase 1 sends a positive acknowledgement.
This enables all the processes at depth 1 in the tree to determine their
parent, namely i0, and, of course, i0 knows its children.
This constructs layer 1.
Inductively, we assume that k phases have been completed and that the
first k layers have been constructed: Each process at depth at most k knows
its parent in the BFS tree, and each process at depth at most k-1 knows
its children. Moreover, the source i0 knows that all of this
has been accomplished. To construct the k+1st layer in phase k+1, process
i0 broadcasts a newphase message along all the edges of the
spanning tree constructed so far, intended for the depth k processes.
Upon receiving a newphase message, each depth k process sends out search
messages to all its neighbors except its parent and waits to receive acknowledgements.
The first search message received by a certain process indicates, that
it is now a new part in the BFS tree; Therefore this process sets the parent
accordingly, and a positive acknowledgement is sent to the parent node.
In all other cases, a negative acknowledgement will be sent. When a depth
k process has received acknowledgements for all its search messages, it
designates the processes which have returned a positive acknowledgement
as its children. If any acknowledgements have been positive, a positive
acknowledgement will be returned to its parent, and so on. Otherwise, negative
acknowledgements go down the way to the root process.
Process i0 terminates the algorithm when it sees a negative
acknowledgement, since no new nodes have been discovered.
Try it out!
This is the application: You need a Java 1.0 enabled internet browser,
or: download the applet and run it stand-alone after setting the correct
permissions and classpaths. If you do this, you will also need the DAJ
Maintained by: Wolfgang Schreiner
Last Modification: January 11, 1999