Question: interval for equal lseq identifiers

[s-panferov]

Hello, @Chat-Wane, I'm writing a port for your library and I found a case that worries me. It's technically possible for two different nodes to generate identifiers with equal digits (if they both will insert into the same position). If we will try to insert a new ident between these two, your interval-finding algorithm will iterate forever, because it will never find such a depth. Do you know how to work-around this problem?

[Chat-Wane]

Hi @s-panferov ,

Thank you for the report. You are right about that. The issue did not appear at the time because I did not simulated concurrent changes. But it is an old project and this was fixed in a more recent one: https://github.com/Chat-Wane/LSEQTree .

If you want to know how to fix this however, I can give you the idea: you have id_1 = [ (1 , (A , 1)); ( 2, (A, 2) ) ] and id_2 = [ (1 , (A , 1)); ( 2, (B, 2) ) ]. This happens in case of concurrent inserts as you mentionned. Let's say that the departure base is 2^2 = 4 identifiers. At depth 0 and depth 1, the number of possible identifiers between id_1 and id_2 is 0. At depth 2 however, the number of possible identifiers is 2^4, for any new identifier generated at depth 3 will copy the id_1 and place itself after id_1 , and before id_2. For instance, id_3 = [ (1 , (A , 1)); ( 2, (A, 2) ); ( 3, (C, 1) ) ]. id_1 < id_3 < id_2