1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
# The empty quorum commits "everything". This is useful for its use in joint
# quorums.
committed
----
<empty majority quorum>∞
# A single voter quorum is not final when no index is known.
committed cfg=(1) idx=(_)
----
idx
? 0 (id=1)
0
# When an index is known, that's the committed index, and that's final.
committed cfg=(1) idx=(12)
----
idx
> 12 (id=1)
12
# With two nodes, start out similarly.
committed cfg=(1, 2) idx=(_,_)
----
idx
? 0 (id=1)
? 0 (id=2)
0
# The first committed index becomes known (for n1). Nothing changes in the
# output because idx=12 is not known to be on a quorum (which is both nodes).
committed cfg=(1, 2) idx=(12,_)
----
idx
x> 12 (id=1)
? 0 (id=2)
0
# The second index comes in and finalize the decision. The result will be the
# smaller of the two indexes.
committed cfg=(1,2) idx=(12,5)
----
idx
x> 12 (id=1)
> 5 (id=2)
5
# No surprises for three nodes.
committed cfg=(1,2,3) idx=(_,_,_)
----
idx
? 0 (id=1)
? 0 (id=2)
? 0 (id=3)
0
committed cfg=(1,2,3) idx=(12,_,_)
----
idx
xx> 12 (id=1)
? 0 (id=2)
? 0 (id=3)
0
# We see a committed index, but a higher committed index for the last pending
# votes could change (increment) the outcome, so not final yet.
committed cfg=(1,2,3) idx=(12,5,_)
----
idx
xx> 12 (id=1)
x> 5 (id=2)
? 0 (id=3)
5
# a) the case in which it does:
committed cfg=(1,2,3) idx=(12,5,6)
----
idx
xx> 12 (id=1)
> 5 (id=2)
x> 6 (id=3)
6
# b) the case in which it does not:
committed cfg=(1,2,3) idx=(12,5,4)
----
idx
xx> 12 (id=1)
x> 5 (id=2)
> 4 (id=3)
5
# c) a different case in which the last index is pending but it has no chance of
# swaying the outcome (because nobody in the current quorum agrees on anything
# higher than the candidate):
committed cfg=(1,2,3) idx=(5,5,_)
----
idx
x> 5 (id=1)
> 5 (id=2)
? 0 (id=3)
5
# c) continued: Doesn't matter what shows up last. The result is final.
committed cfg=(1,2,3) idx=(5,5,12)
----
idx
> 5 (id=1)
> 5 (id=2)
xx> 12 (id=3)
5
# With all committed idx known, the result is final.
committed cfg=(1, 2, 3) idx=(100, 101, 103)
----
idx
> 100 (id=1)
x> 101 (id=2)
xx> 103 (id=3)
101
# Some more complicated examples. Similar to case c) above. The result is
# already final because no index higher than 103 is one short of quorum.
committed cfg=(1, 2, 3, 4, 5) idx=(101, 104, 103, 103,_)
----
idx
x> 101 (id=1)
xxxx> 104 (id=2)
xx> 103 (id=3)
> 103 (id=4)
? 0 (id=5)
103
# A similar case which is not final because another vote for >= 103 would change
# the outcome.
committed cfg=(1, 2, 3, 4, 5) idx=(101, 102, 103, 103,_)
----
idx
x> 101 (id=1)
xx> 102 (id=2)
xxx> 103 (id=3)
> 103 (id=4)
? 0 (id=5)
102
|
