Skip to main content
Module

x/range_reconcile/mod.ts

Efficiently sync sets with range-based set reconciliation
earthstar-project/range-reconcile
Latest
import * as rangeReconcile from "https://deno.land/x/range_reconcile@1.0.2/mod.ts";

Tools for efficient reconciliation of sets. This is an implementation of range-based set reconciliation as described in Aljoscha Meyer's master thesis (https://github.com/AljoschaMeyer/master_thesis).

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.

Reconciliation can be conducted locally or over a network. This library does not have any opinion on message encoding or transport. Users provide these details themselves. Currently the FingerprintTrees are only persisted in memory.

Classes

A node for a FingerprintTree, augmented with a label and lifted value. Can update the labels of its ancestors.

A self-balancing tree which can return fingerprints for ranges of items it holds using a provided monoid.

Produces and responds to messages, enabling efficient reconciliation of two sets.

Variables

A monoid which lifts the member as a string, and combines by concatenating together.

A monoid which lifts the member as 1, and combines by adding together.

Functions

Combine two lifting monoids into a new one.

Execute a complete exchange between two RangeMessengers, syncing their trees.