co-operative computing: let's break it down!#

Or: How I Learned to Stop Worrying and Love xkcd 927.

This is WIP, and I kind of gave up on making it accessible to a general audience halfway through, so sorry general members of the audience! There's also still a bunch of scratch notes lying at the bottom which are longer than the article itself and you can read if you'd like me to feel embarassment.

Here's a true thing about computers today: practically speaking, I can download software that does anything a computer can do on its own (read things! write things! make music! play games! make games!) instantly, for free, and know that what I produce using that software is controlled by me and can't be seen by anyone else.

Here's another true thing: practically speaking, as soon as I want that app's data to be conveniently available on more than one computer, I have to start renting infrastructure from the software's creator and trust them to safely mediate my communication forever. (Let's come back to "conveniently available" and "safely mediating"...)

Let's run that back from another perspective:

Here's a true thing about computers today: practically speaking, someone who makes an app that can do anything a computer can do on its own (read things! write things! make music! play games! make games!) can distribute that app to the entire world instantly, for free, forever, no matter how many people use the app.

Here's another true thing: practically speaking, as soon as that app maker wants the app's data to be conveniently available on more than one computer, they or the app's users become responsible for operating server infrastructure and taking responsibility for safely mediating all the users' communication forever, and it will get more expensive the more users there are.

In other words, why can't we just browse folders of files, open them with a variety of different software at the same time as our collaborators, see them update live, work on them offline, and share links? And choose, for our different files and folders, what trade-offs we want to make around privacy, performance, and cost without having to use a different app for each trade-off?

For some context on what's been simmering in my noodle soup as I've come to write this down, check out some of these influences:

• Sammy Gwilym and Aljoscha Meyer's thoughtful work and commentary on the Willow Protocol, especially the ideas of paths and prefix pruning
• Nikita Prokopov's musings on CRDTs-over-Dropbox
• These two talks by Martin Kleppman at Local-first Conf, especially the focus on commodification and the narrow waist
• Many things Ink and Switch have published, but especially Brooklyn Zelenka & co's work on Subduction
• The formats over apps ethos articulated in Dan Abramov's Social Filesystem post

Let's break it down! How should we co-operate with computers?#

By convenient, do we mean we can look at or change our stuff when we don't have internet? Our stuff will automagically simultaneously be synchronized between computers all over the world? It feels pretty hard to give up the Google Docs workflow. Can we see previous versions of our stuff? Can we search through all our stuff? How much space on our computers does our stuff take up? Can I let people read my stuff but not change it? Can I let people add to my stuff, but not read it? And how much does all this cost? Who is paying for it?

By safely, do we mean that random people on the internet cannot see our stuff? Ad agencies cannot see our stuff? The NSA cannot see our stuff? Only computers owned by us and our collaborators (and not the people who made the app) can see our stuff? And what do we even mean by "cannot see our stuff", do we just mean "can't open the boxes" or do we mean "can't even see the shipping label"? How much convenience are we willing to give up for that safety? Can we lose access to our stuff forever?

The temptation (for someone like me, anyway) is to get frustrated with a piece of software and the choices it has made, and wonder why someone hasn't made the right choices yet! And while we're on the topic of correct choices, what about the actual app? The UI, the features, how it organizes our stuff, what's with all the wrong-choosing?

So let's break that down, and stop choosing!#

I first heard the term "MxN problem" in reference to the Language Server Protocol, a bit of standardization work that advertises itself thusly:

Behold! Glorious simplification. Rather than every compiler creating bindings to every code editor, requiring M compilers x N editors bindings, we create a single protocol which must only be implemented once for each compiler, and once for each editor (only M+N bindings! orders of magnitude fewer!)

Here's a kind of similar looking diagram from Martin Kleppman's talk (just rotate your head 90° and squint).

It seems fair to say that two of the biggest and most successful narrow waists that exist for application developers are the network stack (pictured above) and the file system API, both of which answer the questions "what data can I access", "gimme that data", and "here store this data". But the file system is no good for collaborating, because we change files by updating the entire file at once, and folders are just unstructured paths we choose that can bump into each other indiscriminately. And HTTP is a great way to organize APIs, but it's inherently client-server and so generic that it doesn't actually provide any narrowing of the waist when it comes to data and how it is structured and synchronized.

