W3C CRDT for RDF CG

First meeting

Date: 2024-12-20 14:00UTC
Place: https://meet.jit.si/crdt4rdf

Present

Introductions

Very shortly since we've already done it on the mailing list

  • elf Pavlik: various W3C CGs, for some time Social Web WG, now mostly Solid CG
  • Niko: Working on NextGraph, implementing CRDTs. Also interested in Solid
  • Hala: Distributed Data Management team, from Nantes University. Interested to hear from you about your use cases.
  • Matthieu: Working with Hala and Pascal, more focused on distributed computing. Working on replication, earlier with weak now more with strong consistency.
  • Pascal: Oficer in the GDD team, working on real time editors before Semweb and RDF. Now mostly working on SPARQL engines.
  • Rui: Postdoc working at Oxford university, together with Jesse. Mainly interested how CRDT can play with Solid and LWS. But interested more generally as well.
  • Jesse: Wearing two hats, as a researcher in the EWADA group lead by TimBL and Nigel Shadbolt. In my other role I'm the Solid lead at ODI. Last 5-6 years RDF and Semweb was may life. Not much experience with CRDT but looking to understand better how they can be accomodated by LWS and elsewhere.
  • Jitse: New PhD student at Ghent university, working with Ruben and Peater. I've been develolper in communica. We have set semantics, adding and removing tripples. Wanting to understand the focus of the group.

Topics of interest

