HANDLING OVERLOAD CONDITIONS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 301

PROOF OF THE BOUND

Whenever the player chooses to schedule a task J i , the sequence stops with J i +1 and

the ratio of the cumulative values is

C i
j =0 C j + C i +1

1
k .

ϕ i = =

However, if the player chooses to schedule the last task J m , the ratio of the cumulative
values is

C m
j =0 C j

ϕ m = .

Note that if k and m can be chosen such that ϕ m ≤ 1 /k ; that is,

C m
j =0 C j ≤

1
k ,

(9.4)

then we can conclude that, in the worst case, a player cannot achieve a cumulative
value greater than 1 /k times the adversary's value. Note that

C m
j =0 C j

C m
m− 1
j =0

C m C m

kC m− 1

= = = .

m− 1
j =0

C j + kC m− 1 − m− 1

C j + C m C j

j =0

Hence, if there exists an m that satisfies Equation (9.4), it also satisfies the following
equation:

C m ≤ C m− 1 .

(9.5)

Thus, (9.5) is satisfied if and only if (9.4) is satisfied.

From (9.4) we can also write

i +1

C i +2 = kC i +1 − C j

j =0

i

C i +1 = kC i − C j ,

j =0

and subtracting the second equation from the first one, we obtain

C i +2 − C i +1 = k ( C i +1 − C i ) − C i +1 ;

that is,

C i +2 = k ( C i +1 − C i ) .