What is wrong with this execution of an algorithm in Java?
Consider the following tree:
What I'm trying to do is emulate the Tree Wave algorithm, so that if a node has received a token from all but one of its directly related neighbors, it sends the token to that silent neighbor (always true for a leaf node). And if node receives a token from a silent neighbor, a decision is made. The nodes are always 7 and the tree structure is the same, so I always know each neighbor's node (the directly related nodes).
Tree algorithm pseudocode:
I have the following object:
public final class Node implements Runnable {
private final int name;
// Indicating token receiving from neighbours
private Map<Node, Boolean> neigh = new
HashMap<Node, Boolean>();
public Node(int name) {
this.name = name;
}
public int getName() {
return name;
}
public void addNeigh(Node node) {
neigh.put(node, false);
}
private int flag() {
Collection<Boolean> c = neigh.values();
int count = 0;
for (Boolean bool : c) {
if (!bool) {
count++;
}
}
return count;
}
private Node getSilentNeigh() {
for (Entry<Node, Boolean> entry : neigh.entrySet()) {
if (false == entry.getValue()) {
return entry.getKey();
}
}
return null;
}
public void sendToken(Node from, String token) {
Node n;
if ((n = getSilentNeigh()) != null && flag() == 1) {
if (from.equals(n)) {
System.out.println(name + " decides!");
}
}
neigh.put(from, true);
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Node)) {
return false;
}
final Node n = (Node) obj;
return name == n.name;
}
@Override
public int hashCode() {
int hc = 17;
return 37 * hc + name;
}
@Override
public void run() {
while(flag() > 1);
Node n = getSilentNeigh();
System.out.println(name + " sends token to " + n.getName());
n.sendToken(this, "token");
}
@Override
public String toString() {
return "Node " + name;
}
}
Inside the run () method there is a time (condition), which actually means .. wait (receiving tokens from neighbors), and when there is only one neighbor, the node will not receive a token to send a token to it.
This is how I create the nodes and how I link each other:
// Number of nodes
int numberOfNodes = 7;
// Array of nodes
Node[] nodes = new Node[numberOfNodes];
for (int i = 0; i < nodes.length; i++) {
// Creating node
nodes[i] = new Node(i);
}
nodes[0].addNeigh(nodes[1]);
nodes[0].addNeigh(nodes[2]);
nodes[1].addNeigh(nodes[0]);
nodes[1].addNeigh(nodes[3]);
nodes[1].addNeigh(nodes[4]);
nodes[2].addNeigh(nodes[0]);
nodes[2].addNeigh(nodes[5]);
nodes[2].addNeigh(nodes[6]);
nodes[3].addNeigh(nodes[1]);
nodes[4].addNeigh(nodes[1]);
nodes[5].addNeigh(nodes[2]);
nodes[6].addNeigh(nodes[2]);
What I am doing is randomly choosing the order of execution of the nodes:
// List holding random node numbers
List numbers = new ArrayList<Integer>();
int chosen = 0;
while (chosen < numberOfNodes) {
int processNum = randInt(0, (numberOfNodes - 1));
if (!numbers.contains(Integer.valueOf(processNum))) {
numbers.add(new Integer(processNum));
chosen++;
}
}
So, for example, the nodes can be in any order:
0, 5, 3, 4, 6, 2, 1 5, 3, 0, 2, 1, 6, 4 3, 1, 0, 2, 4, 6, 5
and then start streams:
for (Integer number : numbers) {
Thread thread = new Thread(nodes[number]);
thread.start();
}
Sometimes I get the expected result (2 must solve):
Nodes selected: 0, 4, 5, 2, 6, 3, 1
5 sends token to 2
4 sends token to 1
6 sends token to 2
3 sends token to 1
1 sends token to 0
0 sends token to 2
2 decides!
2 sends token to 0
0 decides!
But usually I get an error and only one solves:
Nodes selected: 5, 3, 4, 6, 0, 2, 1
3 sends token to 1
5 sends token to 2
4 sends token to 1
6 sends token to 2
2 sends token to 0
0 sends token to 1
1 decides!
Exception in thread "Thread-6" java.lang.NullPointerException
at uk.ac.ncl.csc8103.wave.Node.run(Node.java:86)
at java.lang.Thread.run(Thread.java:745)
And yes, this is for Assignment and I am very close to these guys .. but I ran into this problem.
source to share
Well your method run
calls Node n = getSilentNeigh();
This call can return null and you are using the variable n
without checking that it is not null.
@Override
public void run() {
while(flag() > 1);
Node n = getSilentNeigh(); // this call can return null
System.out.println(name + " sends token to " + n.getName()); // you are probably getting
// NullPointerException here
n.sendToken(this, "token");
}
source to share
Inside the run() method there is a while(condition) that actually means.. wait (receiving tokens from neighbours)
This is not correct according to your code
while(flag() > 1);
if Node has only one Node (4/5/6) - for them the flag () will return 1 and which will end the while loop and then move forward and send the request even before initiators start send the message
UPDATE
As you know, there are 4 initiators (3,4,5,6) and an exception for this code to exit the while loop.
Take this
Selected nodes: 5, 3, 4, 6, 0, 2, 1 3 sends token to 1 5 sends token to 2 4 sends token to 1 6 sends token to 2 2 sends token to 0 0 sends token to 1 1 solves!
It is purely a race condition that if a previously started initiator (5) has already reached / sent a message to another initiator neighbor (3) (1). while Initator (3) will try to start and get SlientNeigh, it will get Null (no slient neigh). this way you get Null pointer exception in n.sendToken.
Algorithm link : you don't need sycn (we don't have a rule that each Node should only receive one message from a neighbor).
From link three simple properties
β In each computation there is one initiator, which starts the algorithm by sending out exactly one message
ββ A process, upon receipt of a message, either sends out one message or decides
ββ The algorithm terminates in the initiator and when this happens, each process has sent a message at least once
source to share