Sorting list of vector clocks (total order)?

549 views Asked by At

I understand that vector clocks only provide a partial order. So you can't directly sort them. For this reason you use a tie-breaker for vectors that are concurrent, resulting in a total order.

However sorting the vector clocks so that every cause comes before every effect in the resulting list doesn't seem to work and I don't entirely get why.

I have extensive tests that show me that comparing two vectors works:

    @Override
    public int compareTo(VectorClock<K> that) {

        var res = 0;

        if (this.isAfter(that))
            res = 1;
        else if (that.isAfter(this))
            res = -1;
        else
            res = this.timestamp.compareTo(that.timestamp);

        System.out.println("compare " + this + " : " + that + " => " + res);

        return res;
    }

    public boolean isAfter(VectorClock<K> that) {
        boolean anyClockGreater = false;

        var set = new HashSet<K>();
        set.addAll(this.keySet());
        set.addAll(that.keySet());

        for (K key : set) {
            final Clock thatClock = that.get(key);
            final Clock thisClock = this.get(key);

            if (thisClock == null || thisClock.isBefore(thatClock)) {
                return false;
            } else if (thisClock.isAfter(thatClock)) {
                anyClockGreater = true;
            }
        }
        // there is at least one local timestamp greater or local vector clock has additional timestamps
        return anyClockGreater || that.entrySet().size() < entrySet().size();
    }

However when sorting a list of vector clocks, e.g. one with two vectors that have a happenedBefore relationship and a third vector that is concurrent to both others, it may happen that only the concurrent one is compared to the two others, and the vectors that depend on each other are not compared to each other. Instead their order is (wrongly) decided transitively by the tie-breaker:

VectorClock<String> v1 = VectorClock.fromString("{0=23, 1=28, 2=15, 3=23, 4=15, 5=22, 6=14, 7=19}"); // after v3
VectorClock<String> v2 = VectorClock.fromString("{0=11, 1=16, 2=28, 3=17, 4=24, 5=15, 6=10, 7=8}");
VectorClock<String> v3 = VectorClock.fromString("{0=15, 1=19, 2=15, 3=20, 4=15, 5=22, 6=14, 7=19}"); // before v1

var s = new ArrayList<>(List.of(v1, v2, v3));
s.sort(VectorClock::compareTo);
assertTrue(s.indexOf(v3) < s.indexOf(v1));

Prints (and fails):

compare {0=11, 1=16, 2=28, 3=17, 4=24, 5=15, 6=10, 7=8} : {0=23, 1=28, 2=15, 3=23, 4=15, 5=22, 6=14, 7=19} => 1
compare {0=15, 1=19, 2=15, 3=20, 4=15, 5=22, 6=14, 7=19} : {0=11, 1=16, 2=28, 3=17, 4=24, 5=15, 6=10, 7=8} => 1

What is the underlying reason for this? Is this generally impossible or is there an error?

0

There are 0 answers