## Layered Breadth First Search |

Author:

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.

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 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

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

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

Maintained by: Wolfgang Schreiner

Last Modification: January 11, 1999

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