On Packet Scheduling with Adversarial Jamming and Speedup∗
Martin Böhm1 , Lukasz Jeż2 , Jiřı́ Sgall1 , and Pavel Veselý1
1

Computer Science Institute of Charles University, Prague, Czech Republic,
{bohm,sgall,vesely}@iuuk.mff.cuni.cz
2
Institute of Computer Science, University of Wroclaw, Poland, lje@cs.uni.wroc.pl

arXiv:1705.07018v2 [] 5 Oct 2017

Abstract
In Packet Scheduling with Adversarial Jamming packets of arbitrary sizes arrive over time to
be transmitted over a channel in which instantaneous jamming errors occur at times chosen by the
adversary and not known to the algorithm. The transmission taking place at the time of jamming is
corrupt, and the algorithm learns this fact immediately. An online algorithm maximizes the total size
of packets it successfully transmits and the goal is to develop an algorithm with the lowest possible
asymptotic competitive ratio, where the additive constant may depend on packet sizes.
Our main contribution is a universal algorithm that works for any speedup and packet sizes and,
unlike previous algorithms for the problem, it does not need to know these properties in advance. We
show that this algorithm guarantees 1-competitiveness with speedup 4, making it the first known
algorithm to maintain 1-competitiveness with a moderate speedup in the general setting of arbitrary
packet sizes. We also prove a lower bound of φ + 1 ≈ 2.618 on the speedup of any 1-competitive
deterministic algorithm, showing that our algorithm is close to the optimum.
Additionally, we formulate a general framework for analyzing our algorithm locally and use it
to show upper bounds on its competitive ratio for speedups in [1, 4) and for several special cases,
recovering some previously known results, each of which had a dedicated proof. In particular, our
algorithm is 3-competitive without speedup, matching the algorithm and the lower bound of Jurdzinski
et al. [7]. We use this framework also for the case of divisible packet sizes in which the size of a
packet divides the size of any larger packet, to show that a slight modification of our algorithm is
1-competitive with speedup 2 and it achieves the optimal competitive ratio of 2 without speedup,
again matching the algorithm and the lower bound of [7].

1

Introduction

We study an online packet scheduling model recently introduced by Anta et al. [1] and extended by
Jurdzinski et al. [7]. In our model, packets of arbitrary sizes arrive over time and they are to be transmitted
over a single communication channel. The algorithm can schedule any packet of its choice at any time,
but cannot interrupt its subsequent transmission; in the scheduling jargon, there is a single machine and
no preemptions. There are, however, instantaneous jamming errors or faults at times chosen by the
adversary, which are not known to the algorithm. A transmission taking place at the time of jamming is
corrupt, and the algorithm learns this fact immediately. The packet whose transmission failed can be
retransmitted immediately or at any later time.
The objective is to maximize the total size of packets successfully transmitted. In particular, the goal
is to develop an online algorithm with the lowest possible competitive ratio. We focus on algorithms with
resource augmentation, namely on online algorithms that transmit packets s ≥ 1 times faster than the
offline optimum solution they are compared against; such algorithm is often said to be speed-s, running
at speed s, or having a speedup of s. We note that this notion has been introduced for a similar job
scheduling problem [8], in which speedup is required for constant ratio. In contrast, our problem allows
constant ratio with no speedup, so we consider the competitive ratio as a function of it. This deviates
∗ Work partially supported by GA ČR project 17-09142S, GAUK project 634217 and Polish National Science Center
grant 2016/21/D/ST6/02402.

1

from previous work, which focused on the case with no speedup or on the speedup sufficient for ratio 1,
ignoring intermediate cases.
The distinguishing feature of the model is that the number of different packet sizes is a constant and
that these packet sizes are considered to be constants. Thus, the additive term in the definition of the
competitive ratio may depend on the number and values of the packet sizes. (It is easy to observe that,
at speed 1, without such additive term, it is impossible to attain constant competitive ratio that does not
depend on packet sizes, even for only two sizes.)

1.1

Previous Results

The model was introduced by Anta et al. [1], who resolved it for two packet sizes: If γ > 1 denotes the
ratio of the two sizes, then the optimum ratio for deterministic algorithms is (γ + bγc)/bγc, which is
always in the range [2, 3). Anta et al. [1] note that their lower bound strategy applies to randomized
algorithms as well, but their argument only applies to the adaptive adversary model. To our best
knowledge, randomized algorithms for the more common oblivious adversary model were never considered
in this setting. Anta et al. [1] demonstrate the necessity of instantaneous error feedback by proving that
discovering errors upon completed transmission rules out constant competitive ratio. They also provide
improved results for a stochastic online setting.
These results were extended by Jurdzinski et al. [7], who proved that the optimum ratio for the
case of multiple (though fixed) packet sizes is given by the same formula for the two packet sizes which
maximize it. Moreover, Jurdzinski et al. [7] gave further results for divisible packet sizes, i.e., instances
in which every packet size divides every larger packet size, for which the optimum ratio is 2. Namely,
they generalized the 2-competitive algorithm to a setting with f independent transmission channels (or
machines in scheduling parlance); jamming errors on each channel are independent, and a packet can
only be transmitted on one channel at a time. Furthermore, for the single channel divisible case, they
proved that speed 2 is sufficient for 1-competitiveness in the resource augmentation setting.

1.2

Our results

Our main new results concern the analysis of the non-divisible case with speedup, where we show that
speed 4 is sufficient for a competitive ratio of 1 (Section 5). However, our major contribution is a uniform
algorithm that works well in every setting, together with a uniform analysis framework (Section 4). This
contrasts with the results of Jurdzinski et al. [7], where each upper bound was attained by a dedicated
algorithm with independently crafted analysis. Moreover, unlike those algorithms, which all require prior
knowledge of all possible packet sizes and speedup, in the sense that there are different algorithms for
speeds 1 and 2 (only divisible case), with none for intermediate speeds, our algorithm is oblivious in
that it requires no such information. Furthermore, our algorithm is more appealing as it is significantly
simpler and “work-conserving” or “busy”, i.e., transmitting some packet whenever there is one pending,
which is desirable in practice. See Section 2 for the description of our algorithm.
To recover the 1-competitiveness at speed 2 and also 2-competitiveness at speed 1 for divisible instances,
we have to modify our algorithm slightly, as otherwise we can guarantee 1-competitiveness for divisible
instances only at speed 2.5. This is to be expected, as divisible instances are a very special case. The
analysis of the modified algorithm for divisible instances is in Section 7.
On the other hand, we prove that our original algorithm is 1-competitive on far broader class of
“well-separated” instances at sufficient speed: If the ratio between two successive packet sizes (in their
sorted list) is no smaller than α ≥ 1, our algorithm is 1-competitive if its speed is at least Sα , which
is a non-increasing function of α such that S1 = 4 and limα→∞ Sα = 2; see Section 4.2 for the precise
definition of Sα .
In Section 3 we demonstrate that the analyses of our algorithm are mostly tight, i.e., that (a) on
general instances, the algorithm is no better than (1 + 2/s)-competitive for s < 2 and no better than
4/s-competitive for s ∈ [2, 4), (b) on divisible instances, it is no better than 4/3-competitive for s < 2.5,
and (c) it is at least 2-competitive for s < 2, even for two divisible packet sizes. See Figure 1 for a graph
of our bounds on the competitive ratio depending on the speedup.
In Section 6 we complement these results with two lower bounds on speed that is necessary to achieve
1-competitiveness by a deterministic algorithm. The first one proves that even for two divisible packet
sizes, speed 2 is required to attain 1-competitiveness, establishing optimality of our modified algorithm
2

3

Local analysis upper bounds
Upper bound from Theorem 4.1
Hard instances for MAIN

Competitive ratio

2.5

2

1.5

1
1

2

3

4

5

6

Speedup

Figure 1: A graph of our upper and lower bounds on the competitive ratio of MAIN (s). The upper
bounds are from Section 4 and the lower bounds are by hard instances from Section 3.
and that of Jurdzinski et al. [7] for the divisible case. The second lower bound strengthens the previous
construction by showing that for non-divisible instances with more packet sizes, speed φ + 1 ≈ 2.618 is
required for 1-competitiveness. Both results hold even if all packets are released together.

1.3

Related Results

We first mention a few results concerning the model with adversarial jamming. Anta et al. [3] consider
essentially the same problem but with a different objective: minimizing the number and/or the total size
of pending (i.e., not yet transmitted) packets. They focus on multiple channels (or machines, as therein
the problem is formulated as job scheduling), and investigate what speedup is necessary and sufficient
for competitiveness. Note that for 1-competitiveness, minimizing the total size of pending packets is
equivalent to our objective. In Sections 4-7 they obtain a tight bound of 2 on speedup necessary for
1-competitiveness for two packet sizes, although in their lower bound of 2 they do not release all packets
together, unlike we do in our lower bound constructions. In Section 8 they claim to have a 1-competitive
algorithm with speedup 7/2, but the proof is incorrect; even the example in Section 3 showing that our
algorithm is no better than 4/s-competitive for s ∈ [2, 4) works the same way for their algorithm.
Georgio et al. [6] consider the same problem without any speedup, restricted to jobs of unit size, under
various efficiency and correctness measures, again focusing on multiple machines/channels. This article is
motivated by distributed computation, and thus distinguishes between different information models and
ways in which the machines communicate. In yet another work, Anta et al. [2] consider latency on top of
the previous two objectives, and study the competitiveness of popular scheduling algorithms for all these
measures. Garncarek et al. [5] consider “synchronized” parallel channels that all suffer errors at the same
time. This work distinguishes between “regular” jamming errors and “crashes”, which also cause the
algorithm’s state to reset, losing any information stored about the past√events and proves that for two
packet sizes the optimum ratio tends to 4/3 for the former and to φ = ( 5 + 1)/2 ≈ 1.618 for the latter
as the number f of channels tends to infinity.
As mentioned before, Kalyanasundaram and Pruhs [8] introduced resource augmentation. Among
other results they proved that a constant competitive ratio is possible with a constant speedup for a
preemptive variant of real-time scheduling where each job has a release time, deadline, processing time
and a weight and the objective is to maximize the weight of jobs completed by their deadlines on a single
machine. Subsequently resource augmentation was applied in various scenarios. Of the most relevant for

3

us are those that considered algorithms with speedup that are 1-competitive, i.e., as good as the optimum.
We mention two models that still contain interesting open problems.
For real-time scheduling, Phillips et al. [12] considered the underloaded case in which there exists
a schedule that completes all the jobs. It is easy to see that on a single machine, the earliest deadline
first (EDF) algorithm is then an optimal online algorithm. Phillips et al. [12] proved that EDF on m
machines is 1-competitive with speedup 2 − 1/m. (Here the weights are not relevant.) Intriguingly, finding
a 1-competitive algorithm with minimal speedup is wide open: It is known that speedup at least 6/5 is
necessary, it has been conjectured that speedup e/(e − 1) is sufficient, but the best upper bound proven
is 2 − 2/(m + 1) from [11]. See Schewior [13] for more on this problem.
Later these results were extended to real-time scheduling of overloaded systems, where for uniform
density (i.e., weight equal to processing time) Lam et al. [10] have shown that a variant of EDF with
admission control is 1-competitive with speedup 2 on a single machine and with speedup 3 on more
machines. For non-uniform densities, the necessary speedup is a constant if each job is tight (its deadline
equals its release time plus its processing time) [9]. Without this restriction it is no longer constant,
depending on the ratio ξ of the maximum and minimum weight. It is known that it is at least Ω(log log ξ)
and at most O(log ξ) [4, 10]; as far as we are aware, closing this gap is still an open problem.

2

Algorithms, preliminaries, notations

