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.

Assumptions

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 Program

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 i₀ .
In the first phase, process i₀ 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 i₀, and, of course, i₀ 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 i₀ knows that all of this has been accomplished. To construct the k+1st layer in phase k+1, process i₀ 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 i₀ 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 toolkit.

Source Code

Maintained by: Wolfgang Schreiner
Last Modification: January 11, 1999

[Up] [RISC-Linz] [University] [Search]