Message Passing vs Graph Algorithms

When designing a node algorithm, an important question is what communication primitives a node can use? For example, does the node know its neighbors? can a node detect new incident links? can a node read and/or write into the memory of its neighbors? should it rather exchange messages for all purposes?

While a large number of models exist, it is common to distinguish between two families of paradigms:

• Graph-based algorithms
• Message passing algorithms

This tutorial gives an example for each paradigm, solving the same initial problem, called the Loner problem, where a node turns red when it has at least one neighbor, green otherwise (the node is a loner).

Graph-based algorithm

At the graph level, a node is directly aware of its incident links and adjacent neighbors. Technically, we allow the node to use the three following methods that allows, which one should consider as forbidden in message passing algorithms.

1. onLinkAdded(): override this method to specify what a node does when an incident link is added
2. onLinkRemoved(): override this method to specify what a node does when an incident link is removed
3. getNeighbors(): retreives the list of nodes with whom the current node shares a link

import io.jbotsim.core.Color;
import io.jbotsim.core.Link;
import io.jbotsim.core.Node;

public class LonerGraphBased extends Node{
    @Override
    public void onStart() {
        if (getNeighbors().isEmpty()) {
            setColor(Color.green);
        } else {
            setColor(Color.red);
        }
    }

    @Override
    public void onLinkAdded(Link link) {
        setColor(Color.red);
    }

    @Override
    public void onLinkRemoved(Link link) {
        if (getNeighbors().isEmpty())
            setColor(Color.green);
    }
}

Message passing algorithm

In the message passing version, the nodes are not immediately informed when a neighbors arrives or leaves. Instead, they rely on sending messages repeatedly to detect the presence of other nodes. A possible implementation of this principle is as follows:

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

public class LonerMessageBased extends Node {
    private boolean heardSomeone = false;

    @Override
    public void onClock(){
        if (heardSomeone){
            setColor(Color.red);
        } else {
            setColor(Color.green);
        }
        heardSomeone = false;
        sendAll(new Message());
    }

    @Override
    public void onMessage(Message msg) {
        heardSomeone = true;
    }
}

In both cases, think of telling the topology which of these classes is your default node model. You may want to slow down the execution by calling setTimeUnit() on your Topology object (in the main method).

When the frontier is blurred

We presented above two possible ways of solving the same problem, depending on whether we consider a graph-based model or a message passing model. In many cases, the actual model lies between these two extremes. For instance, it is common to assume that the nodes can identify their neighbors (or communication channels towards them). In this case, looping over getNeighbors() to send each neighbor a particular message seems reasonable. Likewise, manipulating directly the node object of a neighbor is cheating in general, but the particular case of calling getID() on a neighbor when we assume that its identifier is known is reasonable too.

In summary, the polyvalence of JBotSim makes it extremely permissive. An algorithm designer can cheat in about all imaginable ways. We do not attempt to prevent this; rather, we consider that it is your responsibility to identify which primitives you can allow yourself, depending on the considered model.

Next tutorial: Centralized Algorithms

So far, we have seen only distributed algorithms (a.k.a. node algorithms). The next tutorial will present how to code a Centralized Algorithm in JBotSim.