I am trying to figure out the best solution for a distributed system in which I am dealing with a tree (to represent files in a file system). When User A deletes a file or folder, and User B renames the same file or folder (or a file contained in the deleted folder), when User A receives the edit from User B, the file or folder on which the operation is supposed to be performed no longer exists.

I have been thinking about this for a while now, and so far the only solution I have found is to assign a UUID to each file/folder and then, when I pass edits to clients, pass the sequence of UUIDs allowing you to navigate to the file/folder. When a client (User A) receives an edit, it first walks down the path to the file and only merges if the file/folder is still around. The issue with that is the time it takes to walk down that path.

I have been thinking of using tombstones, which I need for my undo/redo system anyway, but I plan to store no more than X operations in the undo/redo stack (say 20), so eventually the delete operations will be garbage collected at some point, and I will still be facing the issue of applying edits to files/folders that are gone.

Any insight on how you would manage this would be welcome.

Bonus: what technique do you recommend to generate a UUID for each item in the tree? I heard of using a 128bytes random number generator (e.g. libuuid in C).

PS: I just found these 2 papers.

• A coordination-free, convergent, and safe replicated tree
• A commutative replicated data type for cooperative editing

Still interested in your experience of the issue though.