Inconsistent ordering in RGA merge method
Consider these states, assuming element 6 has a smaller timestamp than element 4 (possible if Replica B performs other operations, or has a larger DCUId) :
Expected Faulty ordering
Replica A Replica B (ok on A) on B
1362 13452 134562 134526
1 1 1 1
/ \ / \ / \ / \
3 2 3 2 3 2 3 2
\ / / \ / \___
6 4 4 6 4 6
| | |
5 5 5
Note: 5 is not necessary to see the bug, but it helps understanding what should be done.
Elements are added following numbers order :
- 1, 2 and 3 are added and synchronized
- 6 is added on A, 4 and 5 on B (concurrently)
- when merging A to B, 6 is appended at the end of the array instead of being inserted after 5
- merging B to A (before or after A to B) gives the expected ordering, leading to different orderings in the two replicas.
The problem lies in RGA.mergeProtected() :
if (foundWeaker == false) { // No weaker node exist.
index = this.nodes.size
}
This case should be handled by searching upper levels of the tree to find its next sibling.