Construction of a spanning tree (distributed)

General principle

Given a network and a starting node, it is easy to build a spanning tree in a distributed way. First, this node sends a message to all its neighbors. Then, the first time a node receives a message, it chooses this message's sender as parent and sends in turn another message to its neighbors. This propagation wave defines a tree whose root is the starting node (as shown in the picture).

 → 

Construction of a spanning tree in a network.

Implementation in JBotSim

This algorithm can be implemented in a few lines in JBotSim. We define a new class called TreeNode that extends Node (i.e. the usual way of coding distributed algorithms). Of the many events that a subclass of class Node can manage, only two are required here:

1. The selection of a node by the user (middle click on PCs, command-shift click on macs), which triggers a call to onSelection() on that node.
2. The arrival of a message, through method onMessage().

The corresponding code is given below and explained in detail afterwards. This algorithm is quite basic and serves as a classical prototype in many (more elaborate) algorithms. Thus it might be a good investment to understand it well.

import io.jbotsim.core.Message;
import io.jbotsim.core.Node;

import java.util.ArrayList;
import java.util.List;

public class TreeNode extends Node {
    Node parent = null;
    List<Node> children = new ArrayList<Node>();

    @Override
    public void onSelection() {
        parent = this; // becomes root
        sendAll(new Message(this)); // send own reference to neighbors (see explanations)
        setColor(Color.red);
    }

    @Override
    public void onMessage(Message message) {
        if (parent == null) {
            parent = message.getSender();
            getCommonLinkWith(parent).setWidth(4);
            sendAll(new Message(parent)); // propagate wave to all neighbors
        } else {
            if (message.getContent() == this){
                children.add(message.getSender());
            }
        }
    }
}

Detailed explanations: The node selected by the user is the one from which the tree will be constructed. In other words, it is the root. Hence, the code we put in the onSelection() method comes to set the underlying node as root (i.e. parent = this;), then initiate the construction by sending a message to all the neighbors via sendAll(). This code will be executed only at the selected node (following the middle click on that node).

When a node receive a message, it is notified through the onMessage() method. If by this time it has no parent yet, then it chooses the sender of the message as parent. (Note that several messages may arrive at the same round, but then onMessage() will be executed for each message sequentially and thus there will be a first time.) For visualization purposes, the common link with the parent is put in bold, then a new message is sent in turn to propagate the wave further. One trick here is to put the identifier of the parent as message content (here, we use the reference of the object as its identifier, which is a bit cheating but simpler to deal with). This allows the parent to detect when it has a new child, based on seeing its own reference as content of a message (the else part). For homogeneity, the initial node, which is the root and thus its own parent sends this as the message content.

Test: You can test this algorithm by using the following main() method and then add the nodes by hand at execution time. The important line is to tell JBotSim to use TreeNode as the default type of node.

public static void main(String[] args) {
    Topology tp = new Topology();
    tp.setDefaultNodeModel(TreeNode.class);
    tp.setTimeUnit(500);
    new JViewer(tp);
    tp.start();
}

Note: Node selection is made by middle click (or Ctrl+Click).

Extending TreeNode further?

If your algorithm relies on a spanning tree as basic mechanism, then you can extend TreeNode further. Note, however, that one should be careful in overriding the onMessage() method further. Indeed, several types of messages may have to coexist at the different level of inheritance. A safe way to do this is to distinguish them using Flags.