Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Analyzing an Infinite Parallel Job Allocation Process
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 1461/1998 |
| Book | Algorithms — ESA’ 98 |
| DOI | 10.1007/3-540-68530-8 |
| Copyright | 1998 |
| ISBN | 978-3-540-64848-2 |
| DOI | 10.1007/3-540-68530-8_35 |
| Page | 1 |
| Subject Collection | Computer Science |
| SpringerLink Date | Thursday, January 01, 1998 |
| |
|
Analyzing an Infinite Parallel Job Allocation Process
Micah Adler5  , Petra Berenbrink6 and Klaus Schröder7
| (5) |
Department of Computer Science, University of Toronto, Canada |
| (6) |
Department of Mathematics and Computer Science, Paderborn University, Germany |
| (7) |
Heinz Nixdorf Institute and Department of Mathematics and Computer Science, Paderborn University, Germany |
Abstract
In recent years the task of allocating jobs to servers has been studied with the “balls and bins” abstraction. Results in
this area exploit the large decrease in maximum load that can be achieved by allowing each job (ball) a very small amount
of choice in choosing its destination server (bin). The scenarios considered can be divided into two categories: sequential, where each job can be placed at a server before the next job arrives, and parallel, where the jobs arrive in large batches that must be dealt with simultaneously. Another, orthogonal, classification of load
balancing scenarios is into fixed time and infinite. Fixed time processes are only analyzed for an interval of time that is known in advance, and for all such results thus far
either the number of rounds or the total expected number of arrivals at each server is a constant. In the infinite case, there
is an arrival process and a deletion process that are both defined over an infinite time line.
In this paper, we present an algorithm for allocating jobs arriving in parallel over an infinite time line. While there have
been several results for the infinite sequential case, no analogous results exist for the infinite parallel case. We consider
the process where m jobs arrive in each round to n servers, and each server is allowed to remove one job per round. We introduce a simple algorithm, where it is sufficient
for each job to choose between 2 random servers, that obtains the following result: if m ≤
n
6e
, then for any given round, the probability that any job has to wait more than
(log log n) rounds before being processed is at most 1= n
α for any constant α. Furthermore, we analyze the distribution on waiting times: with the same probability, the number of jobs of any given round
that have to wait t + c rounds to be processed is at most
for a small constant c. These results are comparable with existing results for the infinite sequential case.
Supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada, and by ITRC, an Ontario
Centre of Excellence. This research was conducted in part while he was at the Heinz Nixdorf Institute Graduate College, Paderborn,
Germany.
Supported by DFG-SFB 376 “Massive Parallelität”, and by EU ESPRIT Long Term Reseach Project 20244 (ALCOM-IT).
Supported by the DFG-Graduiertenkolleg “Parallele Rechnernetzwerke in der Produktionstechnik”, by DFG-SFB 376 “Massive Parallelität”,
and by EU ESPRIT Long Term Reseach Project 20244 (ALCOM-IT).
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|