57 ms·

So the primary reason of CRDTs is to enable offline editing? The issue is, I don't think CRDTs will help with offline editing either. If the user edits are day

So the primary reason of CRDTs is to enable offline editing? The issue is, I don't think CRDTs will help with offline editing either. If the user edits are days / weeks behind and the documents have severely diverged, then merging two documents becomes less of a theoretical logic problem and more of a pragmatic domain-specific problem that might even require the input of the user (like a merge-tool). CRDTs will ensure that the output is deterministic and correct, but it will not guarantee how "natural" or "reasonable" the output will look, and I think you would have to eventually use a bunch of clever heuristics or even provide a mergetool for the user to cleanly resolve differences.

jitl 5y ago
> offline editing I guess, offline is relative? Most games I play consider >300ms ping to be offline, but I should be able to edit a document with >300ms ping. That said, a lot of CRDT research is focused on totally local, peer to peer editing. > it will not guarantee how "natural" or "reasonable" the output will look I don’t think your assumptions are correct. CRDT algorithms designed for text structures like those used by Automerge (RGA) or Y.js (YATA) do a good job preserving user intent even for concurrent edits to a text. Users won’t end up with the letters in a sentence interleaved, and it’s actually pretty rare in to encounter concurrent insertions at the same position - those are the most troublesome for both time complexity and intention preservation. Most other kinds of document edits - like edits on a order of paragraph items - are much easier.
- whizzter 5y ago
  Everything is "possible" in terms of mapping but CRDT's requires one to reformulate problems and it makes a whole lot of things more complicated without really solving GAME sort of problems. That said I think games are in many cases behind (except fighting games because they care a bit more about outcome accuracy), I think a big part of it is that most rely on pre-made physics systems that might be impressive at rolling around particles and ragdolls but are not designed for multiplayer games to the slightest so they kinda start blowing up when you start mucking around with their states (I suspect this is why fighting games are ahead imo since they often has bespoke essentially 2d sims). I actually implemented a coop multiplayer prototype over WebSockets for a wolf-style raycasting FPS game I had made for 7dfps that was based on OT (like many fighting games are). It's fairly simplistic (if you bring over the collision and physics work inside the OT simulation). OT was a good choice since it would eliminate desynchronization issues, and since I was using websockets that are reliable and but can have some lag getting things reliable from the get-go was a better option. --- 1: The server runs a single truth state a second or so back in time (sent over to clients upon connection). The server never re-simulates anything (clients will, see below) 2: The server keeps a log of events back to the truth cutoff point, once the truth cutoff is passed they're not needed by the server anymore (unless some laggy client hasn't received them yet, but if that clients goes too far behind it should be dropped so no issues for the server about overflowing). 3: Upon connecting clients synchronize time with the server before receiving state and all existing messages. 4: New game states are produced immutably from the previous (with any messages tied to the point in time). 5: When shooting,etc the client sends a timestamped message to the server, the server MIGHT elect to discard or re-time any message a client sends before logging and broadcasting (this is why the time synchronization earlier was important, clients should be created at the "now" point in time or might be re-timed by the server to deter hacking). 6: A client keeps all states between the truth and now, the server will inform clients as the truth moves forward in time so they can discard old states, any message can come from the server as being timed between truth and now and all "old" messages causes a rebuild of states between the message time and "now" (The "now" state is what we display to the user) 7: A client display-cache synchtonizes with "now" and renders, if a server sent "old" messages that caused an enemy to change direction back in time the cache will handle tweening or snapping (and this is totally separated from the simulation). Since the client created a message at "now" it would've been sent directly to the display cache (and triggered immediate feedback to the user), past changes by the server can undo things (f.ex. if you just died before shooting) but handling that smoothly is not related to the simulation code that can remain clean but rather the display cache handler. --- Sadly I only did this as a side-project and some contracts took over so it's been kinda bit-rotting after I left it mid-refactor (it was kinda messy and tied to the game it was written for), but the architecture felt quite stable once working (one minor issue might is that it works best with fixed-point math due to floating point numbers potentially diverging, even if gradual checkpoints by the server could be introduced).

jitl 5y ago

> offline editing I guess, offline is relative? Most games I play consider >300ms ping to be offline, but I should be able to edit a document with >300ms ping. That said, a lot of CRDT research is focused on totally local, peer to peer editing. > it will not guarantee how "natural" or "reasonable" the output will look I don’t think your assumptions are correct. CRDT algorithms designed for text structures like those used by Automerge (RGA) or Y.js (YATA) do a good job preserving user intent even for concurrent edits to a text. Users won’t end up with the letters in a sentence interleaved, and it’s actually pretty rare in to encounter concurrent insertions at the same position - those are the most troublesome for both time complexity and intention preservation. Most other kinds of document edits - like edits on a order of paragraph items - are much easier.

whizzter 5y ago
Everything is "possible" in terms of mapping but CRDT's requires one to reformulate problems and it makes a whole lot of things more complicated without really solving GAME sort of problems. That said I think games are in many cases behind (except fighting games because they care a bit more about outcome accuracy), I think a big part of it is that most rely on pre-made physics systems that might be impressive at rolling around particles and ragdolls but are not designed for multiplayer games to the slightest so they kinda start blowing up when you start mucking around with their states (I suspect this is why fighting games are ahead imo since they often has bespoke essentially 2d sims). I actually implemented a coop multiplayer prototype over WebSockets for a wolf-style raycasting FPS game I had made for 7dfps that was based on OT (like many fighting games are). It's fairly simplistic (if you bring over the collision and physics work inside the OT simulation). OT was a good choice since it would eliminate desynchronization issues, and since I was using websockets that are reliable and but can have some lag getting things reliable from the get-go was a better option. --- 1: The server runs a single truth state a second or so back in time (sent over to clients upon connection). The server never re-simulates anything (clients will, see below) 2: The server keeps a log of events back to the truth cutoff point, once the truth cutoff is passed they're not needed by the server anymore (unless some laggy client hasn't received them yet, but if that clients goes too far behind it should be dropped so no issues for the server about overflowing). 3: Upon connecting clients synchronize time with the server before receiving state and all existing messages. 4: New game states are produced immutably from the previous (with any messages tied to the point in time). 5: When shooting,etc the client sends a timestamped message to the server, the server MIGHT elect to discard or re-time any message a client sends before logging and broadcasting (this is why the time synchronization earlier was important, clients should be created at the "now" point in time or might be re-timed by the server to deter hacking). 6: A client keeps all states between the truth and now, the server will inform clients as the truth moves forward in time so they can discard old states, any message can come from the server as being timed between truth and now and all "old" messages causes a rebuild of states between the message time and "now" (The "now" state is what we display to the user) 7: A client display-cache synchtonizes with "now" and renders, if a server sent "old" messages that caused an enemy to change direction back in time the cache will handle tweening or snapping (and this is totally separated from the simulation). Since the client created a message at "now" it would've been sent directly to the display cache (and triggered immediate feedback to the user), past changes by the server can undo things (f.ex. if you just died before shooting) but handling that smoothly is not related to the simulation code that can remain clean but rather the display cache handler. --- Sadly I only did this as a side-project and some contracts took over so it's been kinda bit-rotting after I left it mid-refactor (it was kinda messy and tied to the game it was written for), but the architecture felt quite stable once working (one minor issue might is that it works best with fixed-point math due to floating point numbers potentially diverging, even if gradual checkpoints by the server could be introduced).