Function sp_npos_elections::balancing::balance

pub fn balance<AccountId: IdentifierT>(
    voters: &mut Vec<Voter<AccountId>>,
    config: &BalancingConfig,
) -> usize

Balance the weight distribution of a given voters at most iterations times, or up until the point where the biggest difference created per iteration of all stakes is tolerance. If this is called with tolerance = 0, then exactly iterations rounds will be executed, except if no change has been made (difference = 0). tolerance and iterations are part of the BalancingConfig struct.

In almost all cases, a balanced solution will have a better score than an unbalanced solution, yet this is not 100% guaranteed because the first element of a crate::ElectionScore does not directly relate to balancing.

Note that some reference implementation adopt an approach in which voters are balanced randomly per round. To advocate determinism, we don’t do this. In each round, all voters are exactly balanced once, in the same order.

Also, note that due to re-distribution of weights, the outcome of this function might contain edges with weight zero. The call site should filter such weight if desirable. Moreover, the outcome might need balance re-normalization, see Voter::try_normalize.

References

• A new approach to the maximum flow problem.
• Validator election in nominated proof-of-stake (Appendix A.)
• Computing a balanced solution, which contains the details of the algorithm implementation.