The general idea of the algorithm is that after each error, we start by transmitting packets of small sizes,
only increasing the size of packets after a sufficiently long period of uninterrupted transmissions. It turns
out that the right tradeoff is to transmit a packet only if it would have been transmitted successfully if
started just after the last error. It is also crucial that the initial packet after each error has the right
size, namely to ignore small packet sizes if the total size of remaining packets of those sizes is small
compared to a larger packet that can be transmitted. In other words, the size of the first transmitted
packet is larger than the total size of all pending smaller packets and we choose the largest such size.
This guarantees that if no error occurs, all currently pending packets with size equal to or larger than the
size of the initial packet are eventually transmitted before the algorithm starts a smaller packet.
We start by some notations. We assume there are k distinct non-zero packet sizes denoted by `i
and ordered so that `1 < · · · < `k . For convenience, we define `0 = 0. We say that the packet sizes are
divisible if `i divides `i+1 for all i = 1, . . . , k − 1. For a packet p, let `(p) denote the size of p. For a set of
packets A, let `(A) denote the total size of all the packets in A.
During the run of an algorithm, at time t, a packet is pending if it is released before or at t, not
completed before or at t and not started before t and still running. At time t, if no packet is running, the
algorithm may start any pending packet. As a convention of our model, if a fault (jamming error) happens
at time t and this is the completion time of a previously scheduled packet, this packet is considered
completed. Also, at the fault time, the algorithm may start a new packet.
Let LALG (i, Y ) denote the total size of packets of size `i completed by an algorithm ALG during a
time interval Y . Similarly, LALG (≥ i, Y ) (resp. LALG (< i, Y )) denotes the total size of packets of size at
least `i (resp. less than `i ) completed by an algorithm ALG during a time interval Y ; formally we define
Pk
Pi−1
LALG (≥ i, Y ) = j=i LALG (j, Y ) and LALG (< i, Y ) = j=1 LALG (j, Y ). We use the notation LALG (Y )
with a single parameter to denote the size LALG (≥ 1, Y ) of packets of all sizes completed by ALG during
Y and the notation LALG without parameters to denote the size of all packets of all sizes completed by
ALG at any time.
By convention, the schedule starts at time 0 and ends at time T , which is a part of the instance
unknown to an online algorithm until it is reached. (This is similar to the times of jamming errors, one
can also alternatively say that after T the errors are so frequent that no packet is completed.) Algorithm
ALG is called R-competitive, if there exists a constant C, possibly dependent on k and `1 , . . . , `k , such
that for any instance and its optimal schedule OPT we have LOPT ((0, T ]) ≤ R · LALG ((0, T ]) + C. We
remark that in our analyses we show only a crude bound on C.
We denote the algorithm ALG with speedup s ≥ 1 by ALG(s). The meaning is that in ALG(s),
packets of size L need time L/s to process. In the resource-augmentation variant, we are mainly interested
in finding the smallest s such that ALG(s) is 1-competitive, compared to OPT = OPT (1) that runs at
speed 1.

4

2.1

Algorithms MAIN and DIV

We now give a common description of the two algorithms, MAIN for general packet sizes and DIV for
divisible sizes. We divide the run of the algorithm into phases. Each phase starts by an invocation of the
initial step in which we need to carefully select a packet to transmit as discussed above. The phase ends
by a fault, or when there is no pending packet, or when there are pending packets only of sizes larger
than the total size of packets completed in the current phase. The periods of idle time do not belong to
any phase.
Formally, throughout the algorithm, t denotes the current time. The time tB denotes the start of
the current phase; initially tB = 0. We set rel(t) = s · (t − tB ). Since the algorithm does not insert
unnecessary idle time, rel(t) denotes the amount of transmitted packets in the current phase. (Note that
we use rel(t) only when there is no packet running at time t, so there is no partially executed packet.)
Thus rel(t) can be thought as a measure of time relative to the start of the current phase (scaled by the
speed of the algorithm). Note also that the algorithm can evaluate rel(t) without knowing the speedup,
as it can simply observe the total size of the transmitted packets. Let P <i denote the set of pending
packets of sizes `1 , . . . , `i−1 at any given time.
The description of MAIN and DIV differ only in Step (3), where DIV enforces an additional divisibility
condition.
Algorithm MAIN and DIV
(1) If no packet is available, stay idle until the next release time.
(2) Let i be the maximal i ≤ k such that there is a pending packet of size `i and `(P <i ) < `i .
Schedule a packet of size `i and set tB = t.
(3) Choose the maximum i such that
(i) there is a pending packet of size `i ,
(ii) `i ≤ rel(t) and
(iii) in case of DIV , `i divides rel(t).
Schedule a packet of size `i . Repeat Step (3) as long as such i exists.
(4) If no packet satisfies the condition in Step (3), go to Step 1.
We first note that the algorithm is well-defined, i.e., that it is always able to choose a packet in
Step (2) if it has any packets pending, and that if it succeeds in sending it, the length of thus started
phase can be related to the total size of the packets completed in it.
Lemma 2.1. Let ALG be either MAIN or DIV . In Step (2), ALG always chooses some packet if it has any
pending. Moreover, if ALG completes the first packet in the phase, then LALG(s) ((tB , tE ]) > s·(tE −tB )/2,
where tB denotes the start of the phase and tE its end (by a fault or Step (4)).
Proof. For the first property, note that the packet of the smallest size is eligible. For the second property,
note that there is no idle time in the phase, and that only the last packet chosen by ALG in the phase
may not complete due to a jam. By the condition in Step (3), the size of this jammed packet is no larger
than the total size of all the packets ALG previously completed in this phase, which yields the bound.
The following lemma shows a crucial property of the algorithm, namely that if packets of size `i are
pending, the algorithm schedules packets of size at least `i most of the time. Its proof also explains
the reasons behind our choice of the first packet in a phase in Step (2) of the algorithm. We give the
statement and proof of the lemma for MAIN . For DIV , the first part of the lemma still holds, while the
divisibility condition makes the proof a bit more tedious; on the other hand divisibility of packet sizes
ensures that the bound in the second part of the lemma can be improved. We postpone this tightened
analysis to Section 7 where we analyze DIV .
Lemma 2.2. Let u be a start of a phase in MAIN (s) and t = u + `i /s.
(i) If a packet of size `i is pending at time u and no fault occurs in (u, t), then the phase does not end
before t.
(ii) Suppose that v > u is such that any time in [u, v) a packet of size `i is pending and no fault occurs.
Then the phase does not end in (u, v) and LMAIN (s) (< i, (u, v]) < `i + `i−1 . (Recall that `0 = 0.)

5

Proof. (i) Suppose for a contradiction that the phase started at u ends at time t0 < t. We have
rel(t0 ) < rel(t) = `i . Let `j be the smallest packet size among the packets pending at t0 . As there is no
fault, the reason for a new phase has to be that rel(t0 ) < `j , and thus Step (3) did not choose a packet to
be scheduled. Also note that any packet scheduled before t0 was completed. This implies, first, that there
is a pending packet of size `i , as there was one at time u and there was insufficient time to complete it,
so j is well-defined and j ≤ i. Second, all packets of sizes smaller than `j pending at u were completed
before t0 , so their total size is at most rel(t0 ) < `j . However, this contradicts the fact that the phase
started by a packet smaller than `j at time u, as a pending packet of the smallest size equal to or larger
than `j satisfied the condition in Step (2) at time u. (Note that it is possible that no packet of size `j is
pending at u; however, at least a packet of size `i is pending.)
(ii) By (i), the phase that started at u does not end before time t if no fault happens. A packet of size
`i is always pending by the assumption of the lemma, and it is always a valid choice of a packet in Step
(3) from time t on. Thus, the phase that started at u does not end in (u, v), and moreover only packets
of sizes at least `i are started in [t, v). It follows that packets of sizes smaller than `i are started only
before time t and their total size is thus less than rel(t) + `i−1 = `i + `i−1 . The lemma follows.

3

Examples for MAIN and DIV

Before analyzing the algorithms, we show some hard instances obtaining some lower bounds on the
performance of the algorithms, in some cases matching our upper bounds from later sections. At the
same time, the examples are instructive in understanding some of the choices both in the analysis and
the design of algorithms.

3.1

Examples with general packet sizes

First we give an instance which shows that MAIN (s) has competitive ratio at least 1 + 2/s for s < 2,
matching Theorem 4.4.
Choose a large enough integer N . At time 0 the following packets are released: 2N packets of size 1,
one packet of size 2 and N packet of size 4/s − ε for a small enough ε > 0 such that it holds 2 < 4/s − ε.
These are all packets in the instance.
First there are N phases, each of length 4/s − ε and ending by a fault. OPT completes a packet of
size 4/s − ε in each phase, while MAIN (s) completes 2 packets of size 1 and then it starts a packet of size
2 which is not finished.
Then there is a fault every 1 unit of time, so that OPT completes all packets of size 1, while the
algorithm has no pending packet of size 1 and as s < 2 the length of the phase is not sufficient to finish a
longer packet.
Overall, OPT completes packets of total size 2 + 4/s − ε per phase, while the algorithm completes
packets of total size only 2 per phase. The ratio thus tends to 1 + 2/s as ε → 0.
Next we prove that for s ∈ [2, 4), the ratio of MAIN (s) is at least 4/s > 1, which shows that the
speedup of MAIN (s) in Theorem 5.1 cannot be improved.
Choose a large enough integer y. There will be four packet sizes: 1, x, y and z such that 1 < x < y < z,
z = x + y − 1, and x = y · (s − 2)/2 + 2; as s ≥ 2 it holds x > 1 and as s < 4 we have x ≤ y − 1 for a
large enough y.
We will have N phases again. At time 0 the adversary releases all N (y − 1) packets of size 1, all N
packets of size y and a single packet of size z (never completed by either OPT or MAIN (s)), whereas the
packets of size x are released one per phase.
In each phase MAIN (s) completes, in this order: y − 1 packets of size 1 and then a packet of size x,
which has arrived just after the y − 1 packets of size 1 are completed. Next, it will start a packet of size z
and fail due to a jam. We show that OPT will complete a packet of size y. To this end, it is required
that y < 2(x + y − 1)/s, or equivalently x > y · (s − 2)/2 + 1 which holds by the choice of x.
After these N phases, we will have jams every 1 unit of time, so that OPT can complete all the
N (y − 1) packets of size 1, while MAIN (s) will be unable to complete any packet (of size y or larger).

6

The ratio per phase is
OPT
y−1+y
2y − 1
2y − 1
=
=
= y·s
y·(s−2)
MAIN (s)
y−1+x
y−1+ 2 +2
2 +1
which tends to 4/s as y → ∞.

3.2

Example with two packet sizes

Our next example shows that both algorithms have ratio no smaller than 2 when s < 2, even if packet
sizes are only 1 and ` ≥ max{s + , /(2 − s)} for an arbitrarily small  > 0. This matches upper bounds
given in Theorem 4.4 for MAIN (2) and an upper bound of 2 for DIV . We denote either algorithm by
ALG.
There will be N phases, that all look the same: In each phase, issue one packet of size ` and ` packets
of size 1, and have the phase end by a fault at time (2` − ε)/s ≥ ` which holds by the bounds on `.
Then ALG will complete all ` packets of size 1 but will not complete the one of size `. By the previous
inequality, OPT can complete the packet of size ` within the phase. Once all N phases are over, the jams
occur every 1 unit of time, which allows OPT completing all N ` remaining packets of size 1. However,
ALG is unable to complete any of the packets of size `. Thus the ratio is 2.

3.3

Example for MAIN in the divisible case

We give an example that shows that MAIN is not very good for divisible instances, in particular it is not
1-competitive for any speed s < 2.5 and thus the bound in Theorem 4.5 is tight. In fact, we show that it
is not better than 4/3-competitive. We use packets of sizes 1, `, and 2` and we take ` sufficiently large
compared to the given speed or competitive ratio. There are many packets of size 1 and 2` available at
the beginning, the packets of size ` arrive at specific times where MAIN schedules them immediately.
The faults occur at times divisible by 2`, so the optimum schedules one packet of size 2` in each
phase between two faults. We have N such phases, N (2` − 1) packets of size 1 and N packets of size 2`
available at the beginning. In each phase, MAIN (s) schedules 2` − 1 packets of size 1, then a packet of
size ` arrives and is scheduled, and then a packet of size 2` is scheduled. The algorithm would need speed
2.5 − 1/(2`) to complete it. So, for ` large, the algorithm completes only packets of total size 3` − 1 per
phase. After these N phases, we have faults after time 1, so the optimum schedules all packets of size 1.
The optimum thus finishes all packets 2` plus all small packets, a total of 4` − 1 per phase. Thus the
ratio tends to 4/3 as ` → ∞.

4

Local analysis and results

In this section we formulate a general method for analyzing our algorithms by comparing locally within
each phase the size of “large” packets completed by the algorithm and by the adversary. This method
simplifies a complicated induction used in [7]; we easily obtain the same upper bounds of 2 and 3 on
competitiveness for divisible and unrestricted packet sizes respectively at no speedup, as well as several
new results for the non-divisible cases included in this section. In Section 5, we use a more complex
charging scheme to obtain our main result. We postpone the use of local analysis for the divisible case to
Section 7.
For the analysis, let ALG denote one of the algorithms MAIN and DIV , and let s ≥ 1 be the speedup.
We fix an instance and its schedules for ALG(s) and OPT .

4.1

Critical times and Master Theorem

The common scheme is the following. We carefully define a sequence of critical times Ck ≤ Ck−1 ≤
· · · ≤ C1 ≤ C0 , where C0 = T is the end of the schedule, satisfying two properties: (1) the algorithm has
completed almost all pending packets of size `i released before Ci and (2) in (Ci , Ci−1 ], a packet of size
`i is always pending. Properties (1) and (2) allow us to relate LOPT (i, (0, Ci ]) and LOPT (≥ i, (Ci , Ci−1 ])
respectively to their “ALG counterparts”. As each packet completed by OPT belongs to exactly one of

7

`k

`k
`i
`i−1

`1
Ck

Ci−1

Ci

C2 C1

C0

Figure 2: An illustration of dividing the schedule of OPT in the local analysis. Rows correspond to
packet sizes and the X-axis to time. Gray horizontal rectangles thus correspond to LOPT (i, (0, Ci ]) and
hatched rectangles correspond to LOPT (≥ i, (Ci , Ci−1 ]).
these sets, summing the bounds gives the desired results. These two facts together imply R-competitiveness
of the algorithm for appropriate R and speed s. See Figure 2 for an illustration.
We first define the notion of i-good times so that they satisfy property (1), and then choose the critical
times among their suprema so that those satisfy property (2) as well.
Definition 1. Let ALG be one of the algorithms MAIN and DIV , and let s ≥ 1 be the speedup. For
i = 1, . . . k, time t is called i-good if one of the following conditions holds:
(i) At time t, algorithm ALG(s) starts a new phase by scheduling a packet of size larger than `i , or
(ii) at time t, no packet of size `i is pending for ALG(s), or
(iii) t = 0.
We define critical times C0 , C1 , . . . , Ck iteratively as follows:
• C0 = T , i.e., it is the end of the schedule.
• For i = 1, . . . , k, Ci is the supremum of i-good times t such that t ≤ Ci−1 .
Note that all Ci ’s are defined and Ci ≥ 0, as time t = 0 is i-good for all i.
The choice of Ci implies that each Ci is of one of the three types (the types are not disjoint):
• Ci is i-good and a phase starts at Ci (this includes Ci = 0),
• Ci is i-good and Ci = Ci−1 , or
• there exists a packet of size `i pending at Ci , however, any such packet was released at Ci .
If the first two options do not apply, then the last one is the only remaining possibility (as otherwise
some time in a non-empty interval (Ci , Ci−1 ] would be i-good); in this case, Ci is not i-good but only the
supremum of i-good times.
First we bound the total size of packets of size `i completed before Ci ; the proof actually only uses
the fact that each Ci is the supremum of i-good times and justifies the definition above.
Lemma 4.1. Let ALG be one of the algorithms MAIN and DIV , and let s ≥ 1 be the speedup. Then,
for any i, LOPT (i, (0, Ci ]) ≤ LALG(s) (i, (0, Ci ]) + `k .
Proof. If Ci is i-good and satisfies condition (i) in Definition 1, then by the description of Step (2) of the
algorithms, the total size of pending packets of size `i is less than the size of the scheduled packet, which
is at most `k and the lemma follows.
In all the remaining cases it holds that ALG(s) has completed all the jobs of size `i released before Ci .
Thus the inequality holds trivially even without the additive term.
Our remaining goal is to bound LOPT (≥ i, (Ci , Ci−1 ]). We divide (Ci , Ci−1 ] into i-segments by the
faults. We prove the bounds separately for each i-segment. One important fact is that for the first
i-segment we use only a loose bound, as we can use the additive constant. The critical part is then the
bound for i-segments started by a fault, this part determines the competitive ratio and is different for
each case. We summarize the general method by the following definition and master theorem.
Definition 2. The interval (u, v] is called an initial i-segment if u = Ci and v is either Ci−1 or the first
time of a fault after u, whichever comes first.
8

The interval (u, v] is called a proper i-segment if u ∈ (Ci , Ci−1 ) is a time of a fault and v is either
Ci−1 or the first time of a fault after u, whichever comes first.
Note that there is no i-segment if Ci−1 = Ci .
Theorem 4.2 (Master Theorem). Let ALG denote one of the algorithms MAIN and DIV , and let s ≥ 1
be the speedup. Suppose that R ≥ 1 satisfies that for each i = 1, . . . , k and each proper i-segment (u, v]
with v − u ≥ `i we have
(R − 1)LALG(s) ((u, v]) + LALG(s) (≥ i, (u, v]) ≥ LOPT (≥ i, (u, v]) .

(4.1)

Suppose furthermore that for the initial i-segment (u, v] we have
LALG(s) (≥ i, (u, v]) > s(v − u) − 4`k .

(4.2)

Then ALG(s) is R-competitive.
Proof. First note that for a proper i-segment (u, v], u is a fault time. Thus if v − u < `i , then
LOPT (≥ i, (u, v]) = 0 and (4.1) is trivial. It follows that (4.1) holds even without the assumption
v − u ≥ `i .
Now consider an initial i-segment (u, v]. We have LOPT (≥ i, (u, v]) ≤ `k + v − u, as at most a
single packet started before u can be completed. Combining this with (4.2) and using s ≥ 1, we get
LALG(s) (≥ i, (u, v]) > s(v − u) − 4`k ≥ v − u − 4`k ≥ LOPT (≥ i, (u, v]) − 5`k .
Summing this with (4.1) for all proper i-intervals and using R ≥ 1 we get
(R − 1)LALG(s) ((Ci , Ci−1 ]) + LALG(s) (≥ i, (Ci , Ci−1 ]) + 5`k
≥ LOPT (≥ i, (Ci , Ci−1 ]) .

(4.3)

Note that for Ci = Ci−1 , Equation (4.3) holds trivially.
To complete the proof of the theorem, note that each completed job in the optimum contributes to
exactly one among the 2k terms LOPT (≥ i, (Ci , Ci−1 ]) and LOPT (i, (0, Ci ]); similarly for LALG(s) . Thus
by summing both (4.3) and Lemma 4.1 for all i = 1, . . . , k we obtain
LOPT

=

k
X

LOPT (≥ i, (Ci , Ci−1 ]) +

i=1

≤

k
X

k
X

(R − 1)LALG(s) ((Ci , Ci−1 ]) +

i=1

+

LOPT (i, (0, Ci ])

i=1

k
X

k
X

LALG(s) (≥ i, (Ci , Ci−1 ]) + 5`k



i=1

LALG(s) (i, (0, Ci ]) + `k



i=1

≤ (R − 1)LALG(s) + LALG(s) + 6k`k = R · LALG(s) + 6k`k .
The theorem follows.

4.2

Analysis of MAIN

The first part of the following lemma implies the condition (4.2) for the initial i-segments in all cases.
The second part of the lemma is the base of the analysis of a proper i-segment, which is different in each
situation.
Lemma 4.3. (i) If (u, v] is an initial i-segment then LMAIN (s) (≥ i, (u, v]) > s(v − u) − 4`k .
(ii) If (u, v] is a proper i-segment and s(v − u) ≥ `i then LMAIN (s) ((u, v]) > s(v − u)/2 and LMAIN (s) (≥
i, (u, v]) > s(v − u)/2 − `i − `i−1 . (Recall that `0 = 0.)
Proof. (i) Let (u, v] be an initial i-segment. If the phase that starts at u or contains u ends before v, let
u0 be its end; otherwise let u0 = u. We have u0 ≤ u + `i /s, as otherwise any packet of size `i , pending
throughout the i-segment by definition, would be an eligible choice in Step (3) of the algorithm, and the
phase would not end before v. Using Lemma 2.2(ii), we have LMAIN (s) (< i, (u0 , v]) < `i + `i−1 < 2`k .
9

Since at most one packet at the end of the segment is unfinished, we have LMAIN (s) (≥ i, (u, v]) ≥
LMAIN (s) (≥ i, (u0 , v]) > s(v − u0 ) − 3`k > s(v − u) − 4`k .
(ii) Let (u, v] be a proper i-segment. Thus u is a start of a phase that contains at least the whole
interval (u, v] by Lemma 2.2(ii). By the definition of Ci , u is not i-good, so the phase starts by a packet of
size at most `i . If v −u ≥ `i then the first packet finishes (as s ≥ 1) and thus LMAIN (s) ((u, v]) > s(v −u)/2
by Lemma 2.1. The total size of completed packets smaller than `i is at most `i + `i−1 by Lemma 2.2(ii),
and thus LMAIN (s) (≥ i, (u, v]) > s(v − u)/2 − `i − `i−1 .
The next theorem gives a tradeoff of the competitive ratio of MAIN (s) and the speedup s using
our local analysis. While Theorem 5.1 shows that MAIN (s) is 1-competitive for s ≥ 4, here we give a
weaker result that reflects the limits of the local analysis. However, for s = 1 our local analysis is tight as
already the lower bound from [1] shows that no algorithm is better than 3-competitive (for packet sizes 1
and 2 − ε). See Figure 1 for an illustration of our upper and lower bounds on the competitive ratio of
MAIN (s).
Theorem 4.4. MAIN (s) is Rs -competitive where:
Rs = 1 + 2/s for s ∈ [1, 4),
Rs = 2/3 + 2/s for s ∈ [4, 6), and
Rs = 1 for s ≥ 6.
Proof. Lemma 4.3(i) implies the condition (4.2) for the initial i-segments. We now prove (4.1) for any
proper i-segment (u, v] with v − u ≥ `i and appropriate R. The bound then follows by the Master
Theorem.
Since there is a fault at time u, we have LOPT (≥ i, (u, v]) ≤ v − u.
For s ≥ 6, Lemma 4.3(ii) implies
LMAIN (s) (≥ i, (u, v]) > s(v − u)/2 − 2`i
≥ 3(v − u) − 2(v − u) = v − u ≥ LOPT (≥ i, (u, v]) ,
which is (4.1) for R = 1.
For s ∈ [4, 6), by Lemma 4.3(ii) we have LMAIN (s) ((u, v]) > s(v − u)/2 and by multiplying it by
(2/s − 1/3) we obtain



2 1
s
−
(v − u) .
· LMAIN (s) ((u, v]) > 1 −
s 3
6
Thus to prove (4.1) for R = 2/3 + 2/s, it suffices to show that
LMAIN (s) (≥ i, (u, v]) >

s
(v − u) ,
6

as clearly v − u ≥ LOPT (≥ i, (u, v]). The remaining inequality again follows from Lemma 4.3(ii), but we
need to consider two cases:
If (v − u) ≥ 6s `i , then
LMAIN (s) (≥ i, (u, v]) >

s
s
s
s
(v − u) − 2`i ≥ (v − u) − (v − u) = (v − u) .
2
2
3
6

On the other hand, if (v − u) < 6s `i , then using s ≥ 4 as well,
LMAIN (s) (≥ i, (u, v]) >

s
(v − u) − 2`i ≥ 0 ,
2

therefore MAIN (s) completes a packet of size at least `i which implies
LMAIN (s) (≥ i, (u, v]) ≥ `i >

s
(v − u) .
6

For s ∈ [1, 4), by Lemma 4.3(ii) we get (2/s) · LMAIN (s) ((u, v]) > v − u ≥ LOPT (≥ i, (u, v]), where
the last inequality holds as there is a fault at time u. This implies (4.1) for R = 1 + 2/s.

10

5

(4α + 2)/α2
2 + 2/α
3 + 1/α for α < α1
Upper bound from Theorem 4.6
Speedup sufficient for 1-competitiveness

Speedup

4

3

2

1
1

α0

α1

2
α

3

Figure 3: A graph of Sα and the bounds on the speedup that we use in Theorem 4.6.
We can obtain better bounds on the speedup necessary for 1-competitiveness if the packet sizes
are sufficiently different. Namely, we call the packet sizes `1 , . . . , `k α-separated if `i ≥ α`i−1 holds for
i = 2, . . . , k. We start by analyzing MAIN (s) for the case of divisible packet sizes, which is a special case
of 2-separated packet sizes. Note that by examples in Section 3 the bound of 2.5 cannot be improved for
our algorithm.
Theorem 4.5. If the packet sizes are divisible, then MAIN (s) is 1-competitive for s ≥ 2.5.
Proof. Lemma 4.3(i) implies (4.2). We now prove (4.1) for any proper i-segment (u, v] with v − u ≥ `i
and R = 1. The bound then follows by the Master Theorem. Since there is a fault at time u, we have
LOPT (≥ i, (u, v]) ≤ v − u.
By divisibility we have LOPT (≥ i, (u, v]) = n`i for some nonnegative integer n. We distinguish two
cases based on the size of the last packet started by MAIN in the i-segment (u, v], which is possibly
unfinished due to a fault at v.
If the unfinished packet has size at most n`i , then LMAIN (s) (≥ i, (u, v]) > 5(v − u)/2 − 3`i /2 −
n`i ≥ 5n`i /2 − 3`i /2 − n`i ≥ (n − 1)`i by Lemma 2.1 and Lemma 2.2(ii). Divisibility now implies
LMAIN (s) (≥ i, (u, v]) ≥ n`i = LOPT (≥ i, (u, v]).
Otherwise by divisibility the size of the unfinished packet is at least (n + 1)`i and the size of the
completed packets is larger by the condition in Step (3) of the algorithm; here we also use the fact that
MAIN (s) completes the packet started at u, as its size is at most `i ≤ v − u. Thus LMAIN (s) (≥ i, (u, v]) >
(n + 1)`i − 3`i /2 ≥ (n − 1/2)`i . Divisibility again implies LMAIN (s) (≥ i, (u, v]) ≥ n`i = LOPT (≥ i, (u, v]).
The theorem now follows by the Master Theorem.
Next, we show that for α-separated packet sizes, MAIN (Sα ) is 1-competitive for the following Sα .
We define
1 1√
α0 = +
33 ≈ 1.46 , which is the positive root of 3α2 − 3α − 2.
2 6
√
3 + 17
≈ 1.78 , which is the positive root of 2α2 − 3α − 1.
α1 =
4

4α + 2


for α ∈ [1, α0 ],

 α2
Sα = 3 + 1
for α ∈ [α0 , α1 ), and
α




2
2+ α
for α ≥ α1 .
11

See Figure 3 for a graph of Sα and all the bounds on it that we use. The value of α0 is chosen as the point
where (4α + 2)/α2 = 2 + 2/α. The value of α1 is chosen as the point from which the argument in case
(viii) of the proof below works, which allows for a better result for α ≥ α1 . If s ≥ Sα then s ≥ (4α + 2)/α2
and s ≥ 2 + 2/α for all α and also s ≥ 3 + 1/α for α < α1 ; these facts follow from inspection of the
functions and are useful for the analysis.
Note that Sα is decreasing in α, with a single discontinuity at α1 . We have S1 = 6, matching the
upper bound for 1-competitiveness using local analysis. We have S2 = 3, i.e., MAIN (3) is 1-competitive
for 2-separated packet sizes, which includes
√ the case of divisible packet sizes studied above. The limit
of Sα for α → +∞ is 2. For α < (1 + 3)/2 ≈ 1.366, we get Sα > 4, while Theorem 5.1 shows that
MAIN (s) is 1-competitive for s ≥ 4; the weaker result of Theorem 4.6 below reflect the limits of the local
analysis.
Theorem 4.6. Let α > 1. If the packet sizes are α-separated, then MAIN (s) is 1-competitive for any
s ≥ Sα .
Proof. Lemma 4.3(i) implies (4.2). We now prove for any proper i-segment (u, v] with v − u ≥ `i that
LMAIN (s) (≥ i, (u, v]) ≥ LOPT (≥ i, (u, v]) ,

(4.4)

which is (4.1) for R = 1. The bound then follows by the Master Theorem.
Let X = LOPT (≥ i, (u, v]). Note that X ≤ v − u.
Lemma 4.3(ii) together with `i−1 ≤ `i /α gives LMAIN (s) (≥ i, (u, v]) > M for M = sX/2 − (1 + 1/α)`i .
As in the case of divisible packet sizes, we use the fact that both X and LMAIN (s) (≥ i, (u, v]) are sums
of some packet sizes `j , j ≥ i, and thus only some of the values are possible. Here the situation is more
complicated, as for example `i+1 , `i+2 , 2`i , `i + `i+1 are possible values, but their ordering may vary.
We distinguish several cases based on X and α. We note in advance that the first five cases suffice for
α < α1 ; only after completing the proof for α < α1 , we analyze the additional cases needed for α ≥ α1 .
Case (i): X = 0. Then (4.4) is trivial.
Case (ii): X = `i . Using s ≥ 2 + 2/α, we obtain M ≥ 0. Thus LMAIN (s) (≥ i, (u, v]) > M ≥ 0 which
implies LMAIN (s) (≥ i, (u, v]) ≥ `i = X and (4.4) holds.
Case (iii): X = `i+1 ≤ 2`i . Using s ≥ (4α + 2)/α2 and X = `i+1 ≥ α`i , we obtain M ≥ (2 +
1/α)`i − (1 + 1/α)`i = `i . Thus LMAIN (s) (≥ i, (u, v]) > `i which together with `i+1 ≤ 2`i implies
LMAIN (s) (≥ i, (u, v]) ≥ `i+1 = X and (4.4) holds.
Case (iv): X ≥ α2 `i . (Note that this includes all cases when a packet of size at least `i+2 contributes to
X.) We first show that s ≥ 2(1 + 1/α2 + 1/α3 ) by straightforward calculations with the golden ratio φ: If
α ≤ φ, we have 1/α + 1/α2 − 1 ≥ 0 and thus s ≥ (4α + 2)/α2 = 2(2/α + 1/α2 ) ≥ 2(1 + 1/α2 + 1/α3 ), as
2/α ≥ 1 + 1/α3 is equivalent to (α − 1)(α2 − α − 1) ≤ 0, which holds for α ∈ (1, φ). If on the other hand
α ≥ φ, then s ≥ 2(1 + 1/α) ≥ 2(1 + 1/α2 + 1/α3 ), as 1/α ≥ 1/α2 + 1/α3 holds for α ≥ φ. Now we obtain






s

1
1
1
1
M −X ≥
−1 X − 1+
`i ≥ 1 + 2 + 3 − 1 X − 1 +
`i
2
α
α
α
α




1
1
1
+ 3 α2 `i − 1 +
`i = 0 ,
≥
2
α
α
α
and (4.4) holds.
Case (v): X ≥ 2`i and α < α1 . (Note that, as long as α < α1 , this includes all cases when at least two
packets contribute to X.) Using s ≥ 3 + 1/α we obtain
 








1
1
1
1
1
1
M −X ≥
3+
−1 X − 1+
`i ≥
1+
2`i − 1 +
`i = 0 ,
2
α
α
2
α
α
and (4.4) holds.
Proof for α < α1 : We now observe that for α < α1 , we have exhausted all the possible values of X.
Indeed, if (v) does not apply, then at most a single packet contributes to X, and one of the cases (i)-(iv)
applies, as (iv) covers the case when X ≥ `i+2 . Thus (4.4) holds and the proof is complete.
Proof for α ≥ α1 : We now analyze the remaining cases for α ≥ α1 .
12

Case (vi): X ≥ (α + 1)`i . (Note that this includes all cases when two packets not both of size `i
contribute to X.) Using s ≥ 2 + 2/α we obtain






1
1
1
1
`i ≥ (α + 1)`i − 1 +
`i = 0
M −X ≥ 1+ −1 X − 1+
α
α
α
α
and (4.4) holds.
Case (vii): X = n · `i < (α + 1)`i for some n = 2, 3, . . .. Since α > α1 > φ, we have `i+1 > `i + `i−1 .
This implies that the first packet of size at least `i that is scheduled in the phase has size equal to `i by
the condition in Step (3) of the algorithm. Thus, if also a packet of size larger than `i contributes to
LMAIN (s) (≥ i, (u, v]), we have
LMAIN (s) (≥ i, (u, v]) ≥ `i+1 + `i ≥ (α + 1)`i > X
by the case condition and (4.4) holds. Otherwise LMAIN (s) (≥ i, (u, v]) is a multiple of `i . Using
s ≥ 2 + 2/α, we obtain M ≥ (n − 1)(1 + 1/α)`i > (n − 1)`i . This, together with divisibility by `i implies
LMAIN (s) (≥ i, (u, v]) ≥ n · `i = X and (4.4) holds again.
Case (viii): X = `i+1 > 2`i . We distinguish two subcases depending on the size of the unfinished packet
of MAIN (s) in this phase.
If the unfinished packet has size at most `i+1 , the size of the completed packets is bounded by


2
LMAIN (s) ((u, v]) > sX − `i+1 = (s − 1)`i+1 ≥ 1 +
`i+1 ,
α
using s ≥ 2 + 2/α. Since the total size of packets smaller than `i is less then (1 + 1/α)`i by Lemma 2.2(ii),
we obtain


2`i+1
1
LMAIN (s) (≥ i, (u, v]) − X >
− 1+
`i > 0 ,
α
α
as `i+1 /α ≥ `i . Thus (4.4) holds.
Otherwise the unfinished packet has size at least `i+2 and, by Step (3) of the algorithm, also
LMAIN (s) ((u, v]) > `i+2 . We have `i+2 ≥ α`i+1 and by the case condition `i+1 > 2`i we obtain




1
1
`i > 2(α − 1)`i − 1 +
`i ≥ 0 ,
LMAIN (s) (≥ i, (u, v]) − X > (α − 1)`i+1 − 1 +
α
α
as the definition of α1 implies that 2(α − 1) ≥ 1 + 1/α for α ≥ α1 . Thus (4.4) holds.
We now observe that we have exhausted all the possible values of X for α ≥ α1 . Indeed, if at least
two packets contribute to X, either (vi) or (vii) applies. Otherwise, at most a single packet contributes
to X, and one of the cases (i)-(iv) or (viii) applies, as (iv) covers the case when X ≥ `i+2 . Thus (4.4)
holds and the proof is complete.

5

MAIN with speed 4

In this section we prove that speed 4 is sufficient for MAIN to be 1-competitive. Examples in Section 3
show that speed 4 is also necessary for our algorithm.
Theorem 5.1. MAIN (s) is 1-competitive for s ≥ 4.
Intuition. For s ≥ 4 we have that if at the start of a phase MAIN (s) has a packet of size `i pending
and the phase has length at least `i , then MAIN (s) completes a packet of size at least `i . To show this,
assume that the phase starts at time t. Then the first packet p of size at least `i is started before time
t + 2`i /s by Lemma 2.2(ii) and by the condition in Step (3) it has size smaller than 2`i . Thus it completes
before time t + 4`i /s ≤ t + `i , which is before the end of the phase. This property does not hold for s < 4.
It is important in our proof, as it shows that if the optimal schedule completes a job of some size, and
such job is pending for MAIN (s), then MAIN (s) completes a job of the same size or larger. However,

13

this is not sufficient to complete the proof by a local (phase-by-phase) analysis similar to the previous
section, as the next example shows.
Assume that at the beginning, we release N packets of size 1, N packets of size 1.5 − 2ε, one packet
of size 3 − 2ε and a sufficient number of packets of size 1 − ε, for a small ε > 0. Our focus is on packets
of size at least 1. Supposing s = 4 we have the following phases:
• First, there are N phases of length 1. In each phase the optimum completes a packet of size 1,
while among packets of size at least 1, MAIN (s) completes a packet of size 1.5 − 2ε, as it starts
packets of sizes 1 − ε, 1 − ε, 1.5 − 2ε, 3 − 2ε, in this order, and the last packet is jammed.
• Then there are N phases of length 1.5 − 2ε where the optimum completes a packet of size 1.5 − 2ε
while among packets of size at least 1, the algorithm completes only a single packet of size 1, as it
starts packets of sizes 1 − ε, 1 − ε, 1, 3 − 2ε, in this order. The last packet is jammed, since for
s = 4 the phase must have length at least 1.5 − ε to complete it.
In phases of the second type, the algorithm does not complete more (in terms of total size) packets of size
at least 1 than the optimum. Nevertheless, in our example, packets of size 1.5 − 2ε were already finished
by the algorithm, and this is a general rule. The novelty in our proof is a complex charging argument
that exploits such subtle interaction between phases.
Outline of the proof. We define critical times Ci0 similarly as before, but without the condition that
0
they should be ordered, i.e., Ci0 is simply the supremum of i-good times; consequently, either Ci0 ≤ Ci−1
0
0
or Ci > Ci−1 may hold. Our plan is to define, for each i, charges between packets of size `i up to time
Ci0 , since nearly each packet of size `i completed by the adversary before Ci0 must be completed by the
algorithm before Ci0 . Each such charge from an adversary’s packet leads to an algorithm’s packet of the
same size and each algorithm’s packet receives at most one such charge; we thus call these charges 1-to-1
charges.
We want to charge the remaining adversary’s packets of size `i (scheduled after Ci0 ) to some algorithm’s
packets in the same phase. For technical reasons it is actually more convenient to partition the schedule
not into phases but into blocks inbetween successive faults. A block can contain several phases of the
algorithm separated by an execution of Step (4); however, in the most important and tight part of the
analysis the blocks coincide with phases.
After the critical time Ci0 , packets of size `i are always pending for the algorithm, and thus (as we
observed above) the algorithm schedules a packet of size at least `i in blocks in which the adversary
completes a packet of size `i . In the crucial lemma of the proof, based on these observations and their
refinements, we show that we can assign the remaining adversary’s packets (i.e., those without 1-to-1
charges) to algorithm’s packets in the same block so that for each algorithm’s packet q the total size of
packets assigned to it is at most `(q). However, we cannot use this assignment directly to charge the
remaining packets, as some of the algorithm’s big packets may receive 1-to-1 charges, and in this case
the analysis needs to handle the interaction of different blocks. This very issue can be seen even in our
introductory example.
To deal with this, we process blocks in the order of time from the beginning to the end of the schedule,
simultaneously completing the charging to the packets in the current block of MAIN (s) schedule and
possibly modifying ADV (the schedule of the adversary) in the future blocks. In fact, in the assignment
described above, we include not only the packets in ADV without 1-to-1 charge but also packets in ADV
with a 1-to-1 charge to a later block. After creating the assignment, if we have a packet q in ALG that
receives a 1-to-1 charge from a packet p in a later block of ADV , we remove p from ADV in that later
block and replace it there by the packets assigned to q (that are guaranteed to be of smaller total size
than p). After these swaps, the 1-to-1 charges together with the assignment form a valid charging that
charges the remaining not swapped packets in ADV in this block together with the removed packets
from the later blocks in ADV to the packets of MAIN (s) in the current block. This charging is now
independent of the other blocks, so we can continue with the next block.
Furthermore, to analyze blocks in which the algorithm does not complete any packet, we shift the
targets of the 1-to-1 charges backward in time by accounting for the first few packets of each size completed
by the adversary at the beginning of the schedule and after Ci0 in the additive constant of the competitive
ratio.
Preliminaries.

We define the notions of blocks and (modified) critical times.

14

Ci0

ALG:

...

ADV:

Figure 4: An illustration of back, up, and forward 1-to-1 charges for size `i . Crossed packets are included
in the set A (and thus contribute to the additive constant).
Definition 3. Let f1 , f2 , . . . , fN be the times of faults. Let f0 = 0 and fN +1 = T is the end of schedule.
Then the time interval (fi , fi+1 ], i = 0, . . . , N , is called a block.
Definition 4. For i = 1, . . . k, the critical time Ci0 is the supremum of i-good times t ∈ [0, T ], where T is
the end of the schedule and i-good times are as defined in Definition 1.
All Ci0 ’s are defined, as t = 0 is i-good for all i. Similarly to Section 4.1, each Ci0 is of one of the
following types: (i) Ci0 starts a phase and a packet larger than `i is started, (ii) Ci0 = 0, (iii) Ci0 = T , or
(iv) just before time Ci0 no packet of size `i is pending but at time Ci0 one or more packets of size `i are
pending; in this case Ci0 is not i-good but only the supremum of i-good times. We observe that in each
case, at time Ci0 the total size of packets p of size `i pending for MAIN (s) and released before Ci0 is less
than `k .
1-to-1 charges and the additive constant. Next we define the set of packets that contribute to the
additive constant.
Definition 5. Let the set A contain for each i = 1, . . . , k:
(i) the first d4`k /`i e packets of size `i completed by the adversary, and
(ii) the first d4`k /`i e packets of size `i completed by the adversary after Ci0 .
If there are not sufficiently many packets of size `i completed by the adversary in (i) or (ii), we take all
the packets in (i) or all the packets completed after Ci0 in (ii), respectively.
For each i, we put into A packets of size `i of total size at most 10`k . Thus we have `(A) = O(k`k )
which implies that packets in A can be counted in the additive constant.
We define 1-to-1 charges for packets of size `i as follows. Let p1 , p2 , . . . , pn be all the packets of size
`i started by the adversary before Ci0 that are not in A. We claim that MAIN (s) completes at least n
packets of size `i before Ci0 . Indeed, before time Ci0 at least n + d4`k /`i e packets of size `i are started by
the adversary and thus released; by the definition of Ci0 at time Ci0 fewer than `k /`i of them are pending
for MAIN (s), one may be running and the remaining ones must be completed. We now charge each pm
to the mth packet of size `i completed by MAIN (s).
We call a 1-to-1 charge starting and ending in the same block an up charge, a 1-to-1 charge from a
block starting at u to a block ending at v 0 ≤ u a back charge, and a 1-to-1 charge from a block ending at
v to a block starting at u0 ≥ v a forward charge. A charged packet is a packet charged by a 1-to-1 charge.
The definition of A implies the following two important properties. See Figure 4 for an illustration.
Lemma 5.2. Let p be a packet of size `i , started by the adversary at time t, charged by a forward charge
to a packet q started by MAIN (s) at time t0 . Then at any time τ ∈ [t − 3`k , t0 ), more than `k /`i packets
of size `i are pending for MAIN (s).
Proof. Let m be the number of packets of size `i that MAIN (s) completes before q. Then, by the
definition of A, the adversary completes m + d4`k /`i e packets of size `i before p. As fewer than 3`k /`i of
these packets are started in (t − 3`k , t], the remaining more than m + `k /`i packets have been released
before or at time t − 3`k . As only m of them are completed by MAIN (s) before t0 , the remaining more
than `k /`i packets are pending at any time τ ∈ [t − 3`k , t0 ).
Lemma 5.3. Let p 6∈ A be a packet of size `i started by the adversary at time t that is not charged. Then
t − 4`k ≥ Ci0 and thus at any τ ≥ t − 4`k , a packet of size `i is pending for MAIN (s).
Proof. Any packet of size `i started before Ci0 + 4`k is either charged or put in A, thus t − 4`k ≥ Ci0 . After
Ci0 , a packet of size `i is pending by the definition of Ci0 .
15

Processing blocks. Initially, let ADV be an optimal (adversary) schedule. First we remove all packets
in A from ADV . Then we process blocks one by one in the order of time. When we process a block, we
modify ADV so that we (i) remove some packets from ADV , so that the total size of removed packets is
at most the total size of packets completed by MAIN (s) in this block, and (ii) reschedule any remaining
packet in ADV in this block to one of the later blocks, so that the schedule of remaining packets remains
feasible. Summing over all intervals, (i) guarantees that MAIN (s) is 1-competitive with an additive
constant `(A).
When we reschedule a packet in ADV , we keep the packet’s 1-to-1 charge (if it has one), however, its
type may change due to rescheduling. Since we are moving packets only to later times only, the release
times are automatically respected. Also it follows that we can apply Lemmata 5.2 and 5.3 even to ADV
after rescheduling.
After processing of a block, there will remain no charges to or from it. For the charges from the
block this is automatic, as there remain no packets to be charged. For the charges to the block, this is
guaranteed as in the process we remove from ADV all the packets in later blocks charged by back charges
to the current block.
From now on, let (u, v] be the current block that we are processing; all previous blocks ending at
v 0 ≤ u are processed. As there are no charges to the previous blocks, any packet scheduled in ADV in
(u, v] is charged by an up charge or a forward charge, or else it is not charged at all. We distinguish two
main cases of the proof, depending on whether MAIN (s) finishes any packet in the current block.
Main case 1: Empty block. The algorithm does not finish any packet in (u, v]. We claim that ADV
does not finish any packet. The processing of the block is then trivial.
For a contradiction, assume that ADV starts a packet p of size `i at time t and completes it. The
packet p cannot be charged by an up charge, as MAIN (s) completes no packet in this block. Thus p is
either charged by a forward charge or not charged. Lemma 5.2 or 5.3 implies that at time t some packet
of size `i is pending for MAIN (s).
Since MAIN does not idle unnecessarily, this means that some packet q of size `j for some j is started
in MAIN (s) at time τ ≤ t and running at t. As MAIN (s) does not complete any packet in (u, v], the
packet q is jammed by the fault at time v. This implies that j > i, as `j > s(v − τ ) ≥ v − t ≥ `i ; we also
have t − τ < `j . Moreover, q is the only packet started by MAIN (s) in this block, thus it starts a phase.
As this phase is started by packet q of size `j > `i , the time τ is i-good and Ci0 ≥ τ . All packets ADV
started before time Ci0 + 4`k /s are charged, as the packets in A are removed from ADV and packets in
ADV are rescheduled only to later times. Packet p is started before v < τ + `j /s < Ci0 + `k /s, thus it is
charged. It follows that p is charged by a forward charge. We now apply Lemma 5.2 again and observe
that it implies that at τ > t − `j there are more than `k /`i packets of size `i pending for MAIN (s). This
is in contradiction with the fact that at τ , MAIN (s) started a phase by q of size `j > `i .
Main case 2: Non-empty block. Otherwise, MAIN (s) completes a packet in the current block (u, v].
Let Q be the set of packets completed by MAIN (s) in (u, v] that do not receive an up charge. Note
that no packet in Q receives a forward charge, as the modified ADV contains no packets before u, so
packets in Q either get a back charge or no charge at all. Let P be the set of packets completed in ADV
in (u, v] that are not charged by an up charge. Note that P includes packets charged by a forward charge
and uncharged packets, as no packets are charged to a previous block.
We first assign packets in P to packets in Q so that for each packet q ∈ Q the total size of packets
assigned to q is at most `(q). Formally, we iteratively define a provisional assignment f : P → Q such
that `(f −1 (q)) ≤ `(q) for each q ∈ Q.
Provisional assignment. We maintain a set O ⊆ Q of occupied packets that we do not use for a
future assignment. Whenever we assign a packet p to q ∈ Q and `(q) − `(f −1 (q)) < `(p), we add q to O.
This rule guarantees that each packet q ∈ O has `(f −1 (q)) > `(q)/2.
We process packets in P in the order of decreasing sizes as follows. We take the largest unassigned
packet p ∈ P of size `(p) (if there are more unassigned packets of size `(p), we take an arbitrary one)
and choose an arbitrary packet q ∈ Q \ O such that `(q) ≥ `(p); we prove in Lemma 5.4 below that
such a q exists. We assign p to q, that is, we set f (p) = q. Furthermore, as described above, if
`(q) − `(f −1 (q)) < `(p), we add q to O. We continue until all packets are assigned.

16

If a packet p is assigned to q and q is not put in O, it follows that `(q) − `(f −1 (q)) ≥ `(p). This implies
that after the next packet p0 is assigned to q, we have `(q) ≥ `(f −1 (q)), as the packets are processed from
the largest one and thus `(p0 ) ≤ `(p). If follows that at the end we obtain a valid provisional assignment.
Lemma 5.4. The assignment process above assigns all packets in P .
Proof. For each size `j we show that all packets of size `j in P are assigned, which is clearly sufficient.
We fix the size `j and define a few quantities.
Let n denote
P the number of packets of size `j in P . Let o denote the total occupied size, defined as
o = `(O) + q∈Q\O `(f −1 (q)) at the time just before we start assigning the packets of size `j . Note that
the rule for adding P
packets to O implies that `(f −1 (Q)) ≥ o/2. Let a denote the current total available
size defined as a = q∈Q\O:`(q)≥`j (`(q) − `(f −1 (q))).
First we claim that it is sufficient to show that a > (2n − 2)`j before we start assigning the packets of
size `j . As long as a > 0, there is a packet q ∈ Q \ O of size at least `j and thus we may assign the next
packet (and, as noted before, actually a ≥ `j , as otherwise q ∈ O). Furthermore, assigning a packet p of
size `j to q decreases a by `j if q is not added to O and by less than 2`j if q is added to O. Altogether,
after assigning the first n − 1 packets, a decreases by less than (2n − 2)`j , thus we still have a > 0, and
we can assign the last packet. The claim follows.
We now split the analysis into two cases, in each we prove that the available space a is sufficiently
large before assigning the packets of size `j .
In the first case, we suppose that a packet of size `j is pending for MAIN (s) at all times in [u, v). Let
z be the total size of packets of size at least `j charged by up charges in this block. The size of packets in
P already assigned is at least `(f −1 (Q)) ≥ o/2 and we have n yet unassigned packets of size `j in P . As
ADV has to schedule all these packets and the packets with up charges in this block, its size satisfies
v − u ≥ `(P ) + z ≥ n`j + o/2 + z. Now consider the schedule of MAIN (s) in this block. By Lemma 2.2,
there is no end of phase in (u, v) and jobs smaller than `j scheduled by MAIN (s) have total size less
than 2`j . All the other completed packets contribute to one of a, o, or z. Using Lemma 2.1, the previous
bound on v − u and s ≥ 4, the total size of completed packets is at least s(v − u)/2 ≥ 2n`j + o + 2z.
Hence a > (2n`j + o + 2z) − 2`j − o − z ≥ (2n − 2)`j , which completes the proof of the lemma in this case.
Otherwise, in the second case, there is a time in [u, v) when no packet of size `j is pending for
MAIN (s). Let τ be the supremum of times τ 0 ∈ [u, v] such that MAIN (s) has no pending packet of size
at least `j at time τ 0 ; if no such τ 0 exists we set τ = u. Let t be the time when the adversary starts the
first packet p of size `j from P .
Since p is charged using a forward charge or p is not charged, we can apply Lemma 5.2 or 5.3, which
implies that packets of size `j are pending for MAIN (s) from time t − 3`k till at least v. By the case
condition, there is a time in [u, v) when no packet of size `j is pending, and this time is thus before
t − 3`k , implying u < t − 3`k . The definition of τ now implies that τ ≤ t − 3`k .
Towards bounding a, we show that (i) MAIN (s) runs a limited amount of small packets after τ and
thus a + o is large, and that (ii) f −1 (Q) contains only packets run by ADV from τ on, and thus o is small.
We claim that the total size of packets smaller than `j completed in MAIN (s) in (τ, v] is less than 3`k .
This claim is similar to Lemma 2.2 and we also argue similarly. Let τ1 < τ2 < . . . < τα be all the ends
of phases in (τ, v) (possibly there is none, then α = 0); also let τ0 = τ . For i = 1, . . . , α, let ri denote
the packet started by MAIN (s) at τi ; note that ri exists since after τ there is a pending packet at any
time in [τ, v] by the definition of τ . First note that any packet started at or after time τα + `k /s has size
at least `j , as such a packet is pending and satisfies the condition in Step (3) of the algorithm. Thus
the total amount of the small packets completed in (τα , v]) is less than `k + `k−1 < 2`k . The claim now
follows for α = 0. Otherwise, as there is no fault in (u, v), at τi , i = 1, . . . , α, Step (4) of the algorithm
is reached and thus no packet of size at most s(τi − τi−1 ) is pending. In particular, this implies that
`(ri ) > s(τi − τi−1 ) for i = 1, . . . , α. This also implies that the amount of the small packets completed
in (τ0 , τ1 ] is less than `k and the claim for α = 1 follows. For α ≥ 2 first note that by Lemma 2.2(i),
s(τi − τi−1 ) ≥ `j for all i = 2, . . . , α and thus ri is not a small packet. Thus for i = 3, . . . , α, the amount
of small packets in (τi−1 , τi ] is at most s(τi−1 − τi ) − `(ri−1 ) < `(ri ) − `(ri−1 ). The amount of small
packets completed in (τ1 , τ2 ] is at most s(τ2 − τ1 ) < `(r2 ) and the amount of small packets completed in
(τα , v] is at most 2`k − `(rα ). Summing this together, the amount of small packets completed in (τ1 , v] is
at most 2`k and the claim follows.
Let z be the total size of packets of size at least `j charged by up charges in this block and completed
by MAIN (s) after τ . After τ , MAIN (s) processes packets of total size more than s(v − τ ) − `k and all of
17

`i

