Author: Bogdan Matasaru

## Problem

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

1. 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.
2. 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.