introduce new shared state chapter

[ansuz]

A preview of this PR's contents can be seen at https://demo.cryptography.dog/shared_state/index.html

This new chapter for the docs introduces some of the common ways in which application state can become desynchronized between peers unless deliberate steps are taken to mitigate conflicts. It then presents some of the core theory behind Conflict-free Replicated Data Types (CRDTs) so as to demystify their behaviour. Finally, it gives some practical examples for the development of webxdc apps using Yjs.

There are some points which I think could be improved, but I'd like a high-level review before I dedicate any effort there. Notably:

1. diagrams were only tested for visibility against the mdbook navy theme, and probably don't look great or function well in other themes. I'll revise this after determining whether those diagrams will be included in the final version
2. the background theory might be overwhelming for people new to some of these ideas. I was considering adding a disclaimer that readers might want to skip to the Practical use section if they struggle with lengthy exposition. I do think some of the information presented can really help with developing an intuition this domain, but I might have simply included too much information. I figure it's easier to cut sections than to prepare new ones.
3. the whole text could probably benefit from having more explicit examples, but I wasn't sure which webxdc apps to include as reference implementations. please do point out any which come to mind

[hpk42]

Thanks Ansuz, all very nice to read. Here is some high level feedback (need to rush now, so i only got until "conflict" chapter" with my preliminary draft feedback (we can also video-chat if needed tomorrow, need to run now):

• more telling chapter titles, a single noun like "Conflict" is too abstract

• The shared-state intro should better directly say what the chapter is about and not explain the webxdc format. I suggest to already give a brief summary in the main intro of the content, e.g. that HTTP implicitely provides message ordering and a "single source of truth" app state model, whereas webxdc apps send and receive payloads between peers, and need to manage message ordering and resolve conflicting incoming updates to app state.

  Opposing "http" and "webxdc" is maybe not perfect but quickly provides a first understanding for even novice developers how to think about webxdc (namely, it is not a framework, but replaces http with P2P APIs, causing a crisis of monotheism :)

• conflict chapter intro: already provide a summary, shorten (no diagram needed probably) and merge "Resolutions in the client-server model" into the intro.

• "The federated model" and "complications in federation": suggest to remove. I enjoyed the read and we should find another use but here the focus should be on the P2P model. So maybe drop the two federation-subsections and change and extend the subsequent "Conflict resolution in webxdc applications" chapter to talk directly about "P2P" messaging, indepedently if the transport is federated or actually P2P. From the POV of the webxdc app it is P2P, not federated.

• can the sub-chapters e.g. in "Conflict" be shown in the TOC somehow? (i know we discussed this and i think the answer was, anything in the TOC needs to be its own file, but i still can't quite believe that)

[ansuz]

Thanks for the reviews! I'm resolving the typos first, then I'll start addressing the deeper issues.

[ansuz]

I've pushed a big update which cuts extraneous information about federated systems and focuses more directly on a comparison between fully centralized and p2p architectures.

The page titles have been updated to reflect their new content, but I haven't renamed the files themselves yet. I figured those details can be left as finishing touches pending approval of the overall structure. I haven't removed the diagram files either, but will do so after confirming that they won't be used.

Let me know what you think once you've read through it. As before, an up-to-date version is hosted at https://demo.cryptography.dog/shared_state/index.html

[ansuz]

One thing though: where are the diagrams? I see some in the PR but not on https://demo.cryptography.dog/shared_state/index.html

I was waiting to confirm whether they were still any use before removing them from the PR, but they're not referenced from any of the pages. Unless there is an appropriate place where they'd be useful I can go ahead and remove them.

All you suggestions seemed reasonable, so I merged them, fixed a typo in one, and re-deployed to the demo instance.

[hpk42]

seems the TOC does not contain the proper titles.

[ansuz]

seems the TOC does not contain the proper titles.

fixed in this commit. mdbook generates pages when you first reference a new URL from SUMMARY.md, but permits the content to diverge beyond that.

[rosano]

I find this quite technical but perhaps that's the intended audience. Would be great to have a working yjs example with webxdc: I couldn't figure it out and went with automerge in https://codeberg.org/webxdc/checklist/ – but this might be beyond scope of this PR.

[ansuz]

I find this quite technical but perhaps that's the intended audience.

I tried to simplify as much as possible, but distributed systems are a fundamentally complex topic :face_with_spiral_eyes:

we can always refine further in response to future questions or points of confusion

Would be great to have a working yjs example with webxdc: I couldn't figure it out and went with automerge in https://codeberg.org/webxdc/checklist/ – but this might be beyond scope of this PR.

There's a link on the practical usage page pointing to the webxdc editor app. Given that you missed it, It's probably worthwhile to link to it again in the final learning more subsection.

I definitely think it's valuable to link to the checklist as well, though it's a bit unfortunate to discuss Yjs specifically and then not have many examples of it used in practice. I've just pushed a commit to link to the editor and checklist. Beyond that I lean towards merging this PR as is, and adding more examples on an ongoing basis.

@hpk42 and I discussed possible projects to reference as examples demonstrating different use-cases, but unfortunately it looks like many of the existing community apps don't quite guarantee convergence when messages arrive out of order. In particular, we're considering the pixel app and the high-score pattern which is common to many webxdc games, both of which are very good almost-CRDTs which can probably be made to provably converge with minor corrections. I plan to open some issues and submit PRs to those on an ongoing basis.

[hpk42]

There are several things i'd like to refine/refactor but this can happen in follow-up PRs, including the section naming. merging this now. thanks a lot @ansuz !