2`i

≥ `j

`j

`i

2`i

≥ `j

`j

ALG:
ADV:

`i

`i

`j

`j

Figure 5: An illustration of the provisional assignment on the left; note that a packet of size `j with a
forward charge is also assigned. Full arcs depict 1-to-1 charges and dashed arcs depict the provisional
assignment. The result of modifying the adversary schedule on the right.
these packets contribute to one of a, o, z, or the volume of less than 3`k of small packets from the claim
above. Thus, using s ≥ 4, we get
a > 4(v − τ ) − o − z − 4`k .
(5.1)
Now we derive two lower bounds on v − τ using ADV schedule.
Observe that no packet contributing to z except for possibly one (the one possibly started by MAIN (s)
before τ ) is started by ADV before τ , as otherwise it would be pending for MAIN (s) just before τ ,
contradicting the definition of τ .
Also, observe that in (u, τ ], ADV runs no packet p ∈ P with `(p) > `j : For a contradiction, assume
that such a p exists. As τ ≤ Cj 0 for any j 0 > j, such a p is charged. As p ∈ P , it is charged by a forward
charge. However, then Lemma 5.2 implies that at all times between the start of p in ADV and v a
packet of size `(p) is pending for MAIN (s); in particular such a packet is pending in the interval before
τ , contradicting the definition of τ .
These two observations imply that in [τ, v], ADV starts and completes all the assigned packets from
P , the n packets of size `j from P , and all packets except possibly one contributing to z. This gives
v − τ ≥ `(f −1 (Q)) + n`j + z − `k ≥ o/2 + n`j + z − `k .
To obtain the second bound, we observe that the n packets of size `j from P are scheduled in [t, v]
and together with t ≥ τ + 3`k we obtain v − τ = v − t + t − τ ≥ n`j + 3`k .
Summing the two bounds on v − τ and multiplying by two we get 4(v − τ ) ≥ 4n`j + 4`k + o + 2z.
Summing with (5.1) we get a > 4n`j + z ≥ 4n`j . This completes the proof of the second case.
As a remark, note that in the previous proof, the first case deals with blocks after Cj , it is the typical
and tight case. The second case deals mainly with the block containing Cj . (The blocks that are before
Cj may fall in either of the cases.) This brings some technical difficulties, but it is a case which has slack.
This is similar to the situation in the local analysis using Master Theorem.
Modifying the adversary schedule. Now all the packets from P are provisionally assigned by f and
for each q ∈ Q we have that `(f −1 (q)) ≤ `(q).
We process all packets q completed by MAIN (s) in (u, v] one by one according to one of the following
three cases; in each case we remove from ADV one or more packets with total size at most `(q).
If q 6∈ Q then the definition of P and Q implies that q is charged by an up charge from some packet
p 6∈ P of the same size. We remove p from ADV .
If q ∈ Q does not receive a charge, we remove f −1 (q) from ADV . We have `(f −1 (q)) ≤ `(q), so the
size is as required. If any packet p ∈ f −1 (q) is charged (necessarily by a forward charge), we remove this
charge.
If q ∈ Q receives a charge, it is a back charge from some packet p of the same size. We remove p from
ADV and in the interval where p was scheduled, we schedule packets from f −1 (q) in an arbitrary order.
As `(f −1 (q)) ≤ `(q), this is feasible. If any packet p ∈ f −1 (q) is charged, we keep its charge to the same
packet in MAIN (s); the charge was necessarily a forward charge, so it leads to some later block. See
Figure 5 for an illustration.
After we have processed all the packets q, we have modified ADV by removing an allowed total size of
packets and rescheduling the remaining packets in (u, v] so that any remaining charges go to later blocks.
This completes processing of the block (u, v] and thus also the proof of 1-competitiveness.

