Re: How to extend a patch theory to fully commute

I haven't fully digested everything you wrote but I guess a remark may
be in order, lest you waste time on something that cannot be implemented
efficiently. I am not claiming this is equivalent to what you aim at,
but I think it is at least related.

A well-known and quite natural way to identify the equivalence class of
all patches that a given patch P can be commuted to, is to use the so
called "minimal context". A minimal context C(P) for some patch P is a
sequence of patches starting at the empty state and preceding P, and
that is minimal in the sense that no subset of it is a valid context. In
other words, no patch in C(P) can be commuted past P. Another way to
look at it is to start with a patch P in /any/ context and then commute
everything you can past P. It is easy to show that this can always be
done and that the result is unique i.e. you always get the same /set/ of
patches for the minimal context.

In principle, we could represent patches as they appear in their minimal
context, together with the set of patches in the minimal context. This
would be a unique representation which could be stored hashed and thus
would be fully tamper-proof.

The problem is that computing minimal contexts is prohibitively
expensive. Nobody has bever come up up with an algorithm that is better
than O(n^3) in the worst case, where n is the size of the context you
start with. The reason it is so hard to improve on this is that before
we can commute two patches, we need to first bring them into proximity.
Suppose half the patches in the starting context commute past, and the
other half does not. The patches that do not commute past will
accumulate before the patch P and all earlier patches you try to commute
must be commuted past all these accumulated patches, one by one.

Cheers
Ben