Once again wishing the hypothetical device I've long been describing was real!
An OS & hardware focused specifically on the task of communicating with diverse people! Using existing protocols. Barely any apps!
Just today I introduced an editor framework to it so basically every editor has infinite undo, collaboration, & composability! (I wasn't responding to anything, just how the scheduling worked out...)
This a bit more "from scratch" than I'm capable of though...
Seeing all the encouragement to try "Linux" & the common pushbacks against it...
If you insist your existing apps should run on "Linux"... I'm impressed by how imperfectly well we've achieved this! Its significantly easier said then done.
To me its very much akin to saying "Don't blame people for driving when our infrastructure is built for cars". There too I'd say we shouldn't be driving.
Yesterday I discussed collaboratively editing text, but there's other things you might want to edit!
Implementation notes: I'd keep the data in RAM in its sorted & compressed form, only decompressing it transiently for processing & modifying. Zipping from columnar format into "edit" rows would be most involved step.
For instance we'd want to edit not only individual files but whole directories of them! And the attributes attached to each of its files!
To implement such a "mapping" CRDT we can define an operation which sets the value at a given key to a given value, possibly to a "tombstone" value to indicate deletions. The problem comes when 2 peers attempt to set the same key to different values!
If we track our understanding of the latest edits our peers are aware of (a "lampart timestamp"), storing that in our edits' metadata, we can establish a causal ordering to these edits. When that fails we can compare peer IDs.
This causal sort is also vital for ordering text insertions!
Talking about text... Lists would be implemented basically the same way but with greater freedom regarding which data you can store in each node.
We may want to incorporate counters, by summing all the nudges up/down collaborators have made.
And once we have collections we'd want to store numbers, constant strings, booleans, etc in them. Combine these datatypes and we should be able to define most other CRDTs you might want.
Continuing my study of ELF Utils' commandline tools...
After initialization both I/O & internationalization as well as parsing commandline flags ar configures LibELF to a specified format version, parses/validates the commandline flags some more ensuring additional args remain, pops the archive name as a commandline arg, & branches over the subcommand specified by those flags.
This may output some help text via LibArgP. Or it may...
For Insert operations ar opens the ELF file, initializes some memory including a symboltable, for oper_qappend operations populates a hashmap ( LibC's search.h one), iterates over the ELF file, followed by extensive validation & cleaning up! For each ELF header (skipping filepaths for performance's sake) initializes a new archive entry for it, considers whether its present in the hashmap, & prepends the entry into a linkedlist.
Primarily ar performs "extractions" ("list" & "print" are variations), involving opening the archive & populating a hashmap, fstat()s the file, iterates over ELF entries, possibly atomically overwrites the file with extracted symbol table, & cleans up. For each entry it handles filepaths specially, extracts it into a new ELF symboltable, and/or checks for presence in the hashmap, & possibly formats human output with lots of options.
@alcinnz
I had limited success with elementary installs for previous Mac users... Nowadays Linux mint is my goto for people who just want something that'll let them use their computer.
To ensure this order independence, we must never incur a merge conflict! Instead we'd apply arbitrary yet deterministic priority based on peer IDs. With this peers can merge as frequently or infrequently as they like! Maybe we'd integrate this collaborative editing into the SRTP/XMPP videocalls I've established?
Our established text editor already logs a sequence of editing operations, which we can reformat into a text-CRDT by adding some provenance metadata.
Now that I've established the basics, we need to address performance issues!
First while writing could be as trivial as appending the edits, that would incur heavy overhead in reading the document in the correct order. However if we keep the document sorted in the correct order then writing to it will remain very efficient (akin to editing an ordinary plaintext file) whilst reading would become trivial!
Second we'd be storing a significant amount of data per byte of text!
To compress a CRDT's provenance metadata away to practically nothing (following Ink & Switch's AutoMerge's lead, ideally we'd achieve compatibility with it!) arranging the data into columnar form reveals plenty of opportunities! Storing all values in one field across a bunch of edits, as opposed to storing an array of edits.
Depending on what works best for each column we could use run-length, diff, codebook, or Deflate compression. With variable-lengthed ints.