Bond distribution to new vaults would be more even if back-and-forth rather than cycled
This line of thought was prompted by discussion related to #1467 (closed) (shuffling in node distribution)
while being distinct from it (in that not touching on shuffling).
The current code I believe cycles through the vaults, assigning nodes in turn from largest node bond downwards.
Consider if there were 10 nodes, bonds 1 through 10, to be distributed between 5 vaults.
On the first cycle, Vault 1 would get 10 and Vault 5 would get 6.
On the second cycle, Vault 1 would get 5 and Vault 5 would get 1.
At the end, the vaults would have bond sizes of 15 / 13 / 11 / 9 / 7.
Maybe still secure (according to funds migrated, influenced by GetMostSecure
), but certainly unbalanced.
(My impression is that for any hypothetical situation, in every cycle the first vault gets more bond than the last,
with the gap widening the more cycles there are (e.g. 20 cycles for 100 nodes into 5 vaults).)
If there were 11 nodes then Vault 1 would get even more, and if there were 9 nodes then Vault 5 would get even less.
This appears to me to be undesired/suboptimal.
Rather, a preferable distribution pattern would be to go back and forth:
Vaults 1 through 5 get 10 through 6, as before.
Next is Vault 5 again (which has the least), 6+5 = 11.
Going back the other way, next is Vault 4 (which now has the least). 7+4 = 11 et cetera,
all ending up with 11 in this example.
A caveat is that, in order to maintain +/-1 equal node numbers per vault,
in practice this might not always be adding the next bond to the smallest-bond vault.
Nevertheless, my impression is that (for the result) it would be no worse and definitely better than the current approach.
How then to implement it?
Not with sorting, since (for node number per vault) a rigid back-and-forth is preferable to a repeated summed-bond sort.
(This is also convenient from a performance perspective.)
|
Golang integer division (I believe) rounds down.
Here, oddness or evenness of na relative to groupNum can be used to determine whether we are on the way down or on the way back.
At time of writing, I thus propose this (alternatives welcome):
groups := make([]NodeAccounts, groupNum)
var onTheWayBack, position, targetGroup int
for i, na := range nas {
// Go back and forth for more even distribution than cycling.
onTheWayBack = (i / groupNum) % 2
position = i % groupNum
targetGroup = onTheWayBack * ((groupNum - 1) - 2 * position) + position
groups[targetGroup] = append(groups[targetGroup], na)
}
In the above example (groupNum 5):
For the first five loops
i is 0 through 4,
position is likewise 0 through 4,
and targetGroup is 0+0, 0+1, 0+2, 0+3, 0+4.
For the next five loops
i is 5 through 9,
position is again 0 through 4,
and targetGroup is 0+0, 0+1, 0+2, 0+3, 0+4.
targetGroup is 4-0, 4-1, 4-2, 4-3, 4-4.