Parallel continuous randomized load balancing (extended abstract)
Petra Berenbrink, Tom Friedetzky, Ernst W Mayr · 1998
) Petra Berenbrink Department of Mathematics and Computer Science Paderborn University, Germany Email: [email protected] Tom Friedetzky and Ernst W. Mayr y Institut fur Informatik Technische Universitat Munchen, Germany Email: (friedetz---mayr)@informatik.tu-muenchen.de Abstract Recently, the subject of allocating tasks to servers has attracted much attention. There are several ways of distinguishing load balancing problems. There are sequential and parallel strategies, that is, placing the tasks one after the other or all of them in parallel. Another approach divides load balancing problems into continuous and static ones. In the continuous case new tasks are generated and consumed as time proceeds, in the second case the number of tasks is fixed. We present and analyze a parallel randomized continuous load balancing algorithm in a scenario where n processors continuously generate and consume tasks according to some given probability distribution. Each processor initiates l...