Why the random strategy choice?

[tleb]

As your GH is linked in the paper which describes LSEQ and I see other questions here, I come here to ask another scary question: why is the allocation strategy random and isn't just alternating?

As I understand it, the goal of the random strategy is to have a doc which can handle both add a lot just after an atom (boundary–) and just before an atom (boundary+). It won't really affect the performance (n % 2 is surely quicker than generating pseudo-randomly 0 or 1 but it isn't done many times) but I wanted to know if there was a reason that I missed?

My final goal is to implement LSEQ in Go. :)

[Chat-Wane]

Sorry for the delay, I just read the issue.

In this implementation, the strategy is alternated as you described, for the sake of simplicity. However, in the paper, the strategy is chosen at random; one per depth in the underlying tree. The reason is the following: it is very easy to challenge the global allocation strategy if you know which sub-allocation strategy is used at which position in the sequence. For instance, if you know that the strategy is boundary+ you will insert new characters in front of each other. After a few, you will invert the insertion pattern, for you know that boundary- is the new sub-allocation function in use at this position.
So it is mostly to make life difficult to malicious users (assuming that they do not know the generated identifiers).

It is worth noting that even with a randomized strategy choice, a malicious user could challenge easily the allocation strategy by inserting between the 'boundary'. However, using LSeq, the difference between 'normally-generated' identifiers (log^2 of the number of insertions) and 'maliciously-generated' identifiers (number of insertions^2) is such that you could detect them and act accordingly.

My final goal is to implement LSEQ in Go. :)

Nice! Do you plan to write a distributed collaborative editor in Go or is it just for fun?

[tleb]

Thanks for all those infos, I'll stick with the alternating solution then.

Nice! Do you plan to write a distributed collaborative editor in Go or is it just for fun?

It's for fun, but if I find a nice project I could make us of this in, I won't hesitate. But first, I need to grasp every detail of LSEQ to make my implementation.