[Jitse] I think it's essential we first agree on the scope of the CG.

  1. Do we want a set CRDT over an unordered set of triples/ quads?
  2. Do we want literal scoped CRDTs so its possible to have a text CRDT to edit literals?
  3. Any other possibilities?
    Furthermore, I think we'va all silently assumed operation based CRDTs. If so, let's also mention that specifically?
  • Jitse: In the previous meeting there were many different ideas. Michael from Braid was interested in CRDT where you can edit the values of literals, while Niko was focused on triples.
  • Niko: Michael presented Braid and I presented NextGraph. In NextGraph triple is atomic, you can't edit inside of triple. Braid seems that they want to edit the literal triple of the triple, he didn't clarify how they would handle triples.
  • Niko: My implementation is based on the paper describing SU-Set. I would like to ask the team from France to give us update on their newer work.
  • Hala & Pascal: presenting slides
  • Pascal: We started with read-write linked data. On the web you only have right to write your own resource. If you have to modify something belonging to someone else, how to do that? We found a use case with LinkedCT.
  • Hala: We tried to make a federated query across two sites. The problem was that maintainer of DrugBank has changed the URI. How the user can update …
  • Pascal: Since you don't have a right to change anything at the cannonical origin. User can take the subset from both sites and create a local copy, a partial replication. You can also make an update feed and receive updates, you can also update your local copy. You can also rewrite your query localy and fix the problem.
  • Pascal: Now it is possible to propose the feed to LinkedCT to fix outdated links by accepting the update. It is like a pull-request from github. Once its fixed, user's site is not required any more. You can build some arbitrary networks of pepople who are reading and publishing to any andpoint.
  • Pascal: Two protocols SU-Set has total replication, and Col-Graph has partial replication with different consistency criteria. If you just replicate fragment it is much more difficult. In SU-Set you need to broadcast to all other sites. Updates will be received (niko: eventually), so it is a reliable broadcast.
  • Pascal: We needed to define CRDT that supports SPARQL Update. We needed to define it preserving the semantics.
  • Pascal: SU-Set has its complexities. showing results of benchmarks. You need unique id per operation. One id per triple is costly, one id per operation is more efficient.
  • Pascal: We were not convinced since it was based on total replication. Forcing people to replicate everything might not be very relistic.
  • Hala: Especially broadcasting updates to everyone
  • Pascal: We started Col-graph after that to address partial replication. Where on can only replicate small update
  • Hala: And you don't need to propagate to all the people.
  • Pascal: It makes things much more complex if everyone doesn't sync. You need to track provenance to ensure …
  • Pascal: There are new results that can improve col-graph. I saw new result on provenance rings at the Web conference (2024) in singapore. Using non-monotonic operators …
  • Hala: We need new consistency criteria.
  • Niko: I want to clarify to others, besed on my experience with implementing SU-Set in NexGraph. It doesn't replicate the whole dataset, we only repliate each resource separately. The DAGs do not cross. Operation only updates one resoure / named graph.
  • Niko: You don't have guarantees on the transactions if they are across different named graphs. You can have operations spanning multiple graphs but they will be split into per graph operations. Partial replication is still subject of research, since we have topic of dependencies between updates.
  • Niko: In next graph we are fully consistent within a named graph. It depends what consistency you are looking for.
  • elf Pavlik: So far we only talk about triples, nothing with values of the literals
  • Niko: French team also works on that.
  • Pascal: You can start combining text in the triple but it could be deleted in between etc. Does someone have a use casse?
  • Rui: Talking about triples and literals. How is that related to schema. For example we often have schema for individuals we are talking about. Sometimes we are removing some properties and adding other things. Would that be a problem if the discussion is only about triples?
  • Rui: Let's say I describe a person and change two properties together, I want them to be like a transaction, either both happen or not.
  • Pascal: In CRDT you need to create a new operation, that captures the constraint between two things.
  • Matthieu: The updates are not comutative, they are overwriting. Non comutative are harder to solve.
  • Pascal: Update is not the same as remove followed by insert.
  • Matthieu: If you want to replace x by y and someone wants to replace x with z, you may end up with both.
  • Rui: Is it difficult to prove new operation.
  • Matthieu: It is not a proof but finding the algorithm is hard.
  • Niko: It is hard to ensure consistency given that order of operations can be different.
  • Jitse: Imagine that you have a dataset conforming to a shape, someone makes an update that still conforms, another one conforms as well. What if two operations together do not conform.
  • Pascal: It is hard converge to ensure constraints at the same time.
  • Hala: I was working with XML schema. There could be some idea.
  • Pascal: If you want to ensure constraints, you may need to drop operations. Everyone doesn't want to loose operations and respect constraints at the same time. I might not be possible to have both.
  • Matthieu: There are algorithms but they are very expensive, they keep the full log and they try to redo when problems occur.
  • Niko: When I bump into that, I have a consensus mechanism in addition which I fallback to when I dont' have solution. But they need to be online so you loose the offline capability.
  • Pascal: For the CG we have to be very clear for the use case. What scenarios do we want to achieve. Once we have clear use cases we can imagine solutions.
  • elf Pavlik: Maybe at some point there need to be some kind of non automated step comparable to 'merge commit' resolving conflict.
  • Niko: I think bergos is using Raft as a consensus mechanism but that breaks guarantees and has to be online. I use CRDT as the basis and use coordination in worst cases like permissions, changing schemas etc.
  • Pascal: So what is the simplest use case? Wikidata, Soild?
  • Niko: It could be mostly for Solid, in NextGraph we have concurent edits in one document at the time. It can synchronise and converge to the same data.
  • Pascal: So you see rdf graphs as documents?
  • Niko: In NextGraph named graph and document is the same.
  • Pascal: Is it application?
  • Niko: It is more of a framework that allows developers to build any kind of application.
  • Pascal: I worked with people who make buildings. So different partners could share buildings and resynchronise?
  • Niko: If data is expressed as RDF yes.
  • Pascal: Yes they have specialized ontologies.
  • Niko: As long as they collaborate on the same documents. Similar to having the same triple store with sparqld updates. But in NextGraph it works offline. Soild is focused on client-server and updates always happen to the server that needs to be online.
  • Jitse: I work on communica, the idea is that you could use it to update and read to Solid pod. The idea is that you could update in your local storage and later synchronise with the server.
  • Jitse: Communica is a SPARQL query engine, which is modular and there is also build for Solid, where you gather all the resources. It is a javascript library.
  • Niko: Communica sounds in many ways similar to nextgraph.
  • Pascal: Communica sounds like sparql engine, do you want to materialize the views and later do the updates?
  • Niko: it is in memory
  • Pascal: Is it a construct query?
  • Jitse: You get mapping, it focuses to do federated queries. Depending on the interface it uses diffent actor to query it.
  • Niko: It aggregates data locally and then runs sparql on that local data?
  • Jitse: There is an aggregated build that uses communica. Communica itself can fetch links and collect document into a local store. It currently doesn't have a good support for updates.
  • Niko: So it is mostly read only.
  • Jitse: Practically no updates.
  • Pascal: It sounds to me like a view maintenance. You need updates to make CRDT interesting. Otherwise it is incremental view maintenance which is well know in databases.
  • Jitse: For communica we want to have updates, that's why we are looking at CRDTs.
  • Pascal: …
  • Niko: I don't know how Wikidata is doing the part of collaborative editing. I don't expect to give solutions to this kind of problems. In NexGraph there is permission system and you know who can edit things. I don't try to solve it for global open linked data. Solid is also more about personal data. The apps run locally on the device and it is nice to be alble to support apps running offline.
  • Jitse: Is the idea of this gruop to find solutions for CRDT within Solid? We are looking at use cases. It reminds me of comment made by Hala about replicating the whole datasets. In Soild most web resources are rather small and they can be compleately duplicated.
  • Niko: …
  • Pascal: If you multiply the graph with CRDT, you may want to query the whole graph in one query. If you look for a difference in the graph.
  • Hala: If you have a replica you may want to choose only some trusted sources.
  • Niko: In LDES you have stream of updates, you don't have conflict resolution but you can still update.
  • Jitse: I'm not that focused on LDES https://tree.linkeddatafragments.org/linked-data-event-streams/
  • …: It has conflict resulution as last write wins
  • Niko: … You need reliable broadcast, I came up with one in NextGraph.
  • Pascal: Maybe reliable is not enough, causal is better?
  • Niko: Causal reliable broadcast. It as a pub-sub that enforces causality. It reades the DAG and enforces the order of commits.

