chat-wane / causaltrack

You know what they call a Quarter Pounder with cheese in France?

CausalTrack

Keywords: Causality tracking, version vectors, interval version vectors, version vector with exceptions

This project provides structures for causality tracking. The first one is the well-known version vector (VV) which allows to characterise on-the-fly causality between events.

The second one is the interval version vector (IVV) [1] which provides a tracking of semantically dependent events. Therefore, independent events are non-blocking to each other.

The next one is a version vector with exceptions (VVwE) [2] which provides the same features than the IVV. Nevertheless, it does not use the same underlying structure.

We provide another version of the VVwE called perishing version vector with exceptions (PVVwE) where exceptions disappear over time by design. Such vector is useful in practice since messages are expected to arrive within defined range of time. Also, the site identifiers that are not used anymore tend to disappear.

Installation

$ npm install causaltrack

Usage

The module has been browserified and uglified. To include CausalTrack within your browser, put the following line in your html:

<script src="./causaltrack.bundle.js"></script>

Then, whether you use the browserified version or nodejs:

var VV = require('causaltrack').VV;   // version vector
var IVV = require('causaltrack').IVV; // interval version vector
var VVwE = require('causaltrack').VVwE; // version vector with exceptions
var PVVwE = require('causaltrack').PVVwE; // perishing VVwE

// #1 Initialize the causality tracking structure with the unique site
// identifier 42
var vv = new VV(42);
var ivv = new IVV(42);
var vvwe = new VVwE(42);
var pvvwe = new PVVwE(42);

// #2 Update the local entry of the local vector. Return a pair
// {_e:entry, _c:counter} of the sender which uniquely identifies the operation
var ecVV = vv.increment();
var ecIVV = ivv.increment();
var ecVVwE = vvwe.increment();
var ecPVVwE = pvvwe.increment();

// #3 Check if the operation has already been integrated
vv.isLower(ecVV);
ivv.isLower(ecIVV);
vvwe.isLower(ecVVwE);
pvvwe.isLower(ecPVVwE);

// #4 Check if the operation is ready to be integrated
vv.isRdy(rvv); // rvv instance of VV
ivv.isRdy(ecIVV); // ecIVV the entry clock specifying a dependency to an o
vvwe.isRdy(ecVVwE); // ecVVwE the entry clock specifying a dependency to an op
pvvwe.isRdy(ecPVVwE);

// #5 Increment the local vector with the entry clock of the received
// operation supposedly ready
vv.incrementFrom(ecVV);
ivv.incrementFrom(ecIVV);
vvwe.incrementFrom(ecVVwE);
pvvwe.incrementFrom(ecPVVwE);

References

[1] Optimized OR-Sets without Ordering Constraints

[2] Concise version vectors in WinFS

causaltrack's Issues

Object.keys unefficient

Current vectors use the Object.keys function to obtains the list of keys in order to store only the used identifiers which can be non contiguous.
However, this function is not efficient at all and should be replaced in case of bottleneck (i.e., very large number of peers).

Improve space management of array

As already mentioned in issue #3, when you assign a value to an index in the array, the gap are filled with null pointer. For instance array[42]=1337 will fill the array of 41 null value...

Todo: fix by using binary search?

Change the signature of some functions

Function increment() should return a pair < localEntry , newCounter > only to ease the usage.

Following that, whether incrementFrom(ec) is:

• Divided between (e, c) so the user do not have to allocate a pair, or
• Kept as (ec) since increment() will already return the pair required.

IVV: an operation can be 64 operations late max

The interval version vector implementation allows a maximum of 64 operations delay because implemented with numbers.

Use BigInt library to deal with higher delays ?
( Remains unlikely in practice, thus categorized as enhancement )

Use the module "sorted cmp array" + add getters

diff between two structures

add diff between two structures

Somehting like vv1.diff(vv2) would give the missing operations of vv1 compared to vv2. I.e., apply all the operations of the diff on vv1 results in vv2

Auto Increase size of the VVs

Create a data structure with tombstones

Current package includes three kinds of causality tracking. VV tracks all events among all the others. Both IVV and VVwE tracks semantically related event (e.g. 2nd operation of 1st peer depends on the 1st operation of 3rd peer, therefore, the former requires that the latter is delivered before being delivered, and nothing else).

The fourth data structure would be a set (ordered for efficient search) with the unique id of the operation and a time-to-live (TTL). When the TTL is expired, the operation does not exist anymore. Theoretically, it can create consistency problems. Nevertheless, in practice, with a TTL high enough, it does not. Difficult part being to set the value of this TTL.

NB: "tombstones" designation refers to the conflict-free replicated data types. One class of CRDTs keeps the deleted elements in the underlying structure forever (hence called tombstones). Using tombstones allows distinguish elements delivered then deleted, of elements not delivered yet.