What is wrong with this execution of an algorithm in Java?

Consider the following tree:

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:

The tree algorithm

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.

+3


source to share


2 answers


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");
}

      

+1


source


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

      

+1


source







All Articles