So what would some nicer primitives look like? We'll know we're getting somewhere if we can create a protocol that seems not only possible but potentially even exciting to implement on top of ATProto, Holochain, Nostr, NextGraph, the onion network, IPFS, or BitTorrent, and on top of which to implement chat, document editing, spreadsheets, geospatial applications, databases, game engines, coding platforms, or even maybe one day a plain text editor. This will be our Criteria.

Aside: I was looking for an explainer article on the MxN problem to maybe link to, realized it was a more obscure term than I thought, but then found this article: Why LSP?. It makes an interesting assertion: the glue code that LSP abstracted away was always a tiny proportion of the code of a language server or code editor, and at the time that the Language Server Protocol came to be, there just weren't very many Language Servers in the first place. To what extent were the protocol's benefits reducing code duplication, and to what extent was it that it communicated to many pieces of software: "hey, it's possible and super useful and not that hard to connect to each other in this way!" How did it serve a social function as well as a technical one? I think it's also interesting to think about ATProto through this lens, as well as the discussion that follows.

I love the file system!#

In a serial world, we can think of our data as a bunch of files that live at a path, and when we want to work on a file we just put a new version of it at that path. In a concurrent world, this strategy raises the question: what happens if two people work on the same file, at the same time? Syncthing is a free app that has worked reliably for over a decade, and it kind of does most of what I want: I can create different folders on my machines, share them with different groups of people, operate on the files using whatever software I want, and it all syncs automatically, privately, peer to peer. But if two people edit the same file at the same time, all it can do is throw its hands in the air and keep both copies.

If we want to take this opportunity to perform a minimal perturbation, perhaps we could say: what if we just program Syncthing to know what to do about it? Just give it some settings that say things like "if you encounter a conflict in a Markdown file, resolve it according to this diff algorithm". Or "if you encounter a conflict in a JSON file, resolve it by merging dictionaries and arrays according to this algorithm". That would be janky, but it'd be pretty cool and good enough for a lot of use cases! You'd create apps that write to files that can be merged automatically, and let the user run services on their devices that sync those files.

It'd work even better if we then started making file formats that are designed for this use case. What if we had .yjs and .automerge files? I'd guess part of why we don't have these things is that the only software which is really file system oriented is desktop software, which also tends to be the least collaboration oriented. Mobile devices and web browsers don't really give apps a space they can write data which something else will sync for them: Syncthing kinda works like this on Android, but not iOS, and not web browsers.

But this idea of a polyglot sync system which knows how to merge many different file formats is pretty nice! Maybe we could just embed it in apps on the less permissive platforms. It does raise some questions though: how will we agree on the file types to sync, the algorithms by which to sync them, ensure all the clients work the same? How are we going to bootstrap the ecosystem? This kinda makes it seem like all file formats need some kind of standards body, which is a bit heavy weight. Or maybe we could come up with some kind of standard language for expressing merge-able file formats, and do an ATProto Lexicon-style self-publishing kind of thing? Each file could be associated with a WASM blob expressing how to merge it, that would give app makers lot of expressivity while still allowing them to delegate the infrastructure!

I actually think all of these ideas are kind of interesting and I'm curious to explore them, but what I think would be the most aligned with the desirable properties of a narrow waist we enumerated would be if there was a single file type which was flexible enough that we could build all of our collaborative apps on it, but still small and simple enough that it could be built on top of any collaboration platform. Remember the Criteria!

The Narrow Waist-land#

Theoretically speaking, we can think of the problem as one of sending, receiving, and storing messages. A message might itself be a whole document or piece of media, or it might be a fragment of a document, or an instruction like "add this text at this offset" or "add this row to this dataset". A system for synchronizing messages (if it wants to do anything more complicated than just send every message to every node in the system) will also need metadata attached to those messages. And we can describe a decentralized system by which metadata it chooses to attach, and what meaning it ascribes to that metadata.

Here's a simplified metadata toolkit:

• content hashes: the only kind of metadata which is inherent to the data. It lets us refer to a message in a way where we can know that what we're seeing is the same thing as when the reference was created.
• session, device, or author ID: these tell us who created the data, and also allow us to delegate the problem of creating a unique identifier to a smaller and less concurrent subset of the data
• any kind of path or deliberately chosen ID: these are most likely to be human readable, and could also be hierarchical
• signature: these prove data authenticity
• timestamps and logical clocks: allow us to order events, loosely or strictly. timestamps are also just useful information
• references to other data: previous elements of a list or DAG, group or permission boundaries

