Competitive distributed job scheduling (extended abstract)
- 1 January 1992
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 571-580
- https://doi.org/10.1145/129712.129768
Abstract
This paper examines the problem of balancing the job load in a network of processors, and introduces an online algorithm for scheduling a sequence of jobs in a competitive manner. The algorithm is shown to be polylog (n)-competitive according to a strict definition that forces the online algorithm to be competitive even when considering any bounded area of the network and bounded period of time.We also analyze the common greedy feedback-based approach, and provide matching lower and upper bounds (up to a polylogarithmic factor) for the tradeoff between the costs of searches and updates under this approach.Keywords
This publication has 0 references indexed in Scilit: