Which model is "right" ?


A: static power = 0
B: static power = constant

A: dynamic power = speed cubed
B: dynamic power = speed to the alpha for some alpha > 0

A: allowable speeds = discrete speeds s_1, ..., s_k
B: allowable speeds = continuous in the range [0, s_mas]
C: allowable speeds = continuous in the range [0, infinite)

Key point: What best models reality it not necessarily
gives the greatest insight


Review of local competitiveness

Theorem: SRPT is optimal for total flow
proof: Let n(t, A) be the number of jobs alive for algorithm
A at time t

Lemma: Total flow for A = integral of t of n(t, A)

Lemma: For all t, for all Opt, n(t, SRPT) <= n(t, Opt)

end proof

Theorem: Every nonclairvoyant algorithm (ie one that doesn't
know job sizes) can produce schedules with total flow huge 
(n^{1/3} times) compared to optimal

Theorem: SETF (which shares the processor equally among
all jobs that have been run the least) wth a speed 1+epsilon
processor is (1+epsilon)/epsilon competitive, 
i.e. has total flow at most (1+epsilon)/epsilon 
times optimal on a unit speed processor
proof:
Lemma: For all t, for all Opt, 
n(t, SETF with speed 1+epsilon) <= 
((1+epsilon)/epsilon) *n(t, Opt with unit speed)
end proof

Why won't local competitiveness work for the YDS problem?


Key equation for amortized local c-competitiveness:

online cost at time t + change bank account Phi <= c * adversary cost at time t

Normally bank account initially and finally empty


In the context of YDS:

P_a(t) + dPhi/dt <= c P_o(t)
or equivalently
s_a^3(t) + dPhi/dt <= c s_o^3(t)

where P = power, s=speed, subscript a is for algorithm OA and o for optimal
and t is current time


Let try to build intuition for Phi. Assume a common deadline d.
Let w = remaining work

Case A: Optimal is done
The Phi better be at least (d-t) (w_a/(d-t))^3


Case B: Optimal has w_o work left
The Phi better be at least 
(d-t) (w_a/(d-t))^3  - c * (d-t) (w_o/(d-t))^3

Question: Why won't 
(d-t) (w_a/(d-t))^3  - c * (d-t) (w_o/(d-t))^3
work? 
Answer: Job arrivals wont' work when w_a >> w_o

Inspiration that has since become a common trick:
Phi = some constant beta * (d-t) ((w_a-w_o)/(d-t))^3  


Arrivals and job completitions are now easy.
Consider running jobs


dPhi/dt = beta*
[3(d-t)^2 (w_a-w_o)^2 (s_o-s_a) + 2 (w_a-w_o)^2 (d-t)]/(d-t)^4
which uses dw/dt=-s and d(d-t)/dt= 1

Simplifying we get

dPhi/dt = beta*
3 ((w_a-w_o)/(d-t))^2 (s_o-s_a) + 2 ((w_a-w_o)/(d-t))^3 


so the key equation becomes

s_a^3 + 
beta* 3 ((w_a-w_o)/(d-t))^2 (s_o-s_a) + 2 ((w_a-w_o)/(d-t))^3 
<= s_o^3

now substitute in s_a = (w_a/(d-t))

(w_a/(d-t))^3 + 
eta* 3 ((w_a-w_o)/(d-t))^2 (s_o- ((w_a-w_o)/(d-t))) + 2 ((w_a-w_o)/(d-t))^3 
<= s_o^3

Now think a while, pull out Littlewood and Hardy's inequalities book ...
to verify

Key Point: Amortized local competitiveness turns the global analysis
of  energy into a problem of locally (in time) verifying that the
key equation holds