Computer Science Department
University of Erlangen-Nuremberg, Germany
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 divergence (see [RSW98]). 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 perfectly balanced.
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.
Full article in PDF (190 KB)
Copyright Notice: ęSpringer-Verlag, Berlin Heidelberg 2007.
Proc. 13th European Conference in Parallel Processing (Euro-Par), pp. 805-814, 2007.