Model

Naive retry on one pointer

One winner per round: all n writers need about n²T/2 to finish.

T_{all} \approx \frac{n ^{2} T}{2}

How it behaves

One input on the horizontal axis, the others held fixed.

Data table

Time to land every commit, by writers (T = 50 ms)
Writers n	Time until all have committed
1	25 ms
1.61	65 ms
2.23	124 ms
2.84	201 ms
3.45	298 ms
4.06	413 ms
4.67	546 ms
5.29	699 ms
5.9	870 ms
6.51	1.06 s
7.13	1.27 s
7.74	1.5 s
8.35	1.74 s
8.96	2.01 s
9.57	2.29 s
10.2	2.59 s
10.8	2.92 s
11.4	3.26 s
12	3.62 s
12.6	3.99 s
13.3	4.39 s
13.9	4.8 s
14.5	5.24 s
15.1	5.69 s
15.7	6.16 s
16.3	6.65 s
16.9	7.16 s
17.5	7.69 s
18.1	8.24 s
18.8	8.8 s
19.4	9.38 s
20	9.99 s
20.6	10.6 s
21.2	11.2 s
21.8	11.9 s
22.4	12.6 s
23.1	13.3 s
23.7	14 s
24.3	14.7 s
24.9	15.5 s
25.5	16.3 s
26.1	17 s
26.7	17.9 s
27.3	18.7 s
27.9	19.5 s
28.6	20.4 s
29.2	21.3 s
29.8	22.2 s
30.4	23.1 s
31	24 s
31.6	25 s
32.2	26 s
32.9	27 s
33.5	28 s
34.1	29 s
34.7	30.1 s
35.3	31.2 s
35.9	32.2 s
36.5	33.4 s
37.1	34.5 s
37.8	35.6 s
38.4	36.8 s
39	38 s
39.6	39.2 s
40.2	40.4 s
40.8	41.6 s
41.4	42.9 s
42	44.2 s
42.6	45.5 s
43.3	46.8 s
43.9	48.1 s
44.5	49.5 s
45.1	50.9 s
45.7	52.2 s
46.3	53.7 s
46.9	55.1 s
47.5	56.5 s
48.2	58 s
48.8	59.5 s
49.4	61 s
50	62.5 s

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Transactions & Concurrency Control
What happens when many users change the same data at the same time, and how do we keep the result correct?
$n^{2} T /2$
Read it in place →