README.md

g# riblt-rust Rust port of RIBLT library by yang1996.

Implementation of Rateless Invertible Bloom Lookup Tables (Rateless IBLTs), as proposed in paper Practical Rateless Set Reconciliation by Lei Yang, Yossi Gilad, and Mohammad Alizadeh. Preprint available at arxiv.org/abs/2402.02668.

Library API

To use this library, implement a Symbol trait, and create Encoder or Decoder objects to encode and decode symbols.

Symbol trait

• fn zero() -> Self - Create a zero symbol.
• fn xor(&self, other: &Self) -> Self - XOR of this symbol and another symbol.
• fn hash(&self) -> u64 - Calculate a hash of the symbol.

Example implementation for 64-bit integer symbols:

use riblt::*;
use std::hash::{SipHasher, Hasher};

pub type MyU64 = u64;

impl Symbol for MyU64 {
  fn zero() -> MyU64 {
    return 0;
  }

  fn xor(&self, other: &MyU64) -> MyU64 {
    return self ^ other;
  }

  fn hash(&self) -> u64 {
    let mut hasher = SipHasher::new_with_keys(123, 456);
    hasher.write_u64(*self);
    return hasher.finish();
  }
}

Encoder methods

• Encoder::<T>::new() - Create a new Encoder for symbols of type T.
• enc.reset() - Reset the Encoder state.
• enc.add_symbol(symbol: &T) - Add a new symbol to the Encoder.
• enc.produce_next_coded_symbol() -> CodedSymbol<T> - Produce the next coded symbol that can be decoded by the Decoder.

Example usage

use riblt::*;

fn foo() {
  let mut enc                  = Encoder::<MyU64>::new();
  let     symbols : [MyU64; 5] = [ 1, 2, 3, 4, 5 ];
  for x in symbols {
    enc.add_symbol(&x);
  }

  let coded = enc.produce_next_coded_symbol();

  // send symbol to the decoder...
}

Decoder methods

• Decoder::<T>::new() - Create a new Decoder for symbols of type T.
• dec.reset() - Reset the Decoder state.
• dec.add_symbol(symbol: &T) - Add a new symbol to the Decoder.
• dec.add_coded_symbol(symbol: &CodedSymbol<T>) - Add a new coded symbol to the Decoder.
• dec.try_decode() - Try to decode added symbols. May returns Err(InvalidDegree).
• dec.decoded() - Returns true if all added coded symbols where decoded.
• dec.get_remote_symbols() -> Vec<HashedSymbol<T>> - Returns an array of decoded remote symbols.
• dec.get_local_symbols() -> Vec<HashedSymbol<T>> - Returns an array of local symbols.

Remote and local symbols can be accessed directly via Decoder properties:

• dec.remote.symbols,
• dec.local.symbols.

Example usage

use riblt::*;

fn foo() {
  let symbols : [CodedSymbol<MyU64>; 5] = ...;

  let mut dec = Decoder::<MyU64>::new();
  for i in 0..symbols.len() {
    dec.add_coded_symbol(&symbols[i]);
  }

  if dec.try_decode().is_err() {
    // Decoding error...
  }

  if dec.decoded() {
    // Success...
  }
}

For the complete example see test example in src/tests.rs.

---

Distributed WAL Synchronization Example

The binary in this project demonstrates a multi-phase log reconciliation between distributed nodes.

1. Start Two Nodes

Open two terminals and launch a node in each:

Terminal 1 (Node A):

cargo run -- --id A --port 8000

Terminal 2 (Node B):

cargo run -- --id B --port 8001

2. Append Data

Add unique entries to each node's log:

To Node A:

cargo run -- --id A --port 8000 --append "Entry from Alice"

To Node B:

cargo run -- --id B --port 8001 --append "Entry from Bob"

3. Synchronize

Trigger the reconciliation from Node A:

cargo run -- --id A --port 8000 --sync-with 8001

The nodes will:

1. Reconcile Checkpoints (bucket hashes) to find mismatching log segments.
2. Reconcile Individual Entries within those segments.
3. Fetch the actual text payloads for missing entries.

4. Running Automated Tests

The full reconciliation logic is verified by an integration test:

Trigger the reconciliation from Node A:

cargo run -- --id A --port 8000 --sync-with 8001

The nodes will:

1. Reconcile Checkpoints (bucket hashes) to find mismatching log segments.
2. Reconcile Individual Entries within those segments.
3. Fetch the actual text payloads for missing entries.

4. Running Automated Tests

The full reconciliation logic is verified by an integration test:

cargo test --test sync_test -- --nocapture

For a detailed technical breakdown of the protocol and data structures, see Spec.md.