A few examples from existing systems (smoothing over many details):

ATProto has a few messages types. Let's just look at records, the most important one, which contain the actual app data formatted as typed binary JSON (a post, a like, whatever your heart desires). They contain:

• the DID of the creating user: who created the record. in this protocol, just this information can also be used to identify which server stores the record!
• a collection: what type of record this is
• a record key: a unique ID for the record within its collection and repository
• the above three pieces of metadata form a URI which can be used to refer to the record
• a content hash is also computed, which can be used to ensure that the message you're seeing now is the same one as when e.g. your friend saw it
• a signature: an unforgeable piece of data that proves the authorship of the message
• this metadata isn't able to express permissions, so a new piece of metadata is being added: a space ID, unique for each record, which indicates its permission boundary

git:

• we have blobs, which contain the actual files being version-controlled, and are keyed by a content hash
• we have commits, which are messages that contain a list of blobs that should or shouldn't now exist at different paths and a text description of the change, and have their own content hash, parent commits, author information, and optionally a signature as metadata
• we have ref updates, which are messages that instruct a repository to resolve a human readable reference like main to point to a specific commit

Willow:

• each message is associated with a namespace, a subspace, a path, and a timestamp. All of the namespace, subspace, and path can be used to enforce permissions and synchronize subsets of data. The timestamp is used to determine which message to keep if there are multiple with the same namespace, subspace, and path.
• there is also a special "delete" message which gets

a filesystem:

• a file is a binary blob, and a directory is basically just a pointer
• they both have as metadata a text name, a parent folder, a modified timestamp, an owner, and a set of permissions. the text names and parent folders form paths that can be used to access files, and the owner and permissions are used to enforce access.

It's paths all the way down#

Here's my loose proposal for something that looks as file system-y as possible.

File internals: binary paths that point at a set of binary blobs, keyed by content hash. Deletion is implemented by range-based tombstones, which permanently remove part of the tree from the file. The only operations are write(path, blob), delete(path, start, end), and delete(path, tombstone).

There's an expectation that higher layers would use paths both for intra-file permissions and for syncing subsets of a file. The biggest question I have about this is whether "keyed by content hash" will be a deal-breaker level of overhead per op for live collaboration use cases, as compared to something like just making concurrent writes to the same path undefined behavior and accept the sharp edges (just as working with raw binary files has sharp edges). I think it's worth trying the deterministic and unforge-able version, and only abandon if it's absolutely impossible to get the necessary performance out of applications.

File identification and metadata: the file ID is a content hash of a binary blob which represents arbitrary metadata. That metadata could be used for things like provenance, schema descriptions, permissions, or more. Notice that metadata that's part of this blob cannot change, so it's not as good a candidate for data that might change over time, like the file's human readable name. That might be stored inside the file at a path specified by a higher level protocol.

Folders: this one seems harder, and let's remember here that these layers should compose: multiple folder systems could all work with the file protocol above, and each of those folder systems could accomodate multiple file protocols. But here's a couple different thoughts:

1. A folder is a file (and therefore has a unique identifier via content hash of its metadata), which tracks a set of leaf nodes (non-folder file IDs), and an optional parent node. If the parent node is omitted, the parent is considered to be the root of the namespace. If a cycle forms, all the nodes in the cycle are considered to be at the root until someone manually breaks the cycle. The catch being: how do you implement predictable access via a path using this system?
2. Just store a set of ops: optionally add files to a path, or delete a set of previous operations. The folder structure is then implicit from the paths. The catch being: moving a huge folder (or even just renaming it) means updating every single path entry, and concurrent operations within that folder would still land at the old location.

Or maybe... accept a model that's slightly less dead-simple here, and do both: allow the path-based files to be mapped to the ID-based files, with the higher level of the directory tree being programmatically accessible paths (think /var/lib or .local/share), and the lower levels being user data (think /home/user/Documents/West\ Coast\ Road\ Trip/car-rental-insurance-photos-DO-NOT-DELETE.zip).

Identity and permissions: just kidding! I'm not going to provide a generic universal substrate for identity and permissions management here because for the time being I do value my sanity. Instead, I'll propose we do the HTTP thing: standardize ways to add metadata to the connections between apps and the file system, and the file systems just reject requests which don't fit their internal notions of permissions. And again, remember the ethos: there doesn't have to be a single solution!

Non file system-y things: collaborative apps have other needs that we could kludge onto this system. Maybe each file or folder can also optionally carry realtime broadcast channels for presence, audio, video, or ephemeral messages? What else might fit in here?

Where to go with this#

I plan to talk to other other people who are thinking about the narrow waist (and people who aren't!), consider with them whether the above proposal, variants thereof, or other protocols meet the Criteria, and build proof of concepts. I dream of a prototype which allows you to:

• browse and open files and folders distributed heterogenously over multiple decentralized protocols: some on one protocol, some on another, all viewed through a unified interface, and
• create new apps which can operate over those files and folders, both inline and distributed over HTTP

END OF CURRENT DRAFT, OLD/ROUGH NOTES FOLLOW#

imagine, at the highest level, that when we use an app, it has a way to tell us what stuff it wants to store, and it leaves it up to us to choose where to store that stuff. and the place with all our stuff has a way of telling our apps whether anything has changed in the stuff we store. computer nerds have a name for a "way of telling": a "protocol". for convenience, let's refer to this hypothetical protocol as "myco", because we're fond of the imagery of networks of fungal mycelium interfacing between many different forms of life, and because we're a pastiche of ourselves. here's another thing computer nerds like to say: when a piece of software uses a certain way of telling, we say it "speaks" that protocol. now we can have fun and say that an app "speaks myco"!

so: i've used an app which speaks myco to make some stuff. maybe i just want to store it on my computer. maybe i want to put it in a free proprietary cloud like Google Drive! maybe i want to publish it publically on the internet. maybe i want to keep it totally encrypted and secret. maybe i want send it by carrier pigeon on a USB key. maybe i just want to share it with my housemates. the app doesn't know, the app doesn't care!

conversely, the place where you keep your stuff does not know or care what apps you use. maybe it's a chat app. maybe it's a music app, spreadsheets, camera, recipes, activism, passivism, an app that tracks pun production rates to predict groan intake and budget smirk output. again, don't know, don't care! everybody's speaking to everbody. call it a lingua funga!

now, it goes without saying: users might care. the people who make apps and storage might also care. but we're imagining a protocol for apps and storage which do not care. however, if we manifest successfully, there'd be nothing stopping someone from riveting their preferred storage solution onto the back of their app or vice versa, so if this turns out to be a good idea it wouldn't just be for the agnosticism zealots!

things are sounding pretty utopic so far, so what's the catch?

good news everyone!#

sorry to string you all along like this, but myco kinda already exists, and has for decades. it's called a file system! it fits the bill exactly. file systems can be private, public, shared, kept for one person, all of the above. and apps which use file systems don't really know or care about those choices. conversely, different implementations of file systems and services don't tend to know or care about which apps use them.

so why don't we just encourage the creation of more file system apps and more file system providers that fit different use cases? to answer that question, let's have a peek under the hood and come back to "conveniently available."

what does an app tell a file system? it might come as a surprise, but as far as both the app and the file system are concerned, a file is basically just one enormous line of text on a strip of paper, that has a little label with a name on it. you can put bundle those strips together into a folder, which also has a name label, and you can put folders in folders too.

at the highest level, an app can tell the file system:

• can i see what's on the strip of paper named alfalfa.jpg in the folder named cool_beans?
• what folders and strips of paper exist inside cool_beans?
• put the strip of paper hummus is the best dip! in the folder cool_beans with the label garbanzo.txt. even if there's already another strip with that label, just throw that old garbanzo out!
• move the strip of paper named sweet_pea.js in the folder named cool_beans into the folder named pulsation_station
• delete the strip of paper named lima.mp4 in the folder named cool_beans

so, that's a lot to digest. what were we talking about again? right: why don't we make file system providers which give different answers to some of our earlier questions. like, does it synchronize our stuff between our computers? that one turns out to be pretty hard for a file system provider, because of the way apps tell file systems about their stuff.

check out this tough nugget: what if two different people put different strips of paper with the same label at the same time? what strip of paper should the file system then tell apps has that label? the default answer chosen by providers like Syncthing, Google Drive, or Dropbox is "whichever strip came second, even if it was only by a millisecond" and that's what they tell apps. the file system provider itself can try to help, by keeping the different strips of paper, and allowing users to inspect them and pick which one to keep later.

that'd obviously be quite annoying when it happens, even for one person who works on multiple computers let alone a group of people collaborating at the same time. it's essentially an automated version of garbanzo_DRAFT_v3_april_PRE_FINAL, and no one is ever happy about a folder full of garbanzo_DRAFT_v3_april_PRE_FINAL. maybe even more importantly, there isn't even a way for an app to realize this has happened and do anything about it, because this isn't part of the file system protocol, it's a way providers have tried to work around the problem. and it's probably one of the biggest reasons why we don't just co-operate by sharing file system folders with each other!

the big lesson here is that the protocol itself — the way apps tell their storage providers about their stuff — affects what answers are even possible to give to questions about "conveniently available" and "safely mediating". so if we're making a new protocol, what we should probably try to aim for is enabling a bigger set of possible answers, and maybe focus on answers which other popular protocols have neglected. but no matter what we choose, we're going to preclude some answers from being possible. there is, as always, no such thing as free lunch.

so what are we doing here?#

this was supposed to be an essay about co-operative computing. so we're interested in situations where multiple are working on stuff stored with the same provider at the same time. we found out that if apps use a file system protocol, they'll end up doing a bunch of stuff which is really inconvenient in this scenario. so what kinds of things can we do?

first, there was nothing#

let's start with the most basic and necessary act: creating a new strip of paper. without this, we have nothing. we can all just stuff strips of paper into the box without bumping into each other. but that's not a great way to organize your stuff. what are you going to do when you need to find a specific strip, look through them all one by one til you find the one you want? that's why file systems have the labels and the folders! but that's exactly where they got into trouble.

if we accept the ideas that:

• we do need labels to be able to organize our stuff, and
• just keeping the most recent strip of paper for each label is not a good way to collaborate on a strip of paper then there's no way forward here besides figuring how to make sure that no one picks the same label for the same strip of paper.

there are broadly speaking three ways of doing this:

• name labels: give every person a unique label, and then store our strips of paper with both the name of the person and the name of the label. then people can just make sure they don't re-use the same label themselves!
• random labels! just mash your fingers on the keyboard to pick a huge and totally random string of letters for the label, so big that there's just no chance someone else will pick the same one. let's try it right now: ourgoabrgjoabnpaidjfhaboawefhoi. go on, you do it too! please e-mail me if you got the same one, it means our fates are intertwined and we must fulfill our destiny together.
• finally: hashes. no, not like breakfast, get your mind out of the griddle! get ready, it's the most complicated one: cleverly calculate a big string of letters using just the letters which are on the strip of paper in question. just make sure to do it so cleverly that there's just no chance someone else would come up with a different strip of paper that results in the same label. we're basically going to take all the letters on the strip and carefully jumble them up and combine them really thoroughly, making sure to follow the same recipe each time so they always jumble up the same way. ok, so kind of like breakfast, other than the careful recipe following. i swear to you that hashes are really what computer people call these!

let's take stock: random labels are the simplest, and it seems to work: a big jumble of letters we could never remember or write down ourselves, but which no one else could have guessed until we told them about it. it is pretty annoying that we can't remember them or write them down though.

hashes are more complicated, but it does have the advantage that we can make sure we haven't jumbled up our labels and strips of paper: if the label gets damaged, we can always calculate the label again using the letters on the strip of paper. if the strip of paper gets damaged, we might not be able to calculate the letters again, but at least we'll know something went wrong! and if we're lucky, maybe someone else still has the letters and we can grab them from them. but, doing these calculations is too hard to do by hand, so now we're completely reliant on the computer to calculate the labels for us.

name labels is the most complicated (just ask your friendly local nation state how easy it is to give every person a unique label), and it requires bringing in a lot of assumptions about who will be using the protocol, how they'll identify themselves, how we'll make sure only that person creates files with their unique label, and so on. but random labels and hashes both gave us very hard to remember labels like r3411yb4db34ns, whereas with name labels we can still give files descriptive and memorable names like garbanzo.txt. if we also take on the additional challenge of handing out name labels that are not only unique but also memorable, then we finally get an advantage over the other methods: labels a human could remember and write down by hand.

i'm not sure if we have enough information yet to decide which method is best, so let's see if considering other features brings any clarity. regardless of which labelling method, we can now create a strip of paper, and we can give it a label.

god is change#

so a natural thing tends to happen when we've written some nice words down on a strip of paper: we look at them, and we think "oh god why am i like this?" and immediately want to light it on fire and start over again. we want to change what we've written. we've already gone over why that's hard when we talked about file systems: if two people change the same strip at the same time, all we can do is either just throw one straight in the garbage, or store both new strips and perform automated garbanzo_DRAFT_v3_april_PRE_FINAL.

in fact, this is even harder than creating something new because the label already exists, and everyone already knows about it, so we can't use the same trick from file creation of picking a label that no one else could possibly have chosen. so if we still agree that just throwing data out or keeping all the data indiscriminately are bad options, what choices do we have left? if we take a name labels-esque approach, we could say that only a specific person is allowed to change a specific strip of paper, but that wouldn't be very co-operative. otherwise, we could just say that whatever piece of data is stored at a label, that's the only piece of data that will ever get stored at that label. that seems kinda crazy! data never changes? data never changes! take that, octavia.

if we conclude that data never changes, it's actually a bit of a win for the hash mongers. one thing we didn't discuss was that because of how hashes work (the label is determined by the strip of paper), you couldn't have changed which strip goes with which label in the first place, which could be a huge disadvantage. but in this case, it actually doesn't matter!

nothing lasts forever#

well, there's a special way of changing a something that isn't so hard to co-operate on: destroying it! if we both try to delete something at the same time, it's ok: the end result can just be that the thing gets deleted. boom, glad at least one of these was easy, right?

ok fine, there's a catch. for two people trying to delete something in the same box at the same time, it is that easy. but say someone (even just one person!) decides to delete garbanzo.txt from a box which is hooked up to another box. the first box can get rid of the strip of paper, but it has to hang on to the label garbanzo.txt and leave a little note that it's been deleted. otherwise, when the two boxes ask each other what's up, the second box will say "well, i've got neat strip of paper called garbanzo.txt", and the first will say "oh woah, i've never heard of garbanzo.txt in my life!" and add it straight back to its collection.

another hash related quirk here: it's kind of weird to try to delete one. if you delete a strip of paper that says "hi!", and hang on to its label to make sure you remember it was deleted, then if someone else tries to create a strip of paper that says "hi!", you'll say "oh sorry, we deleted that", and they just... can't. so that seems pretty inconvenient for the hash mongers.

ok, we've spent a good amount of time on files, but you may recall there was a second component to file systems.

how do i hold all these files?#

labels are definitely helpful for keeping track of our files, but it still kinda sucks to open up a box and just see a giant pile of papers, even if they're labeled. most people with big boxes of paper will group them into folders. how does that work for multiple boxes and multiple people adding to them?

for creating a folder and adding strips of paper and other folders to it, all is good! even if multiple people do this at the same time, and use the same label, we can just add all the strips they both tried to add and it all works out.

moving a strip of paper from one folder to another is a bit more complicated: what should we do if that's done at the same time? we could arbitrarily pick one, but that's not very satisfying in a similar way to randomly picking which update to a strip of paper should happen. what happens if we apply the same rule

outline#

• intro: articulate current problems:
  • MxN
  • hosting and applications are tied together
  • users do not have control over data
• architectures of co-operative computing:
  • centralized: can you choose at what address? to what extent does one address going down break co-operation?
  • distributed: to what extent does one address going down remove access to data?
  • interoperable: to what extent can the same data be operated over by two different apps?
  • concurrent: to what extent can the same data be operated over at the same time?
  • file system (decentralized undistributed interoperable serial)
    • app computations and data run on the users' computer
    • co-operation is faciliated manually by the user
    • unsuited to real-time collaboration
  • server centric (centralized undistributed intraoperable concurrent)
    • app computations run on the app maker (& maybe user's) computer, data is stored on the app maker's computer
    • co-operation is facillitated automatically by the server
    • suitable for real-time collaboration
  • self-hostable (centralized semi-distributed intraoperable concurrent)
    • app computations run on the user, app maker, or a third party's server (& maybe user's computer), data is stored on that same server
    • co-operation is facillitated automatically by the server
    • suitable for real-time collaboration
  • federated (semi-decentralized semi-distributed intraoperable concurrent)
  • IPFS (decentralized distributed semi-interoperable concurrent)
    • app computations run on the user's computer, data is stored on a third party's server
    • co-operation is embedded in the data model?
    • unsuited to real-time collaboration
  • git (semi-decentralized distributed semi-interoperable concurrent)
    • app computations run on the user's computer, data is stored on the user's computer and third party's server
    • co-operation is facillitated semi-manually using tools the app provides
    • unsuited to real-time collaboration
  • local first (centralized distributed intraoperable concurrent)
    • app computations and data are stored on the users' computers and a server
    • co-operation is facillitated automatically by the server
    • suited to real-time collaboration (until the server is unavailable)
  • true p2p (decentralized distributed intraoperable concurrent)
    • app computations and data is stored on the users' computers, and optionally some servers
    • co-operation is facillitated automatically by the users' computers
    • suitable for real-time collaboration (until the users' computers are unable to reach each other)
    • closed laptop problem if no server
  • ATProto (semi-decentralized semi-distributed interoperable concurrent)
    • app computations and data are stored on a third party's server
    • co-operation is application-defined
    • not suited to real-time collaboration
  • willow (decentralized distributed interoperable-ish concurrent)
  • keyhive (decentralized distributed interoperable-ish concurrent)
  • myco (decentralized distributed interoperable concurrent)
• solution:
  • MxN -> M+N
  • user chooses hosting which is compatible with all their apps
  • data is stored in a standardized format, which is accessible to the user
• sidetro: file systems (universes of Px(M+N))
• the details:
  • as simple as possible: file system protocol is very dumb, and therefore very flexible
  • ownership/usability: should be able to run on same device for fast access
  • necessary operations:
    • create data
    • delete data
    • organize data
    • request permissions/data
  • safe operations: create data. delete data (with overhead). organize data?
  • practical considerations: how would this work on mobile devices etc
  • tricky use cases:
    • single doc could reference things from other docs (tag a person! transclusion!)
    • single doc could have different permissions for different parts (comment/suggest/edit)
    • where should a share link point?
    • how does sign-in work?

the rest#

• storing multiple copies on duplicate create/update doesn't make sense: how do we differentiate the copies? with a label... but if we can give them unique labels anyway, why not just give them unique labels to begin with?
• deletion: necessarily delete forever? because multiple boxes. but then can't really delete CAS blobs (because you're not only preventing that label from being used forever, you're preventing that data from existing forever). could do causal tree of deletions/revokes, but now you're keeping a causal tree. what would an app expect? that after deletion, data should be gone, and should not resurrect. should there be manual data resurrection within the scope of a file browser? how should an app respond to such a thing? do we track a hash for folders, and delete at a hash? but without keeping the full metadata tree, the hash doesn't tell us what was in the folder at deletion time, so a late-joining client couldn't determine which data was intended for deletion from just the hash. it's probably a good idea to track the hash at deletion time anyway tho, so we can at least flag if unknown data was deleted.
  • is there something we can do with tracking epochal clocks such that we can properly permanently delete even tombstones after a time? like say something was created at time X. then box A deletes that thing at time Y. if box A hasn't spoken to box B since before time X, it wouldn't be able to tell whether the thing at X was new. but if box A has spoken to box B since time X, then even without talking to box B, box A can safely delete something. so basically, we only need to hold on to labels newer than the least recent time we talked to any box which we might talk to again. i guess also with a caveat around introducing. basically there are ways in certain circumstances to delete tombstones (especially in a hub-and-spoke model), but with much caveat, and it's still worthwhile to endeavor to reduce tombstone overhead.
• folders: it's ok if multiple people create and add to the same folder. removing from a folder has the same q about foreverness. what if user initiates detaching & re-attaching the same blob to the same topic repeatedly? must declare CAS blob children at folder creation time? otherwise late-added children must be via transitive folder?
• why folders instead of just indexes?
  • in order to determine which data to sync where, we need a pkey?
• what list operations on folders? should there be a filter? prefix?
• the safe ops:
  • create a folder, which is an ID and created at timestamp:
    • potential metadata:
      • unique ID
      • keep track of hash of contents
      • timestamp?
      • arbitrary metadata?
      • optional canonical name? (survives deletions/simultaneous creations, listing based on canonical name means listing all the surviving subfolders simultaneously)
      • permission enumeration?
      • roles allowed?
    • what IDs are allowed?
    • can we specify that it can never be deleted?
  • delete a folder by unique ID
  • moving folders:
    • here's a use case that's hard to handle here:
      • as a user, i've given an app permission to store its data in a subfolder (say under "foo"). now i want that subfolder to instead live under "bar", but for any concurrent writes to the folder when it was living under "foo" to still get made to the folder under "bar". is this google drive-like model of a folder as a distinct entity which happens to have a parent possible? how does google drive handle folder cycles? do we just have to relax the notion that there is a "primary" reference to the folder, and therefore accept that deleting a folder may not necessarily fully delete it if various apps have created multiple references to the same folder? but if cycles are allowed, how do nested permissions work? how does google drive handle folder cycles and permissions?
  • create a file within a folder, which is itself a block and is a list of blocks with size ranges?
    • i suppose we could likewise allow a file to have a canonical name, and say that listing a file's contents by canonical name is listing the set of lists of blocks of surviving file listings?
  • delete a file
    • range pruning!! range pruning!!
    • compaction via ownership transfer? (but have to retransmit data for compaction?)
• beyond file systems:
  • permissions
  • transclusion
  • ephemeral data
  • indexes
  • synchronize transactions? i.e. if i perform some ops in a transaction on one box, no other box ever sees the intermediate state? what is the point of this, if a different box could've constructed said intermediate state itself anyway? maybe we only need transactions when writing, but not when reading? it still seems useful to have them though: imagine we're using transactions for atomic move ops (delete and create), and doing a big sync. without transaction boundaries, our choices for never communicating a state where the file either doesn't exist or exists twice is to:
    • wait until sync is done to show changes (high latency, what if data is changing faster than it is syncing, potentially indefinite)
    • ...?
• emphasize that the point is that the protocol handles all data storage concerns. the app developer is not responsible for storing anything

scattered thoughts#

• if we're decoupling application layer from storage/sync, then protocol needs to include identity/authorship?
• other things protocol may need to include:
  • delivery status/notifications?
  • share links?
• how do you propogate data recovery thru the system? (revert a file to an earlier state, undelete a file, restore a whole workspace to a previous version)

old/rough#

as a software user, i want the changes i make to my data to be visible as fast as possible to both myself and my intended audience, but no one else. and i want to be able to rely on that data to still be there years or even decades into the future. as a software developer, i want to take on as little operational burden as possible.

currently, there are two major paradigms:

1. software stores data on my computer, but it's cumbersome to share it to my intended audience.
2. software stores data on a computer that lives in a warehouse far away, and the software developer has to manage that infrastructure.

i am imagining something that provides the best of both worlds: a protocol for software written by other people to store data on my devices, which synchronizes it to other devices according to my preferences.

those preferences could look very different for different people: some people want to just pay someone money to store their data somewhere privately, and the protocol should support this. some people want someone to store their data for free, even if it might not be private, and the protocol should support this. some people want the data to only live on their own computers, and the protocol should support this. the protocol should support any mixture of the above!

rather than making another piece of software which further empowers software creators to more easily take on that operational burden, or which empowers their users to instead take on that operational burden, could we instead disseminate a solution which allows developers to treat the entire data and synchronization layer as an abstraction?

what would such a layer need to take responsibility for? it would need to be able to:

• establish connections between computers
• store and consistently synchronize information between those computers
• ensure that the correct information is shared with the correct computers
• provide a method for doing the above which is flexible enough that it doesn't constrain what type of application can be built on it, yet powerful enough that actually useful and performant applications can be built on top of it

http/filesystem#

Certainly these formats' ubiquity has become a self-reinforcing loop, but do they also have some secret sauce from which we can learn? Borrow? Misappropriate? Steal?

Well, here's a non-exhaustive list of things to like about them:

• They're path-based, and can be interacted with by a human being as well as a computer program.
• They have incredibly simple mental models. They both say "gimme a path. do you want some data or you got some data?", and then they either say "got it boss" or "bzzt, no can do!"
• They give us ways to talk about things which they don't constrain or implement at all, like permissions, identity, and failure modes.
• Their shape doesn't create any performance bottlenecks.
• It is easy to build formats on top of them.
• They accept arbitrary bytes for content.
• They allow you to access the resources they store progressively: you don't have to load an entire resource to access any of it.