We must quantify the total number of requests in the system.
Analyzing DFS: Assumptions
Work at any processor can be partitioned into independent pieces as long as its size exceeds a threshold ε.
A reasonable work-splitting mechanism is available.
If work w at a processor is split into two parts ψw and (1 - ψ)w, there exists an arbitrarily small constant α (0 < α ≤ 0.5), such that ψw > αw and (1 - ψ)w > αw.
The costant α sets a lower bound on the load imbalance from work splitting.
Analyzing DFS
If processor Pi initially had work wi, after a single request by processor Pj and split, neither Pi nor Pj have more than (1 - α)wi work.
For each load balancing strategy, we define V(P) as the total number of work requests after which each processor receives at least one work request (note that V(p) ≥ p).
