It’s in the Block States > Dead(PeerId) > Trigger for voting:
“we take the Hash of the event H. Then if H % 2^age == 0 for any peer (sorted by age ascending) in our section, we relocate this node to the neighbour that has the lowest number of peers.”
The bold text indicates younger nodes are preferred for relocation. But rfc0045 says prefer older nodes, so there is a conflict.
I think I have found the problems in the algorithm:
The sections that have a shorter prefix should be chosen in priority as target of relocations, even if they have more nodes. This is the main problem and it is only one line to modify.
There is a mysterious hard coded rule that suppress node ageing when the event concerns a non-adult node in a section with a prefix length > 4 that doesn’t do any good.
With these modifications the simulation is beginning to fly (with 75 sections created). It is not yet perfect because there are still a lot of young node rejections (70%), but the situation is unblocked.
I also think that relocations implementing a change of owning sections during a split or a merge shouldn’t trigger other relocations in cascade to avoid destabilizing newly created sections. This means that the Gone and Live events generated by a split or merge operations shouldn’t count for node ageing. The result is almost the same: 71 sections but there are less merge events (280 instead of 377) which demonstrates a more stable network. This one is debatable.
I have just uploaded my modifications in my fork, but I haven’t analyzed all the consequences. If you want to study them.
Thanks for the clarification. Instinctively, I would think that you would want to relocate an elder rather than a young node to an unhealthy neighbouring section. The reason for this is that the if a neighbour is already in trouble, you don’t want to send an untrusted adversary its way. This seems like a preferred option as long as the section from which the chosen elder is leaving has enough elders to remain healthy. I may have my thinking backward on this, but this is the sentiment that first comes to mind…
I didn’t explain why this is needed: what we observe currently during the simulations are successive splits that create a completely unbalanced network, for example () => 0 & 1, 0 => 00 & 01, 01 => 010 & 011, 010 => 0100 & 0101, 0101 => 01010 & 01011. Here there are 6 sections: 1, 00, 011, 0100, 01010 and 01011 with distinct prefix lengths instead of similar ones. At one time the shorter prefix needs a merge which triggers a generalized merge of all the sections that recreates the section with zero length prefix ().
And then the cycle begins again. This creates a oscillating phenomenon from 1 section to a few ones.
By selecting the target section for relocation with the shorter prefix, we insure that a section with a long prefix won’t be split and so an unbalanced network is not created.
Of course, if there are several sections with a short prefix then the smaller section must be selected among them.
Nice catch, Thierry. Avoid, at all costs, a cascade merging, the greatest fear, seems the most reasonable option.
And adding a step in the random relocation, forcing the new node to find a key in the neighbouring section with shorter prefix, could be the best of both worlds.
Hey @tfa, thanks for this! @bart is away for a couple of days, so I’ll be looking into this in the meantime. Let me get back to you once I have something.
Your modifications certainly made things better, but it still isn’t enough. For example, we are still seeing sections of ~1000 nodes, which is way too much (ideal section size is between 20 - 30 nodes). We are currently trying different approach and will update as soon as we have some results.
Yes, the algorithm must be improved because sections are still too big and there are too many node rejections, but I don’t observe as big sections as you do. With default settings (no arguments given) I get 71 sections with 154 nodes on average (min size is 33 and max is 431).
This is the result with my fork, but you have made some modifications since the fork, I will try to merge them when I have time, to see how things evolve.
My random seed is: AGE_SEED="[1070056145, 2737779209, 2756500248, 3832683655]"
I have rebased my code on Maidsafe new version and I got similar results. The number of sections is now only 65, which is not very far from previuos result (71). Maybe the difference is due to the new drop probability distribution, which I suppose is a better model of outside world (not under vaults control).
I also noticed that the age penalty for a rejoining node is now less severe (minus 1 instead of divided by 2). Maybe this is a good thing for people who need to restart their vault.
After that I made an experiment and added 1 to the number of trailing zeros so that a relocation is done at each event and not just every other event. The results are better (but still not perfect):
57843 rejections (instead of 70874)
102 sections (instead of 65)
Then I replaced boolean norejectyoung parameter by a numerical one that indicates the number of allowed young peers in a section. Modifying this parameter can generate slightly better results:
Max Young
Rejections
Sections
1
57843
102
2
56780
119
3
56242
104
4
56002
83
We can observe that the optimum is to allow 2 young nodes (age = 1) in a section.
I have updated my repository with this code and the specific command generate this configuration is:
Cheers for the testing, just a small point.
I suspect age start at 4 is actually here we want to be. 1-3 is just work for the network, but 4 means a node does some work and the network does minimum.
I tested with init_age = 4 and different values for max_young parameters. The results were not good.
Then I realized that, in my modification to insure a relocation is done for every event, I must add init_age instead of simply 1. With this modification the results are much better:
Rejections: 44357
Sections: 2073
Average section size: 19.33
But in return the simulation is now much longer to execute (about 53 mn), so I have only tested with max_young=1. I will test other values later. But I think that a great step has already been made.
I have tested with different values for max_young parameter and the results are very good:
Max Young
Sections
Rejections
∞
2360
0
1
2073
44357
2
3642
31845
3
4042
25093
4
4122
21000
5
4108
17795
6
4125
15389
7
4098
13608
8
4088
11936
9
4080
10745
10
4084
9651
There is large plateau with more than 4000 sections. This means we don’t need to be very precise on the number of young nodes allowed in a section, though we cannot completely remove the control, as demonstrated by the first line.
Then I have specifically analyzed the results with max_young=6 (meaning that 6 young nodes are allowed in a section). Here are different metrics computed from the number of nodes in each section, group by prefix length:
Prefix len
Count
Average
Min
Max
11
55
27.62
15
48
12
3902
16.58
10
32
13
168
14.10
10
22
All
4125
16.62
10
48
Count is the number of sections having the prefix length (for example there are 55 sections with prefix length 11), and average, min, max are aggregates values computed on the number of nodes of these sections (for example the average size of these 55 sections is 27.62 nodes).
Lastly, for @digipl, the nodes by final age in this configuration:
Just wondering what the plateau situation is like in comparison. Is it all length 12? Is there some “control system” mechanism that drives the optional prefix length to be 12 and sections eventually become mostly prefix length 12.
I think it might be beneficial to see that analysis for all above max_young == 6 and at least for max_young == 10
We do already gave such a mechanism in place, however I think that as the network grows the balance happens naturally. So the option is more complex code to force/help balance or allow the natural balance which in some ways is nice as that is also how data distributes in a balanced manner.
The aim of the “control system” implemented in the vaults is to insure the safety and efficiency of the network. This includes, among other things, the need to get a well-balanced prefix tree, which means few distinct values for the prefix length (ideally 1 or 2).
In this configuration (young_max=6) the result is good because we have 3 values but with few sections having the min or the max prefix length (1.33% of the sections with the min prefix length and 4% with the max prefix length).
Of course, the target is not specifically 12 and the value depends on the size of the network. For example, after 4000 iterations (instead of 100000), the node distribution is:
Prefix len
Count
Average
Min
Max
Standard dev
7
123
21.37
18
28
1.71
8
10
16.40
12
23
3.34
All
133
21.00
12
28
2.28
And after 20000 iterations:
Prefix len
Count
Average
Min
Max
Standard dev
9
222
26.75
18
31
1.98
10
580
13.30
8
23
2.13
All
802
17.02
8
31
6.37
The results with max_young=10 after 100000 iterations is:
One thing important for the limit of young nodes per section is to help with the situation when the network is relatively quiet. That is a possible attack vector for large adversaries who would try and flood the network at that time. So the limit effectively stops the flood from being too large and if there was growth then many other nodes would jump on the join queue (even other attackers, which is ok). This is the same protection really that states the network should only accept nodes when in needs them.
Both points for sure debatable and I think @mav has already made good arguments against that proposal. Personally I am on the fence, but slightly in favour of this protection.