LSEQ: CRDT for sequences

This framework allows the developper to configure underlying components of its allocation strategy and to measure the size of identifiers generated (see package module). Available components are divided in 4 categories:

• Base: Double or Constant (parameter departure base)
• Boundary: Double or Constant (parameter departure boundary)
• Allocation strategies: Beginning (boundary+) or Ending (boundary-) (parameters base, boundary)
• Strategy Choice: Single, Round-Robin or Random (parameter(s) allocation strategie(s))

Of course, the framework also allows to develop custom components.

Run

The frameworks gives two examples of launching:

• On synthetic sequences (Front, Queue, Both or Random)
• On Wikipedia pages

Once again, custom synthetic sequences can be added, and other kinds of real collaborative edited documents complying with the provided interface can be added.

Synthetic Documents Experiments

Table 1. Boundary setup with a single boundary+ strategy and constant base=2¹⁰, boundary=10.

nbInsert	FRONT				QUEUE				RANDOM
	id lenght		id bit-lenght		id lenght		id bit-lenght		id lenght		id bit-lenght
	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX
100	19.3	39	193.3	390	1	1	10	10	2.43	5	24.3	50
1000	197.2	397	1972.4	3970	2.92	5	29.2	50	3.63	7	36.3	70
5000	X	X	X	X	12.54	25	125.42	250	4.5	10	45	100
10000	X	X	X	X	24.62	49	246.2	490	4.87	11	48.7	110
50000	X	X	X	X	121.7	243	1217	2430	5.73	13	57.3	130
100000	X	X	X	X	X	X	X	X	6.09	14	60.8	140

Table 2. Doubled base setup experiment. Parameters are boundary+ strategy and base=2^4+depth, boundary=10.

nbInsert	FRONT				QUEUE				RANDOM
	id lenght		id bit-lenght		id lenght		id bit-lenght		id lenght		id bit-lenght
	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX
100	20.26	41	365.26	1025	3.19	4	19.91	26	2.01	5	11.38	35
1000	197.47	404	27336.5	83426	6.35	8	49.78	68	3.24	7	20.44	56
5000	X	X	X	X	8.69	10	77.9	95	4.04	9	27.1	81
10000	X	X	X	X	9.69	11	91.64	110	4.4	10	30.4	95
50000	X	X	X	X	11.96	13	126.26	143	5.24	13	38.4	143
100000	X	X	X	X	12.97	14	143.3	161	5.6	13	42	143
500000	X	X	X	X	15.4	17	186.67	221	6.42	15	50.9	180

Table 3. Round-Robin setup experiment. Both boundary+ and boundary- are employed with constant base=2¹⁰ and boundary=10.

nbInsert	FRONT				QUEUE				RANDOM
	id lenght		id bit-lenght		id lenght		id bit-lenght		id lenght		id bit-lenght
	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX
100	1.97	2	19.7	20	1	1	10	10	2.2	4	22.1	40
1000	5.93	10	59.3	100	4.83	9	48.3	90	3.51	7	34.1	70
5000	25.42	50	254.2	500	23.6	47	235.7	470	4.25	9	42.5	90
10000	49.39	98	494	980	47.5	95	475.4	950	4.62	10	46.2	100
50000	X	X	X	X	X	X	X	X	5.46	11	54.6	110
100000	X	X	X	X	X	X	X	X	5.82	13	58.2	130

Table 4. LSEQ setup experiment. Random strategy choice with a doubled base. Strategies : boundary+ and boundary- with base=2^4+depth, boundary=10.

nbInsert	FRONT				QUEUE				RANDOM
	id lenght		id bit-lenght		id lenght		id bit-lenght		id lenght		id bit-lenght
	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX	AVG	MAX
100	3.25	4	20.4	26	4.05	7	27.73	56	2.16	4	12.4	26
1000	7.77	9	67.1	81	7.72	9	65.93	81	3.35	7	21.3	56
5000	9.36	10	86.6	95	11.04	13	113.5	143	4.13	10	28	95
10000	10.62	12	105.5	126	12.02	13	128.3	143	4.5	10	31.23	95
50000	12.46	14	134.5	161	14.11	16	164.9	200	5.35	11	39.47	110
100000	13.26	15	148.3	180	15.06	16	182.5	200	5.71	12	43.2	126
500000	15.42	17	189.3	221	16.3	17	207.5	221	6.54	14	52.2	161
1M	16.38	18	208.9	243	17	18	221.8	243	6.9	15	56.31	180