Vector/Matrix in a CRDT

[JMLX42]

Hi there!

I am working on a new version of the open source SmartShape Engine written 100% in Rust using wgpu.

One of the main features I am investigating is making the new engine data driven + collaborative in a decentralized way. For example, if a user changes the color of an object, that object would change color for all the other users.

Here is an example that uses some WASM properties to synchronize the state of the WASM modules between multiple instances: https://twitter.com/kettlecorn/status/1620567336704180225 It's very low level and transparent. But IMHO it does cover the elephant in the room for larger projects: consistency and concurrency.

So I am trying to use CRDTs instead. The goal is to store the entire state of the 3D application in a CRDT and communicate the CRDT operations on the network to synchronize that state along multiple instances.

To do that, I need to store things like Vector and Matrix in such CRDT. I have started working with the crdts crate. To implement the state as a crdts::Map<uuid::Uuid, crdts::Orswot<String, Value>, Value>. In order for this to work, Value must implement:

• Hash
• PartialEq
• Eq
• PartialOrd
• Ord

Implementing Eq and PartialEq and Hash

I leveraged the ordered_float crate to have comparable/hashable floats:

type Float32 = ordered_float::OrderedFloat<f32>;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Value {
    I32(i32),
    I64(i64),
    U32(u32),
    U64(u64),
    F32(Float32),
    Vec2i(Vector2<i32>),
    Vec3i(Vector3<i32>),
    Vec4i(Vector4<i32>),
    Vec2u(Vector2<u32>),
    Vec3u(Vector3<u32>),
    Vec4u(Vector4<u32>),
    Vec2f(Vector2<Float32>),
    Vec3f(Vector3<Float32>),
    Vec4f(Vector4<Float32>),
    Mat2x2f(Matrix2<Float32>),
    Mat2x3f(Matrix2x3<Float32>),
    Mat2x4f(Matrix2x4<Float32>),
    Mat3x2f(Matrix3x2<Float32>),
    Mat3x3f(Matrix3<Float32>),
    Mat3x4f(Matrix3x4<Float32>),
    Mat4x2f(Matrix4x2<Float32>),
    Mat4x3f(Matrix4x3<Float32>),
    Mat4x4f(Matrix4<Float32>),
}

IMHO it makes sense and it builds fine. So I expect this choice to work OK with the rest of the nalgebra API.

Am I missing something?

Implementing Ord and PartialOrd

This is where things get tricky: it does not make much mathematical sense to sort/compare vectors or matrices. But my understanding is that is does not have to make sense mathematically as long as it is consistent from a data point of view.

Thus, I am using Vector::norm() and Matrix::norm() to compare Value:

impl Value {
    pub fn norm(&self) -> f32 {
        match self {
            Value::I32(v) => *v as f32,
            Value::I64(v) => *v as f32,
            Value::U32(v) => *v as f32,
            Value::U64(v) => *v as f32,
            Value::F32(v) => cast::<Float32, f32>(*v),
            Value::Vec2i(v) => cast::<Vector2<i32>, Vector2<f32>>(*v).norm(),
            Value::Vec3i(v) => cast::<Vector3<i32>, Vector3<f32>>(*v).norm(),
            Value::Vec4i(v) => cast::<Vector4<i32>, Vector4<f32>>(*v).norm(),
            Value::Vec2u(v) => cast::<Vector2<u32>, Vector2<f32>>(*v).norm(),
            Value::Vec3u(v) => cast::<Vector3<u32>, Vector3<f32>>(*v).norm(),
            Value::Vec4u(v) => cast::<Vector4<u32>, Vector4<f32>>(*v).norm(),
            Value::Vec2f(v) => cast::<Vector2<Float32>, Vector2<f32>>(*v).norm(),
            Value::Vec3f(v) => cast::<Vector3<Float32>, Vector3<f32>>(*v).norm(),
            Value::Vec4f(v) => cast::<Vector4<Float32>, Vector4<f32>>(*v).norm(),
            Value::Mat2x2f(v) => cast::<Matrix2<Float32>, Matrix2<f32>>(*v).norm(),
            Value::Mat2x3f(v) => cast::<Matrix2x3<Float32>, Matrix2x3<f32>>(*v).norm(),
            Value::Mat2x4f(v) => cast::<Matrix2x4<Float32>, Matrix2x4<f32>>(*v).norm(),
            Value::Mat3x2f(v) => cast::<Matrix3x2<Float32>, Matrix3x2<f32>>(*v).norm(),
            Value::Mat3x3f(v) => cast::<Matrix3<Float32>, Matrix3<f32>>(*v).norm(),
            Value::Mat3x4f(v) => cast::<Matrix3x4<Float32>, Matrix3x4<f32>>(*v).norm(),
            Value::Mat4x2f(v) => cast::<Matrix4x2<Float32>, Matrix4x2<f32>>(*v).norm(),
            Value::Mat4x3f(v) => cast::<Matrix4x3<Float32>, Matrix4x3<f32>>(*v).norm(),
            Value::Mat4x4f(v) => cast::<Matrix4<Float32>, Matrix4<f32>>(*v).norm(),
        }
    }
}

impl PartialOrd for Value {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Value {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        if self.norm() == other.norm() {
            Ordering::Equal
        } else if self.norm() > other.norm() {
            Ordering::Greater
        } else {
            Ordering::Less
        }
    }
}

Again, I know that makes no mathematical sense. But I don't actually intend to actually sort/compare Vector and/or Matrices in my code to compute anything (I might even find a way to make sure Ord and PartialOrd are not visible/usable outside of the CRDT interface). I just need this traits implemented so the CRDT can sort the values.

Does it make sense to use the norm here?

[JMLX42]

I guess my point is: how can I test this properly/thoroughly to make sure the required CRDT and Vector/Matrix properties are indeed preserved.