Elixir language support

[fire]

What's a series of steps to get started on a compatible version of braid or antimatter in Elixir?

Looking for a step by step guide.

[toomim]

Cool! What do you want to build?

Do you want:

• A braid-http protocol implementation?
• An antimatter pruning algorithm for any crdt?
• A particular crdt, like sync9, with an antimatter implementation as well?
• A library to make it easy to build apps on top of braid-http and a crdt?

These things are all different and will have different steps. If you could describe a little more context I could probably help you out.

[fire]

I'll describe the problem.

We wanted to merge game world scenes which represent changes to a tree structure in Godot Engine (C++) to allow from 1 to 1000 players to be in the same place—possibly fissioning into different islands.

I also have Mixer, which provides a Blender to Blender bridge and eventually a Blender to Godot Engine bridge. This python script module is called broadcaster.

Looking at your descriptions, it feels like a direct CRDT / antimatter implementation with the properties of merging, deleting subtrees, and history collapsing is the closest path.

I hesitate to say this is HTTP only because games tend to only use HTTP for authentication/authorization and restore large states. The other uses like VOIP and transform interpolation require a quality of services that are UDP based. So the two protocols that constrain my choices are webrtc and enet.

I'd make the Godot engine proposal first if it is more straightforward, but the multiplayer Blender one is also useful to all.

1. https://github.com/fire/mixer/tree/fire/broadcaster
2. Elixir
3. https://membraneframework.org/ allows both native code (c++) integration and a sink/source/filter pipeline architecture.

Similar projects

I believe that jel https://github.com/jel-app uses OT and sharedb to provide these properties with voxels.

See also https://github.com/ottypes/json1

[toomim]

Thank you very much! That context is very helpful.

I think @dglittle would be helpful for you here. He has been building a CRDT called Shelf that merges trees of JSON, is very efficient, and requires only 90 lines of code.

I'll get him in touch.

[toomim]

Oh, and @siliconjungle might be interested, too.

[dglittle]

fire, toomim: hello! I have read through the comments so far -- I'm happy to help how I can! If you like, fire, I'm willing to zoom chat with you and explain how these CRDTs work.. I think at the end of the day, the first step toward implementing any of this stuff in Elixir is to understand what's going on algorithmically.

[toomim]

Let me be more explicit. @fire, you probably don't need all the power of antimatter, because if your core issue is merging subtrees of JSON, then you can do that with a simpler CRDT that doesn't require history in the first place.

Antimatter is solving for the harder case in synchronization algorithms (both OT and CRDT) of merging simultaneous edits to a sequence of data (e.g. collaboratively editing a string of text of an array). But if your data is just a tree of JSON like:

{
  a: {
    b: {
      c: false,
      d: 8
      e: null
    },
    f: true
  },
  g: {h: 3}
}

...and all you do is create, replace, and delete values, then you can create a consistent p2p synchronized data structure without maintaining as much history in the first place. All you need is to store an additional integer of metadata along with each node in the JSON tree, and whenever any two nodes conflict, you choose the node with the higher (or lower) integer.

This is what shelf does. You can also find some explanations of shelf here:

• https://www.npmjs.com/package/@glittle/shelf
• https://braid.org/algorithms/shelf
• https://braid.org/meeting-8
• https://braid.org/meeting-6
• https://braid.org/meeting-11
• https://braid.org/meeting-12
• https://braid.org/meeting-31

I'd check that out and see if it does what you need. You can store arrays in a shelf but you can't merge changes that insert/delete sections or change the arrays' lengths; only replace entries. (You can likewise store and replace entire strings, but not "edit" them.) This tends to be what you need for games. Both @dglittle and @siliconjungle have built simple games on top of shelves. @pkulchenko also built an implementation in Lua.

If you do need a more robust OT/CRDT synchronizer that stores actual history, then antimatter would totally be useful and I'd be very happy to help you with that, but I want to make sure you're solving the actual problem you have.

[siliconjungle]

@fire I'd be happy to chat through some things as well. Depending on your exact needs, you may be able to get away with a super simple key/value store of last writer wins registers (a version per object, with user id's as tie breaker's).

[fire]

Godot models its scenes as a tree of nodes with an unordered list of properties that are the Variant Godot Engine type.

You are advising I can solve most of the problem by the incrementing integer version (shelf) of the property overwriting the last one:

I'll try that.

Will try to describe a problem where I do need the full power though.

[fire]

@siliconjungle Let me know when's a good time. I want to do some homework on the problem, but not long enough to be stuck.

[siliconjungle]

Godot models its scenes as a tree of nodes with an unordered list of properties that are the Variant Godot Engine type.

You are advising I can solve most of the problem by the incrementing integer version (shelf) of the property overwriting the last one:

I'll try that.

Will try to describe a problem where I do need the full power though.

I think there are a few main things that would be worth thinking about:

• Does each property need to be able to be versioned separately? Does it make sense to do that at the component level? Or maybe even the game object level? This question really comes down to the level of granularity you need for your merging. For some things you may want to group all changes to a component together.
• Do you need to support transactions? e.g. grouping together changes to many different components simultaneously.
• Do you need to support history? To what degree?
• Will you need to support references & re-parenting? I imagine in a scene graph you would. So it may pay to separate the CRDT definitions from the "tree" data type. So that the tree is a versioned set of pointers to objects in memory.

Happy to chat whenever - I am in AEST timezone though so, keep in mind reasonable hours.

[fire]

The type hierarchy is:

Everything is a Variant. A Node (scene graph) pointer is a Variant. A reference / resource (savable) is a variant. Primitives like Vector3 or Transform is a Variant. Custom non primitives types are typed Object, also a variant.

I can model the Variant as a json document with an unordered list of properties that can be _set or _get and can query their types. A scene is a series of Nodes that have a hierarchical parent-child relationship.

Godot Engine described a network replication algorithm where the scene is replaced by a binary byte array which can be modeled here as editing a valid json document. However, this requires a custom definition of the mapping which can be configuration time consuming.

We've done a network protocol where the hierarchy is one layer deep and parenting is done as a node that describes faux parenting. This is equivalent to scenes represented by a byte array in a ordered list. I think it's ordered.. However this is not the full Godot SceneTree.

I think we can get away with not having history. I suspect it's required for transactions.

separate the CRDT definitions from the "tree" data type

Separate the CRDT from the tree is an interesting path to pursue. It reminds of the blockwise versions of the CRDT / OT algorithms in the literature.

I checked your time in Austalia and it's midnight. I'll try to catch you in 12 hours. 👍

[fire]

I got distracted and had to change plans. What are some async ways to contact. I list some addresses at https://chibifire.com/.

[fire]

The V-Sekai model is that each client has set of entities. Each entity is a set of properties. Each entity can be parented to one parent. When client Alice connects to a relay, the relay shares the data with Bob and Carol.

Relays

1. There can be many relays.
2. Each relay has a capacity

Rules

1. Client has ownership and mastery.
2. Ownership determines default rules to change entity properties (allow, deny, ask (default deny))
3. The last person who is the owner is the one who determines the current state of everything they own. -> If this causes too many issues we will define a different state conflict resolution method at a later date
4. State interpolation can be nearest, linear or cubic.

Properties

Interpolation is hard for strings, but easier for geometrical values.

@MalekiRe