18

τ ≥ t + `/s − 2

t
ALG:
ADV:

`
`

Figure 6: An illustration of Case (D3).

6

Lower Bounds

In this section we study lower bounds on the speed necessary to achieve 1-competitiveness. We start with
a lower bound of 2 which holds even for the divisible case. It follows that our algorithm DIV and the
algorithm in Jurdzinski et al. [7] are optimal. Note that this lower bound follows from results of Anta et
al. [3] by a similar construction, although the packets in their construction are not released together.
Theorem 6.1. There is no 1-competitive deterministic online algorithm running with speed s < 2, even
if packets have sizes only 1 and ` for ` > 2s/(2 − s) and all of them are released at time 0.
Proof. For a contradiction, consider an algorithm ALG running with speed s < 2 that is claimed to be
1-competitive with additive constant A where A may depend on `. At time 0 the adversary releases
N1 = dA/`e + 1 packets of size ` and N0 = d(2/s) · N1 · (s − 1) · `2 + (2/s) · ` · (A + 1)e packets of size 1.
These are all packets in the instance.
The adversary’s strategy works by blocks where a block is a time interval between two faults, where
the first block begins at time 0. The adversary ensures that in each such block ALG completes no packet
of size ` and moreover ADV either completes an `-sized packet or completes more 1’s (packets of size 1)
than ALG.
Let t be the time of the last fault; initially t = 0. Let τ ≥ t be the time when ALG starts the
first `-sized packet after t; we set τ = ∞ if it does not happen. Note that we use here that ALG is
deterministic. In a block beginning at time t, the adversary proceeds according to the first case below
that applies.
(D1) If ADV has less than 2`/s pending packets of size 1, then the end of the schedule is at t.
(D2) If ADV has all packets of size ` completed, then it stops the current process and issues a fault at
times t + 1, t + 2, . . . Between each two consecutive faults after t it completes one packet of size 1
and it continues issuing faults until it has no pending packet of size 1. Then there is the end of the
schedule. Clearly, ALG may complete only packets of size 1 after t as ` > 2s/(2 − s) > s.
(D3) If τ ≥ t + `/s − 2, then the next fault is at time t + `. In the current block, the adversary completes
a packet `. ALG completes at most s · ` packets of size 1 and then it possibly starts ` at τ (if
τ < t + `) which is jammed, since it would be completed at


2`
2
`
−2=t+`+
−1 `−2>t+`
τ + ≥t+
s
s
s

where the last inequality follows from 2s − 1 ` > 2 which is equivalent to ` > 2s/(2 − s). Thus the
`-sized packet would be completed after the fault. See Figure 6 for an illustration.
(D4) Otherwise, if τ < t + `/s − 2, then the next fault is at time τ + `/s − ε for a small enough ε > 0. In
the current block, ADV completes as many packets of size 1 as it can, that is bτ + `/s − ε − tc
packets of size 1; note that by Case (D1), ADV has enough 1’s pending. Again, the algorithm does
not complete the packet of size ` started at τ , because it would be finished at τ + `/s. See Figure 7
for an illustration.
First notice that the process above ends, since in each block the adversary completes a packet. We
now show LADV > LALG + A which contradicts the claimed 1-competitiveness of ALG.
19

t
ALG:
ADV:

τ < t + `/s − 2
`

Gain = 7
Gain = 8

Figure 7: An illustration of Case (D4).
If the adversary’s strategy ends in Case (D2), then ADV has all `’s completed and then it schedules
all 1’s, thus LADV = N1 · ` + N0 > A + N0 . However, ALG does not complete any `-sized packet and
hence LALG ≤ N0 which concludes this case.
Otherwise, the adversary’s strategy ends in Case (D1). We first claim that in a block (t, t0 ] created in
Case (D4), ADV finishes more 1’s than ALG. Indeed, let o be the number of 1’s completed by ALG in
(t, t0 ]. Then τ ≥ t + o/s where τ is from the adversary’s strategy in (t, t0 ], and we also have o < ` − 2s or
equivalently ` > o + 2s, because τ < t + `/s − 2 in Case (D4). The number of 1’s scheduled by ADV is

 
 
 

`
o `
o o + 2s
2
τ + −ε−t ≥ t+ + −ε−t ≥
+
−ε =
o+2−ε
s
s s
s
s
s


2
o+1 ≥o+1
≥
s
and we proved the claim.
Let α be the number of blocks created in Case (D3); note that α ≤ N1 , since in each such block
ADV finishes one `-sized packet. ALG completes at most s` packets of size 1 in such a block, thus
LADV ((u, v]) − LALG ((u, v]) ≥ (1 − s) · ` for a block (u, v] created in Case (D3).
Let β be the number of blocks created in Case (D4). We have


s
2`
s · N0
β>
· N0 −
=
− 1,
2`
s
2`
because in each such block ADV schedules less than 2`/s packets of size 1 and less than 2`/s of these
packets are pending at the end. By the claim above, we have LADV ((u, v]) − LALG ((u, v]) ≥ 1 for a block
(u, v] created in Case (D4).
Summing over all blocks and using the value of N0 we get
LADV − LALG ≥ α · (1 − s) · ` + β
s · N0
−1
2`
≥ N1 · (1 − s) · ` + N1 · (s − 1) · ` + A + 1 − 1 = A

> N1 · (1 − s) · ` +

where we used s ≥ 1 which we may suppose w.l.o.g. This concludes the proof.
Our main lower bound of φ + 1 = φ2 ≈ 2.618 generalizes the construction of Theorem 6.1 for more
packet sizes, which are no longer divisible. Still, we make no use of release times.
Theorem 6.2. There is no 1-competitive deterministic online algorithm running with speed s < φ + 1,
even if all packets are released at time 0.
Proof. The adversary chooses ε > 0 small enough and k ∈ N large enough so that s < φ + 1 − 1/φk−1 .
For convenience, the smallest size in the instance is ε instead of 1. There will be k + 1 packet sizes in the
instance, namely `0 = ε, and `i = φi−1 for i = 1, . . . , k.
Suppose for a contradiction that there is an algorithm ALG running with speed s < φ + 1 that is
claimed to be 1-competitive with additive constant A where A may depend on `i ’s, in particular on ε
and k. The adversary issues Ni packets of size `i at time 0, for i = 0, . . . , k; Ni ’s are chosen so that
N0  N1  · · ·  Nk . These are all packets in the instance.
20

ALG:
ADV:

ε 1

φ3

φ
φ2

Figure 8: An illustration of Case (B5).
Pk
More precisely, Ni ’s are defined inductively so that it holds Nk > A/`k , Ni > `k φs j=i+1 Nj + A/`i
Pk
for i = k − 1, . . . , 1, and finally N0 > φ`k (A + 1 + sφ`k i=1 Ni )/ε2 .
The adversary’s strategy works by blocks where a block is again a time interval between two faults
and the first block begins at time 0. Let t be the time of the last fault; initially t = 0. Let τi ≥ t be the
time when ALG starts the first packet of size `i after t; we set τi = ∞ if it does not happen. Again, we
use here that ALG is deterministic. Let τ≥i = minj≥i τj be the time when ALG starts the first packet of
size at least `i after t. Let PADV (i) be the total size of `i ’s (packets of size `i ) pending for the adversary
at time t.
In a block beginning at time t, the adversary proceeds according to the first case below that applies.
Each case has an intuitive explanation which we make precise later.
(B1) If there are less than φ`k /ε packets of size ε pending for ADV , then the end of the schedule is at
time t.
Lemma 6.3 below shows that in blocks in which ADV schedules ε’s it completes more than ALG in
terms of total size. It follows that the schedule of ADV has much bigger total size for N0 large
enough, since the adversary scheduled nearly all packets of size ε; see Lemma 6.8.
(B2) If there is i ≥ 1 such that PADV (i) = 0, then ADV stops the current process and continues by
Strategy Finish described below.
(B3) If τ1 < t + `1 /(φ · s), then the next fault occurs at time τ1 + `1 /s − ε, so that ALG does not finish
the first `1 -sized packet. ADV schedules as many ε’s as it can.
In this case, ALG schedules `1 too early and in Lemma 6.3 we show that the total size of packets
completed by ADV is larger than the total size of packets completed by ALG.
(B4) If τ≥2 < t + `2 /(φ · s), then the next fault is at time τ≥2 + `2 /s − ε, so that ALG does not finish
the first packet of size at least `2 . ADV again schedules as many ε’s as it can. Similarly as in the
previous case, ALG starts `2 or a larger packet too early and we show that ADV completes more
in terms of size than ALG, again using Lemma 6.3.
(B5) If there is 1 ≤ i < k such that τ≥i+1 < τi , then we choose the smallest such i and the next fault is
at time t + `i . ADV schedules a packet of size `i . See Figure 8 for an illustration.
Intuitively, this case means that ALG skips `i and schedules `i+1 (or a larger packet) earlier.
Lemma 6.5 shows that the algorithm cannot finish its first packet of size at least `i+1 (thus it also
does not schedule `i ) provided that this case is not triggered for a smaller i, or previous cases are
not triggered.
(B6) Otherwise, the next fault occurs at t + `k and ADV schedules a packet of size `k in this block.
Lemma 6.6 shows that ALG cannot complete an `k -sized packet in this block. See Figure 9 for an
illustration.
We remark that the process above eventually ends either in Case (B1), or in Case (B2), since in each
block ADV schedules a packet. Also note that the length of each block is at most φ`k .
We describe Strategy Finish, started in Case (B2). Let i be the smallest index i0 ≥ 1 such that
PADV (i0 ) = 0. For brevity, we call a packet of size at least `i long, and a packet of size `j with 1 ≤ j < i
short; note that ε’s are not short packets. In a nutshell, ADV tries to schedule all short packets, while
preventing the algorithm from completing any long packet. Similarly to Cases (B3) and (B4), if ALG is
starting a long packet too early, ADV schedules ε’s and gains in terms of total size.

21

ALG:
ADV:

ε 1

φ

φ2

φk

...
φk

Figure 9: An illustration of Case (B6).
Adversary’s Strategy Finish works again by blocks. Let t be the time of the last fault. Let τ ≥ t
be the time when ALG starts the first long packet after t; we set τ = ∞ if it does not happen. The
adversary proceeds according to the first case below that applies:
(F1) If PADV (0) < φ`k , then the end of the schedule is at time t.
(F2) If ADV has no pending short packet, then the strategy Finish ends and ADV issues a fault at times
t + ε, t + 2ε, . . . Between each two consecutive faults after t it completes one packet of size ε and it
continues issuing faults until it has no pending ε. Then there is the end of the schedule. Clearly,
ALG may complete only ε’s after t if ε is small enough. Note that for i = 1 this case is immediately
triggered, as `0 -sized packets are not short, hence there are no short packets whatsoever.
(F3) If τ < t + `i /(φ · s), then the next fault is at time τ + `i /s − ε, so that ALG does not finish the first
long packet. ADV schedules as many ε’s as it can. Note that the length of this block is less than
`i /(φ · s) + `i /s ≤ φ`k . Again, we show that ADV completes more in terms of size using Lemma 6.3.
(F4) Otherwise, τ ≥ t + `i /(φ · s). ADV issues the next fault at time t + `i−1 . Let j be the largest
j 0 < i such that PADV (j 0 ) > 0. ADV schedules a packet of size `j which is completed as j ≤ i − 1.
Lemma 6.7 shows that ALG does not complete the long packet started at τ .
Again, in each block ADV completes a packet, thus Strategy Finish eventually ends. Note that the
length of each block is less than φ`k .
We now prove the lemmata mentioned above. In the following, t is the beginning of the considered
block and t0 is the end of the block, i.e., the next fault after t. Recall that LALG ((t, t0 ]) is the total size
of packets completed by ALG in (t, t0 ]. We start with a general lemma that covers all cases in which
ADV schedules many ε’s.
Lemma 6.3. In Cases (B3), (B4), and (F3) it holds LADV ((t, t0 ]) ≥ LALG ((t, t0 ]) + ε.
Proof. Let i and τ be as in Case (F3); we set i = 1 and τ = τ1 in Case (B3), and i = 2 and τ = τ≥2 in
Case (B4). Note that the first packet of size (at least) `i is started at τ with τ < t + `i /(φ · s) and that
the next fault occurs at time τ + `i /s − ε. Furthermore, PADV (0, t) ≥ φ`k by Cases (B1) and (F1). As
t0 − t ≤ φ`k it follows that ADV has enough ε’s to fill nearly the whole block with them, so in particular
LADV ((t, t0 ]) > t0 − t − ε.
Let a = LALG ((t, t0 ]). Since ALG does not complete the `i -sized packet we have τ ≥ t + a/s and thus
also a < `i /φ as τ < t + `i /(φ · s).
If a < `i /φ − 3sε/φ which is equivalent to `i > φ · a + 3sε, then we show the required inequality by
the following calculation:
LADV ((t, t0 ]) + ε > t0 − t = τ +

`i
a `i
a + φ · a + 3sε
−ε−t≥ + −ε>
− ε > a + 2ε .
s
s
s
s

Otherwise, a is nearly `i /φ and thus large enough. Then we get
LADV ((t, t0 ]) + ε > t0 − t = τ +

`i
a `i
a φa
−ε−t≥ + −ε> +
− ε > a + 2ε
s
s
s
s
s

where the penultimate inequality follows by `i > φa, and the last inequality holds as (1 + φ)a/s > a + 3ε
for ε small enough and a ≥ `i /φ − 3sε/φ.
22

− 1 and Si = Si−1 + `i for i = 1, . . . , k. Thus Si =
Pi For brevity, we inductively define S0 = φ i+1
`
+
φ
−
1
and
a
calculation
shows
S
=
φ
− 1. We prove a useful observation.
i
i
j=1
Lemma 6.4. Fix j ≥ 2. If Case (B3) and Case (B5) for i < j are not triggered in the block, then
τi+1 ≥ t + Si /s for each i < j.
Proof. We have τ1 ≥ t + `1 /(φ · s) = t + (φ − 1)/s by Case (B3) and τi+1 ≥ τi + `i /s for any i < j, since
Case (B5) was not triggered for i < j and the first `i -sized packet needs to be finished before starting the
next packet. Summing the bounds gives the inequalities in the lemma.
Lemma 6.5. In Case (B5) the algorithm does not complete any packet of size `i or larger.
Proof. Recall that we have τ≥i+1 < τi , thus the first packet p of size at least `i has size at least `i+1 . It
suffices to prove
`i+1
τ≥i+1 +
− t > `i ,
(6.1)
s
which means that p would be completed after the next fault at time t + `i .
We start with the case i = 1 in which τ≥2 < τ1 . Since Case (B4) was not triggered, we have
τ≥2 ≥ t + `2 /(φ · s) = t + 1/s. We show (6.1) by the following calculation:
τ≥2 +

`2
1 `2
1+φ
−t≥ +
=
> 1 = `1 ,
s
s
s
s

where the strict inequality holds by s < φ + 1.
Now consider the case i ≥ 2. By the minimality of i satisfying the condition of Case (B5) we
use Lemma 6.4 for j = i to get τi−1 ≥ t + Si−2 /s. Since a packet `i−1 is started at τi−1 , it holds
τ≥i+1 ≥ t + (Si−2 + `i−1 )/s = t + Si−1 /s. Thus
τ≥i+1 +

`i+1
Si−1 + `i+1
φi − 1 + φi
−t≥
=
s
s
s
φi+1 + φi−2 − 1
φi+1
=
≥
≥ φi−1 = `i ,
s
s

where the penultimate inequality holds by i ≥ 2 and the last inequality by s < φ + 1. (We remark that
the penultimate inequality has a significant slack for i > 2.)
Lemma 6.6. In Case (B6) ALG does not complete a packet of size `k .
Proof. It suffices to prove


1
τk > t + 1 −
s
since then ALG completes the first `k -sized packet

`k
>t+ 1−
τk +
s


`k ,

(6.2)

at

1
`k
= t + `k ,
`k +
s
s

thus after the fault.
Since Case (B3) and Case (B5) are not triggered, we use Lemma 6.4 for j = k to get τk ≥
t + Sk−1 /s = t + (φk − 1)/s. Recall that k is large enough so that s < φ + 1 − 1/φk−1 which is equivalent
to (φk − 1)/s > (1 − 1/s)φk−1 . This shows (6.2), because τk − t ≥ (φk − 1)/s and `k = φk−1 .
Lemma 6.7. In Case (F4) ALG does not complete any long packet.
Proof. Recall that the first long packet p is started at τ and it has size of at least `i , thus it would be
completed at least at τ + `i /s. We show τ + `i /s − t > `i−1 by the following calculation:
τ+

`i
`i
`i
φ`i
`i
−t≥
+ =
>
= `i−1 ,
s
φ·s
s
s
φ

where the strict inequality holds by s < φ + 1. This implies that the long packet p would be completed
after the next fault at time t + `i−1 .
23

We are ready to prove that at the end of the schedule LADV > LALG + A holds, which contradicts
the claimed 1-competitiveness of ALG. We inspect all the cases in which the instances may end, starting
with Cases (B1) and (F1). We remark that we use only crude bounds to keep the analysis simple.
Lemma 6.8. If the schedule ends in Case (B1) or (F1), we have LADV > LALG + A.
Proof. Recall that each block (t, t0 ] has length of at most φ`k , thus LALG ((t, t0 ]) ≤ sφ`k and LADV ((t, t0 ]) ≤
φ`k .
We call a block in which ADV schedules many ε’s small, other blocks are big. Note that Cases (B3),
(B4), and (F3) concern small blocks, whereas Cases (B5), (B6), and (F4) concern big blocks.
Using Lemma 6.3, we have that in each small block (t, t0 ] it holds LADV ((t, t0 ]) ≥ LALG ((t, t0 ]) + ε.
Let β be the number of small blocks. We observe that


N0 − φ`εk ε
β≥
,
φ`k
because in each such block ADV schedules at most φ`k /ε packets of size ε and PADV (0) < φ`k at the
end in Cases (B1) and (F1).
Pk
The number of big blocks is at most i=1 Ni , since in each such block ADV schedules a packet of
size at least `1 . For each such block we have LADV ((t, t0 ]) − LALG ((t, t0 ]) ≥ −sφ`k which is only a crude
bound, but it suffices for N0 large enough.
Summing over all blocks we obtain


k
k
N0 − φ`εk ε2
X
X
− sφ`k
Ni
LADV − LALG ≥ βε − sφ`k
Ni ≥
φ`k
i=1
i=1
> A + sφ`k

k
X

Ni − sφ`k

i=1

where (6.3) follows from N0 > φ`k (A + 1 + sφ`k

k
X

Ni = A ,

(6.3)

i=1

Pk

i=1

Ni )/ε2 .

It remains to prove the same for termination by Case (F2).
Lemma 6.9. If Strategy Finish ends in Case (F2), then LADV > LALG + A.
Proof. Note that ADV schedules all short packets and all ε’s, i.e., those of size less than `i . In particular,
we have LADV (< i) ≥ LALG (< i).
Call a block in which ALG completes a packet of size at least `i bad. As the length of any block is
at most φ`k we get that LALG (≥ i, (t, t0 ]) ≤ sφ`k for a bad block (t, t0 ]. Bad blocks are created only in
Cases (B5) and (B6), but in each bad block ADV finishes a packet strictly larger than `i ; note that
Pk
here we use Lemmata 6.5 and 6.6. Hence the number of bad blocks is bounded by j=i+1 Nj . As ADV
completes all `i ’s we obtain
LADV (≥ i) − LALG (≥ i) ≥ `i Ni − `k φs

k
X

Nj

j=i+1

> `i `k φs

k
X

Nj + A − `k φs

j=i+1

k
X

Nj ≥ A ,

j=i+1

Pk
where in the strict inequality we used Nk > A/`k for i = k and Ni > `k φs j=i+1 Nj + A/`i for i < k.
By summing it with LADV (< i) ≥ LALG (< i) we conclude that LADV > LALG + A.
Using Lemmata 6.8 and 6.9 we conclude the proof of the theorem.

24

7

Analysis of DIV

In this section we analyze DIV , giving a simple proof that it matches the performance of the algorithms
from [7] on divisible instances. We use the framework of local analysis from Section 4.
Throughout the section we assume that the packet sizes are divisible. We start by a few observations
on divisibility that lead to a strengthening of Lemma 2.2. Recall that rel(t) = s · (t − tB ) is the relative
time after the start of the current phase tB , scaled by the speed of the algorithm.
Lemma 7.1. (i) If DIV starts or completes a packet of size `i at time t, then `i divides rel(t).
(ii) Let t be a time with rel(t) divisible by `i and rel(t) > 0. If a packet of size `i is pending at time t,
then DIV starts or continues running a packet of size at least `i at time t.
(iii) If at the beginning of phase at time u a packet of size `i is pending and no fault occurs before time
t = u + `i /s, then the phase does not end before t.
Proof. (i) follows trivially from the description of the algorithm.
(ii): If DIV continues running some packet at t, it cannot be a packet smaller than `i by (i) and
the claim follows. If DIV starts a new packet, then a packet of size `i is pending by the assumption.
Furthermore, it satisfies all the conditions from Step 3 of the algorithm, as rel(t) is divisible by `i and
rel(t) ≥ `i (from rel(t) > 0 and divisibility).
(iii): We proceed by induction on i. Assume that no fault happens before t. If the phase starts by
a packet of size at least `i , the claim holds trivially, as the packet is not completed before t. This also
proves the base of the induction for i = 1.
It remains to handle the case when the phase starts by a packet smaller than `i . Let P <i be the set
of all packets of size smaller than `i pending at time u. By the Step (2) of the algorithm, `(P <i ) ≥ `i .
We show that all packets of P <i are completed if no fault happens, which implies that the phase does not
end before t.
Let j be such that `j is the maximum size of a packet in P <i ; note that j exists, as the phase starts by
a packet smaller than `i . By the induction assumption, the phase does not end before time t0 = u + `j /s.
From time t0 on, the conditions in Step (3) guarantee that the remaining packets from P <i are processed
from the largest ones, possibly interleaved with some of the newly arriving packets of larger sizes, as
rel(τ ) for the current time τ is always divisible by the size of the largest pending packet from P <i . This
shows that the phase cannot end before all packets from P <i are completed, if no fault happens.
Now we prove a stronger analogue of Lemma 4.3.
Lemma 7.2. (i) If (u, v] is an initial i-segment then LDIV (s) (≥ i, (u, v]) > s(v − u) − 3`k .
(ii) If (u, v] is a proper i-segment and s(v − u) ≥ `i then LDIV (s) (≥ i, (u, v]) > s(v − u)/2 − `i ;
furthermore LDIV (s) ((u, v]) > s(v − u)/2 and LDIV (s) ((u, v]) is divisible by `i .
Proof. Suppose that time t ∈ [u, v) satisfies that rel(t) divisible by `i and rel(t) > 0. Then observe that
Lemma 7.1(ii) together with the assumption that a packet of size `i is always pending in [u, v) implies
that from time t on only packets of size at least `i are scheduled, and thus the current phase does not
end before v.
For a proper i-segment (u, v], the previous observation for t = u + `i /s immediately implies (ii):
Observe that t ≤ v by the assumption of (ii). Now LDIV (s) (< i, (u, v]) is either equal to 0 (if the phase
starts by a packet of size `i at time u) or equal to `i (if the phase starts by a smaller packet). In both
cases `i divides LDIV (s) (< i, (u, v]) and thus also LDIV (s) ((u, v]). As in the analysis of MAIN , the total
size of completed packets is more than s(v − u)/2 and (ii) follows.
For an initial i-segment (u, v] we first observe that the claim is trivial if s(v − u) ≤ 2`i . So we may
assume that u + 2`i /s ≤ v. Now we distinguish two cases:
1. The phase of u ends at some time u0 ≤ u + `i /s: Then, by Lemma 7.1(iii) and the initial observation,
the phase that immediately follows the one of u does not end in (u0 , v) and from time u0 + `i /s on,
only packets of size at least `i are scheduled. Thus LDIV (s) (< i, (u, v]) ≤ 2`i .
2. The phase of u does not end by time u + `i /s: Thus there exists t ∈ (u, u + `i /s] such that `i
divides rel(t) and also rel(t) > 0 as t > u. Using the initial observation for this t we obtain that the
phase does not end in (u, v) and from time t on only packets of size at least `i are scheduled. Thus
LDIV (s) (< i, (u, v]) ≤ `i .
25

In both cases LDIV (s) (< i, (u, v]) ≤ 2`i , furthermore only a single packet is possibly unfinished at time v.
Thus LDIV (s) (≥ i, (u, v]) > s(v − u) − 2`i − `k and (i) follows.
Theorem 7.3. Let the packet sizes be divisible. Then DIV (1) is 2-competitive. Also, for any speed s ≥ 2,
DIV (s) is 1-competitive.
Proof. Lemma 7.2(i) implies (4.2). We now prove (4.1) for any proper i-segment (u, v] with v − u ≥ `i
and appropriate R. The theorem then follows by the Master Theorem.
Since u is a time of a fault, we have LOPT (≥ i, (u, v]) ≤ v − u. If LOPT (≥ i, (u, v]) = 0, (4.1) is trivial.
Otherwise LOPT (≥ i, (u, v]) ≥ `i , thus v − u ≥ `i ≥ `i /s and the assumption of Lemma 7.2(ii) holds.
For s ≥ 2, Lemma 7.2(ii) implies
LDIV (s) (≥ i, (u, v]) > s(v − u)/2 − `i ≥ v − u − `i ≥ LOPT (≥ i, (u, v]) − `i .
Since both LDIV (s) (≥ i, (u, v]) and LOPT (≥ i, (u, v]) are divisible by `i , this implies LDIV (s) (≥ i, (u, v]) ≥
LOPT (≥ i, (u, v]), i.e., (4.1) holds for R = 1.
For s = 1, Lemma 7.2(ii) implies
LDIV ((u, v]) + LDIV (≥ i, (u, v]) > (v − u)/2 + (v − u)/2 − `i
≥ v − u − `i ≥ LOPT (≥ i, (u, v]) − `i .
The divisibility of LDIV ((u, v]), LDIV (≥ i, (u, v]), and LOPT (≥ i, (u, v]) by `i implies LDIV ((u, v]) +
LDIV (≥ i, (u, v]) ≥ LOPT (≥ i, (u, v]), i.e., (4.1) holds for R = 1.

References
[1] Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, Joerg Widmer, and Elli Zavou.
Measuring the impact of adversarial errors on packet scheduling strategies. J. Scheduling, 19(2):135–
152, 2016. Also appeared in Proc. of SIROCCO 2013: 261–273. URL: http://dx.doi.org/10.
1007/s10951-015-0451-z.
[2] Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, and Elli Zavou. Competitive analysis of task scheduling algorithms on a fault-prone machine and the impact of resource augmentation. In Proc. of the 2nd Int. Workshop on Adaptive Resource Management
and Scheduling for Cloud Computing (ARMS-CC@PODC), LNCS 9438, pages 1–16, 2015. URL:
http://dx.doi.org/10.1007/978-3-319-28448-4_1.
[3] Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, and Elli Zavou. Online parallel
scheduling of non-uniform tasks: Trading failures for energy. Theor. Comput. Sci., 590:129–146,
2015. Also appeared in Proc. of FCT 2013: 145-158. URL: http://dx.doi.org/10.1016/j.tcs.
2015.01.027.
[4] Marek Chrobak, Leah Epstein, John Noga, Jiřı́ Sgall, Rob van Stee, Tomáš Tichý, and Nodari
Vakhania. Preemptive scheduling in overloaded systems. J. Comput. Syst. Sci., 67:183–197, 2003.
URL: http://dx.doi.org/10.1016/S0022-0000(03)00070-9.
[5] P. Garncarek, T. Jurdziński, and K. Loryś. Fault-tolerant online packet scheduling on parallel
channels. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS),
pages 347–356, May 2017. doi:10.1109/IPDPS.2017.105.
[6] Chryssis Georgiou and Dariusz R. Kowalski. On the competitiveness of scheduling dynamically
injected tasks on processes prone to crashes and restarts. J. Parallel Distrib. Comput., 84:94–107,
2015. URL: http://dx.doi.org/10.1016/j.jpdc.2015.07.007.
[7] Tomasz Jurdzinski, Dariusz R. Kowalski, and Krzysztof Loryś. Online packet scheduling under
adversarial jamming. In Proc. of the 12th Workshop on Approximation and Online Algorithms
(WAOA), LNCS 8952, pages 193–206, 2014. See http://arxiv.org/abs/1310.4935 for missing
proofs. URL: http://dx.doi.org/10.1007/978-3-319-18263-6_17.
26

[8] Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. of the ACM,
47(4):617–643, 2000. Also appeared in Proc. of the 36nd IEEE Symp. on Foundations of Comput.
Sci. (FOCS), pages 214–221, 1995. URL: http://doi.acm.org/10.1145/347476.347479.
[9] Chiu-Yuen Koo, Tak Wah Lam, Tsuen-Wan Ngan, Kunihiko Sadakane, and Kar-Keung To. On-line
scheduling with tight deadlines. Theor. Comput. Sci., 295:251–261, 2003. URL: http://dx.doi.
org/10.1016/S0304-3975(02)00407-3.
[10] Tak Wah Lam, Tsuen-Wan Ngan, and Kar-Keung To. Performance guarantee for EDF under overload.
J. Algorithms, 52:193–206, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.10.004.
[11] Tak Wah Lam and Kar-Keung To. Trade-offs between speed and processor in hard-deadline scheduling.
In Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 623–632.
ACM/SIAM, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.314884.
[12] Cynthia A. Phillips, Clifford Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling
via resource augmentation. Algorithmica, 32:163–200, 2002. URL: http://dx.doi.org/10.1007/
s00453-001-0068-9.
[13] Kevin Schewior. Deadline Scheduling and Convex-Body Chasing. PhD dissertation, TU Berlin, 2016.
URL: http://dx.doi.org/10.14279/depositonce-5427.

27

