We investigate the following very simple
load-balancing algorithm on the N
which we call Odd-Even Transposition Balancing
The edges of the cycle are partitioned into two matchings canonically.
A matching defines a single step, the two matchings
form a single round.
Processors connected by an edge of the matching perfectly
balance their loads, and, if there is an
excess token, it is sent to the lower-numbered
The difference between the real process where the
tokens are assumed integral and the
idealized process where the tokens are assumed
divisible can be expressed in terms of the local
We show that Odd-Even Transposition Balancing
has a local divergence of N/2-1.
Combining this with previous results, this shows that
after O(N2log (KN)) rounds,
any input sequence with initial imbalance K is
Experiments are presented that show that
the number of rounds necessary to perfectly balance
a load sequence with imbalance K that has been obtained
by pre-balancing a random sequence with much larger imbalance is
significally larger than the average number
of rounds necessary for balancing random sequences with imbalance K.