Noam Mori has found a bug in the spatial message propagation mechanism (Grid, HierGrid and TiledWraparound). The bug effects the handling of node location if it is exactly on the border of two bins. The symptoms of the bug is that after running the simulation for a while some nodes do not receive some of the messages sent to them, even by a physically close neighbor and even when there is no interference at all.

This bug is originated from the following method (this is the original code). File: Location.java, class: Location2D (same goes for Location3D):

    public boolean inside(Location min, Location max)
    {
        Location2D min2d = (Location2D)min, max2d = (Location2D)max;
        if(Main.ASSERT) Util.assertion(min2d.x<=max2d.x && min2d.y<=max2d.y);
        return x<=max2d.x && y<=max2d.y && x>=min2d.x && y>=min2d.y;
    }

The fix is:

      public boolean inside(Location min, Location max)
    {
        Location2D min2d = (Location2D)min, max2d = (Location2D)max;
        if(Main.ASSERT) Util.assertion(min2d.x<=max2d.x && min2d.y<=max2d.y);
        return x<max2d.x && y<max2d.y && x>=min2d.x && y>=min2d.y; //Changed by Noam Mori (= removed)
    }
    public boolean inside(Location bounds)
    {
        Location2D l2d = (Location2D)bounds;
        return x<l2d.x && y<l2d.y && x>=0 && y>=0; //Changed by Noam Mori (= removed)
    }

Explanation:
When deciding if a node is inside a squared area (a bin) the right and the bottom borders should not be considered part of the bin. This is because when trying to determine to which bin the node belongs the following methods are used:

    private LinearList getBin(Location l)
    {
        return bins[getBinI(l)][getBinJ(l)];
    }
    private int getBinI(Location l)
    {
        return (int)((l.getX()-bl.getX())/di);
    }
    private int getBinJ(Location l)
    {
        return (int)((l.getY()-bl.getY())/dj);
    }

The code states that nodes on the border of two adjacent bins belong to the top and/or left bin of the two and not both bins as the original inside(Location bounds) method implies. This inconsistency latter effects the handling of nodes movement if they are exactly on the border of two bins – it is removed from the liked list of the correct bin while the “size” field of a separate bin is wrongly updated or sometimes it does not change bins at all (depending on what is the node’s next step after stopping exactly on the border).

For example: say that each bin is 10X10 and there is a node in position <15,15>. This node moves to the left and stops exactly at position <10,15> (on the border of 2 bins). Say that it’s next step (step s) is to the right to position <10.2,15>. Before step s the node was part of the right bin but when it makes step s the original algorithm thinks that it is in the left bin (this is the result of the method getBin) and so the node will be wrongly transferred from the left bin to the right bin. This is done by removing the node from the bin’s linked list which is done on the correct list via the next and prev fields of the node (RadioData), but the “size” of the left bin is wrongly decremented, as seen in the following code:

    public void del(Field.RadioData data)
    {
        if(Main.ASSERT) Util.assertion(data.loc.inside(bl, tr));
        if(data.prev!=null) data.prev.next = data.next;
        if(data.next!=null) data.next.prev = data.prev;
        if(radioList==data) radioList = radioList.next;
        size--;
        data.next = null;
        data.prev = null;
        if(CHECK_CYCLE)
        {
            if(hasCycle())
            {
                throw new RuntimeException("cycle detected");
            }
        }
    }

When the “size” of a bin is smaller than the length of it’s list of nodes it can only transfer messages to the first “size” nodes in its linked list, as seen in the following code:

    public int visitTransmit(SpatialTransmitVisitor visitor, RadioInfo srcInfo, Location srcLoc, Message msg, Long durationObj, double limit)
    {
        int visited=0;
        for(Field.RadioData dst=radioList; dst!=null && visited<size; dst=dst.next, visited++)
        {
            visitor.visitTransmit(srcInfo, srcLoc, dst.info, dst.entity, dst.loc, msg, durationObj);
        }
        return visited;
    }

Fixing the method “inside” as described above solves the described bug in all its forms.

Gabriel Kliot

07/24/2008