crdt-graph

An op-based 2P2P-Graph CRDT implementation in Rust.

Based on the 2P2P-Graph specification from Shapiro et al., "A comprehensive study of Convergent and Commutative Replicated Data Types" (2011).

Overview

A 2P2P-Graph (Two-Phase Two-Phase Graph) is a conflict-free replicated data type that models a directed graph with add and remove operations for both vertices and edges. Each replica maintains four sets:

Updates follow the op-based CRDT model with two phases:

• atSource — Precondition checks executed only on the originating replica.
• downstream — State mutations applied on all replicas (including the source).

Usage

First, define concrete types that implement the required traits:

use crdt_graph::{
    TwoPTwoPAddEdge, TwoPTwoPAddVertex, TwoPTwoPGraph, TwoPTwoPId,
    TwoPTwoPRemoveEdge, TwoPTwoPRemoveVertex, UpdateOperation,
};

type Id = u64;

// -- Vertex add --
#[derive(Clone, Debug)]
struct VA { id: Id }

impl TwoPTwoPId<Id> for VA {
    fn id(&self) -> &Id { &self.id }
}
impl TwoPTwoPAddVertex<Id> for VA {}

// -- Vertex remove --
#[derive(Clone, Debug)]
struct VR { id: Id, add_vertex_id: Id }

impl TwoPTwoPId<Id> for VR {
    fn id(&self) -> &Id { &self.id }
}
impl TwoPTwoPRemoveVertex<Id> for VR {
    fn add_vertex_id(&self) -> &Id { &self.add_vertex_id }
}

// -- Edge add --
#[derive(Clone, Debug)]
struct EA { id: Id, source: Id, target: Id }

impl TwoPTwoPId<Id> for EA {
    fn id(&self) -> &Id { &self.id }
}
impl TwoPTwoPAddEdge<Id> for EA {
    fn source(&self) -> &Id { &self.source }
    fn target(&self) -> &Id { &self.target }
}

// -- Edge remove --
#[derive(Clone, Debug)]
struct ER { id: Id, add_edge_id: Id }

impl TwoPTwoPId<Id> for ER {
    fn id(&self) -> &Id { &self.id }
}
impl TwoPTwoPRemoveEdge<Id> for ER {
    fn add_edge_id(&self) -> &Id { &self.add_edge_id }
}

# fn main() {
// Create two replicas
let mut replica_a: TwoPTwoPGraph<VA, VR, EA, ER, Id> = TwoPTwoPGraph::new();
let mut replica_b: TwoPTwoPGraph<VA, VR, EA, ER, Id> = TwoPTwoPGraph::new();

// Replica A: add vertices (atSource + local downstream)
let op1 = replica_a.prepare(UpdateOperation::AddVertex(VA { id: 1 })).unwrap();
let op2 = replica_a.prepare(UpdateOperation::AddVertex(VA { id: 2 })).unwrap();

// Broadcast to Replica B (downstream)
replica_b.apply_downstream(op1).unwrap();
replica_b.apply_downstream(op2).unwrap();

// Replica B: add an edge
let op3 = replica_b.prepare(UpdateOperation::AddEdge(EA { id: 10, source: 1, target: 2 })).unwrap();
replica_a.apply_downstream(op3).unwrap();

// Both replicas now have the same state
assert!(replica_a.lookup_vertex(&1));
assert!(replica_b.lookup_vertex(&1));
assert_eq!(replica_a.generate_petgraph().edge_count(), 1);
assert_eq!(replica_b.generate_petgraph().edge_count(), 1);
# }

API

Preconditions