README
JavaScript Interval Tree Clock Library
This is a JavaScript implementation of Interval Tree Clock as described in itc2008
Interval Tree Clocks (ITC) is a novel causality tracking mechanism that generalizes both Version Vectors and Vector Clocks.
Causality tracking is modeled by a set of core operations: fork, event and join, that act on stamps (logical clocks).
Causality is characterized by a partial order over the event components of stamps.
There are 3 basic operations over a stamp:
fork The fork operation allows cloning of the causal past of a stamp, resulting in a pair of stamps that share causal past.
event An event operation adds a new event to the event component, so that if s1 results from event(a) the causal ordering is such that s < s1. This action does a strict advance in the partial order such that s1 is not dominated by any other entity and does not dominate more events than needed.
join This operation merges two stamps, producing a new one. If join((i1,e1), (i2,e2)) = (i3,e3), the resulting event component e3 should be such that e1 ≤ e3 and e2 ≤ e3.
Installation
$ npm install --save itc-js
API
Creating a new stamp
A new stamp is only created upon instantiating of a new history of events, e.g. upon creating a new replica set.
const Stamp = require('itc-js').Stamp
let a = new Stamp()
// a.toString() === '(1: 0)'
Forking
A stamp can be forked by calling a fork() method on a stamp. The stamp's casual history then splits into 2 parts, a stamp with one of them is returned as the result of the fork():
const Stamp = require('itc-js').Stamp
let a = new Stamp()
// a.toString() === '(1: 0)'
let b = a.fork()
// a.toString() === '((1,0): 0)'
// b.toString() === '((0,1): 0)'
Stamping
Use event() method to record an event in the stamp's history.
const Stamp = require('itc-js').Stamp
let a = new Stamp()
let b = a.fork()
b.event()
// b.toString() === '((0,1): (0,0,1))'
Joining
Use join() method to join stamps:
const Stamp = require('itc-js').Stamp
let a = new Stamp()
let b = a.fork()
b.event()
b.event()
a.join(b)
// a.toString() === '((0,1): (0,0,2))'
Example
const Stamp = require('itc-js').Stamp
let a = new Stamp()
// a.toString() === '(1: 0)'
let b = a.fork()
// a.toString() === '((1,0): 0)'
// b.toString() === '((0,1): 0)'
a.event()
// a.toString() === '((1,0): (0,1,0))'
b.event()
// b.toString() === '((0,1): (0,0,1))'
let c = a.fork()
// c.toString() === '(((0,1),0): (0,1,0))'
b.event()
// b.toString() === '((0,1): (0,0,2))'
a.event()
// a.toString() === '(((1,0),0): (0,(1,1,0),0))'
b.join(c)
// b.toString() === '(((0,1),1): (1,0,1))'
// c.toString() === '(((0,1),0): (0,1,0))'
let c = b.fork()
// c.toString() === '((0,1): (1,0,1))'
// b.toString() === '(((0,1),0): (1,0,1))'
a.join(b)
// a.toString() === '((1,0): (1,(0,1,0),1))'
// b.toString() === '(((0,1),0): (1,0,1))'
a.event()
// a.toString() === '((1,0): 2)'
// b.toString() === '(((0,1),0): (1,0,1))'
// c.toString() === '((0,1): (1,0,1))'
Comparing stamps
To compare stamps use leq method of a stamp. This method returns true if given stamp is strictly before the one in the argument, false otherwise.
const Stamp = require('itc-js').ImmutableStamp
let a = new Stamp()
// a.toString() === '(1: 0)'
let [a1, b1] = a.fork()
// a1.toString() === '((1,0): 0)'
// b1.toString() === '((0,1): 0)'
let b2 = b1.event()
// b2.toString() === '((0,1): (0,0,1))'
b1.leq(b2) // true
Immutable stamps
You can also use immutable stamps if you want to enforce strict immutability.
The API of immutable stamps is slighly different:
const Stamp = require('itc-js').ImmutableStamp
let a = new Stamp()
// a.toString() === '(1: 0)'
let [a1, b] = a.fork()
// a1.toString() === '((1,0): 0)'
// b.toString() === '((0,1): 0)'
let a2 = a1.event()
// a2.toString() === '((1,0): (0,1,0))'
let b1 = b.event()
// b1.toString() === '((0,1): (0,0,1))'
let [a3, c] = a2.fork()
// c.toString() === '(((0,1),0): (0,1,0))'
let b2 = b1.event()
// b2.toString() === '((0,1): (0,0,2))'
let a4 = a3.event()
// a4.toString() === '(((1,0),0): (0,(1,1,0),0))'
let b3 = b2.join(c)
// b3.toString() === '(((0,1),1): (1,0,1))'
// c.toString() === '(((0,1),0): (0,1,0))'
let [b4, c1] = b3.fork()
// c1.toString() === '((0,1): (1,0,1))'
// b4.toString() === '(((0,1),0): (1,0,1))'
let a5 = a4.join(b4)
// a5.toString() === '((1,0): (1,(0,1,0),1))'
// b4.toString() === '(((0,1),0): (1,0,1))'
let a6 = a5.event()
// a6.toString() === '((1,0): 2)'
// b4.toString() === '(((0,1),0): (1,0,1))'
// c1.toString() === '((0,1): (1,0,1))'
License
Licensed under MIT License. Copyright 2018 Coldrift Technologies B.V. All rights reserved.