Use cases

[Niko] I am listing here some topics I would like to expand with you all during this call (if time allows) and maybe in the subsequent calls. Please feel free to add your interests and expectations here below too, and to mark if you are also interested in the same or not.

  • Conflict Resolution Mechanism for RDF: how many exist? I am using SU-Set, do we want to dig more into it? Is there some alternative? m-ld mentionned some consensus mechanisms like Raft, which are not eventual consistent, but maybe there is an interest for that too?
  • sync protocols: what are the options? I developed a protocol based on the BEC paper of Kleppmann et al. What are the alternatives? do we want more details about NGProto and the associated DID method?
  • about blanknodes, I use skolemization. Other opinions? (Pieter Colpaert: both skolem IRIs as blank nodes must be supported, no?)
  • RDF CRDT and Solid: how can they integrate? What are the options? I recently wrote a use-case for the LWS WG (Linked Web Storage) that will take over the finalizing of the Solid specs. I proposed and presented the need for abstraction and decoupling. What do you think? The question of using HTTP for synchronizing updates has also been mentionned (BRAID etc)
  • on the more general topic of source selection, distribution and federation of datasets (TREE, LDES, SEMIC, DeKaloG, FedUP) which are not exactly about CRDT but are related, do we want to dig more on those subjects and how? (Pieter Colpaert: I would really try to start from the smallest scope possible with this group, and only expand from the moment the base document on this small scope is somewhat usable)

bergi: Three layers/specifications

  • Transport: What goes over the wire
  • Algorithm: The logic a client must implement
  • API: Abstraction Layer like rdf-dataset-changelog for RDF/JS

CG Draft Reports

Can we see any potential proposals?

CG Chairs

This way we will be able to add future meetings to the CG calendar.

  • Jesse: Couple of observations, not to be throwing anyone under the bus bus, but @niko and @elfpavlik seemed to somewhat emerge as leaders during this call - and in the creation of this WG. I would promote you as chairs.
Select a repo