Say, we have N
number of accounts with positive balances B_1, ..., B_n
.
We can make a transfer T(from,to,amount)
which moves certain amount of balance between accounts.
We have knowledge about an optimal distribution of balances O_1, ..., O_n
.
The question is: How can we find the minimum set of transfers that achieve the optimal distribution? Can we always get away with N-1
transfers at most?
Example:
Balances {0}: 10, {1}: 40, {2}: 50
Optimal {0}: 20, {1}: 60, {2}: 20
T(2,0,10) => {0}: 20, {1}: 40, {2}: 40
T(2,1,20) => {0}: 20, {1}: 60, {2}: 20
Round-robin load balancing is the simplest and most commonly-used load balancing algorithm.
There are two primary approaches to load balancing. Dynamic load balancing uses algorithms that take into account the current state of each server and distribute traffic accordingly. Static load balancing distributes traffic without making these adjustments.
The weighted least connections algorithm maintains a weighted list of application servers with their number of active connections. The service forwards a new connection to a server based on the following combination: Its proportion to the weight or preference. Its number of active connections.
Yes, you can always get away with no more than N-1
transfer. Here is a proof by induction:
N=2
, it is obvious that no more than a single transfer is required.N>2
, there are two cases:
i
and j
such that B_i > O_i
and B_j < O_j
. Transfer min(B_i - O_i, O_j - B_j)
from account i
to account j
. This balances one of the two accounts, thereby reducing the problem to the N-1
case.
The proof is constructive, giving you an algorithm. The algorithm does not attempt to minimise the number of transfers.
It is easy to come up with heuristics for reducing the number of steps. It is a bit late in the day for me to be thinking hard about optimality, but it would not surprise me if the problem turned out to be NP-hard.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With