Home

Awesome

range_reconcile

A module for the efficient reconciliation of sets. This is a TypeScript implementation of range-based set reconciliation as described in Aljoscha Meyer's master thesis.

In this method peers generate fingerprints for ranges of items they hold in a totally ordered set.

When two ranges from different peers hold the same items, they produce the same fingerprint.

But when two ranges are different from one another, they produce different fingeprints. The two peers then subdivide non-matching ranges, generating and comparing fingerprints until the ranges are whittled down to the disjoint elements, which are then exchanged.

About this implementation

This implementation has the following features:

One caveat: the FingerprintTree provided by this module can only store its values in memory.

Using this moudule

Outline

At the broadest level:

  1. For each set you wish to reconcile, instantiate a FingerprintTree and insert that set's elements.
  2. Create a RangeMessenger for each FingerprintTree.
  3. Reconcile the sets by exchanging messages between two RangeMessengers.

Detailed usage

Importing

import {
  FingerprintTree,
  RangeMessenger,
} from "https://deno.land/x/range_reconcile/mod.ts";

Or install the NPM module:

npm install range-reconcile

FingerprintTree

The FingerprintTree is used as the representation of a set you wish to reconcile. Instantiation requires a 'lifting monoid' to be provided, and optionally a function with which to compare inserted values.

This lifting monoid is important because it is used to generate the fingerprints which peers exchange and compare their own fingerprints to.

Therefore the lifting monoid must satisfy the following criteria:

  1. The lift method must map every item that could possibly occur in a set to a value from the monoid, that is, to a value that can be combined with other such values according to the next two rules. lift(item) is the fingerprint of the set that contains only item. For larger sets, the fingerprint is computed by combineing the results of lift(item) of all the individual items in the larger set. Doing so efficiently is done by the tree behind the scenes.
  2. The combine method must be associative — i.e. combine(a, combine(b, c)) === combine(combine(a, b), c)
  3. The neutral value must be a value from the monoid that leaves other (monoid) values unaffected when combining them with it: combine(a, neutral) === a and combine(neutral, a) === a.

RangeMessenger

Once you have a FingerprintTree containing the values you wish to reconcile, you can instantiate a RangeMessenger which generates the messages for another peer.

This RangeMessenger requires a configuration which describes how to decode and encode messages from and to the other peer respectively.

Once instantiated, the initial messages to send to the other peer can be generated with the initialMessages method.

Upon receiving a message, it should be passed to RangeMessenger.respond, which returns the response to be sent back in turn.

How messages are sent and received is up to you. Just make sure that whichever system you choose sends and processes the messages in order (i.e. first-in, first-out).

Development

This module uses Deno as its development runtime. Installation instructions can be found here.

API documentation can be viewed with deno doc mod.ts.

Tests can be run with deno task test.

Benchmarks can be run with deno task bench.

Acknowledgements

TODO: