why Magic Folders doesn't work for more than 2 clients

[Zooko Wilcox-O'Hearn]

Dear folks:

Context: “Magic Folders” is a new layer on top of Tahoe-LAFS which
implements Dropbox-like "auto-sync" behavior. It's super exciting!
Development of it was sponsored by Open Technology Fund. We've
finished implementing it, but now we're noticing some bugs and
limitations, and this is the biggest one I'm aware of right now.

As David described in this comment:

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/2551#comment:22

The current design and implementation of Magic Folders only works if
you have no more than two clients attached to it. By "clients" I mean
here either two devices owned by the same user or two users each with
their own device — Tahoe-LAFS and Magic Folders are unaware of any
distinction between a separate human user with their own device versus
a separate client/node/process/device operated by the same human user.

The problem is subtle, and I'm writing this letter mostly in order to
cement my own understanding of *why* the current design fails in the
3-party (or more) case. Also in order to draw Daira's attention to it
and see what sort of fix she would suggest.

Here is the section of the design doc about the problem of
distinguishing conflicts from overwrites pushed by your peer. We
whimsically named this problem the "Fire Dragons" problem.

https://tahoe-lafs.org/trac/tahoe-lafs/browser/docs/proposed/magic-folder/remote-to-local-sync.rst#fire-dragons-distinguishing-conflicts-from-overwrites

The goal of the Fire Dragon slaying protocol is to make it so that you
can reliably tell whether a given new version submitted to you by your
peer was derived from the most recent version that *you* created, or
if it was derived from a previous version than the most recent version
that you created. If your peer says that it was derived from the most
recent version that you created, then this means your peer is
instructing you to *overwrite* your most recent version with their new
version. If instead your peer says that it was derived from an earlier
version, then this means there is a *conflict*, where you and your
peer simultaneously made changes to the file.

The way the current Fire Dragon slaying protocol attempts to track
this distinction is by including a slot with each upload called the
"last-downloaded record". When you receive a new version from someone
else, you inspect the last-downloaded record that accompanies that
version, and if it shows that the version they started from was the
most recent version you sent them, then you know it is an overwrite
[*], and if it isn't, then you know it is a conflict.

Now here's the problem: this design assumes that you are the only
source of downloadable versions that they could have started with! But
if there's a *third* party, and they started with a download from that
third party, then with this design you will assume that they are
starting from an *earlier version from you*, when in fact they are
starting from a version from the third party, which might in turn have
been derived from the most recent version from you. (Or it might not
have — it might have been derived from a previous version from you.)

Bottom line:

1. Magic Folders exists, and is awesome.
2. It works fine if you have no more than 2 devices/users/endpoints
attached. (Or if no more than two of them are editing the same
document at the same time.)
3. The current version doesn't work if more than 2 endpoints edit the
same file at the same time.

I have an idea about how to fix this, but I'm not going to include it
in this note, because I want Daira to have a chance to think about the
problem and propose a fix before being biased by my proposed fix, and
I want Leif to have a chance to reply with his proposed fix (that he
attempted to explain to me at the Nuts & Bolts party today).

Regards,

Zooko

[*] Except if there turns out to be an Earth Dragon — see the design
doc for details.