Slide 29 of 47
Notes:
The Differential PVM Strategy’s competitive ratio is unknown. One can easily prove that no strategy can have a competitive ratio smaller than the difference between the strongest machine and the weakest machine in any given resource.
Consider a system of 10,000 identical machines, plus one with as much memory as all the others combined. An adversary creates 10,000 jobs that fill a normal machine’s memory exactly and one job that fills the huge memory exactly. The system cannot tell them apart. Whenever a new job comes in, the scheduler must place it on the machine with the huge memory or risk a competitive ratio of 10,000. However, if it does so for every job, it receives a competitive CPU load ratio of 10,001.
In practice, we have demonstrated that the Differential PVM Strategy performs well, keeping most of the power of the Enhanced PVM Strategy.
