# Root-to-Leaf Scheduling in Write-Optimized Trees

Christopher Chung  Independent Researcher<EMAIL_ADDRESS>William Jannen
Williams College<EMAIL_ADDRESS>Samuel McCauley  Williams
College<EMAIL_ADDRESS>Bertrand Simon  IN2P3 Computing
Center/CNRS<EMAIL_ADDRESS>
###### Abstract

In a large, parallel dictionary, performance is dominated by the cache
efficiency of its database operations. Cache efficiency is analyzed
algorithmically in the disk access machine (DAM) model, in which any $P$
disjoint sets of $B$ contiguous elements can be moved simultaneously for unit
cost.

Write-optimized dictionaries (WODs) are a class of cache-efficient data
structures that buffer updates and apply them in batches to optimize the
amortized update cost in the DAM model. As a concrete example of a WOD,
consider a $B^{\varepsilon}$-tree. $B^{\varepsilon}$-trees encode updates as
messages that are inserted at the root of the tree.

Messages are applied lazily at leaves: $B^{\varepsilon}$-trees only move—or
“flush”—messages when close to $B$ of them can be written simultaneously,
optimizing the amount of work done per DAM model cost. Thus, recently-inserted
messages reside at or near the root and are only flushed down the tree after a
sufficient number of new messages arrive. Other WODs operate similarly.

Although this lazy approach works well for many operations, some types of
updates do not complete until the update message reaches a leaf. For example,
both deferred queries and secure deletes must flush through all nodes along
their root-to-leaf path before the operation takes effect.

What happens when we want to service a large number of (say) secure deletes as
quickly as possible? Classic techniques leave us with an unsavory choice. On
the one hand, we can group the delete messages using a write-optimized
approach and move them down the tree lazily. But, then many individual deletes
may be left incomplete for an extended period of time, as their messages sit
high in the tree waiting to be grouped with a sufficiently large number of
related messages. On the other hand, we can ignore cache efficiency and
perform a root-to-leaf flush for each delete. This begins work on individual
deletes immediately, but performs little work per unit cost, harming system
throughput. We propose a middle ground to this all-or-nothing tradeoff.

This paper investigates a new framework for efficiently flushing collections
of messages from the root to their leaves in a write-optimized data structure.
We model each message as completing when it has been flushed to its leaf; our
goal is to minimize the average completion time in the DAM model. We give an
algorithm that $O(1)$-approximates the optimal average completion time in this
model (whereas achieving the optimal solution is NP-hard). Along the way, we
give a new $O(1)$-approximation algorithm for a classic scheduling problem:
scheduling parallel tasks for weighted completion time with tree precedence
constraints.

##  1 Introduction

In large, parallel dictionaries, performance hinges on the cache efficiency of
database operations. Therefore, data structures such as $B$-trees that achieve
strong guarantees on their cache efficiency have become ubiquitous in modern
databases.

The Disk Access Machine (DAM) model [2] is a powerful tool for theoretically
describing the cache efficiency of a data structure. In the DAM model there
are three machine-dependent parameters: $B$, the size of a cache line; $P$,
the number of disk accesses that can be performed in parallel; and $M\gg PB$,
the size of the cache. In a single _IO_ , the data structure can read or write
up to $P$ sets of $B$ contiguous elements to or from cache. The cost of any
process under the DAM model is defined as the number of IOs required to
complete the process.

Recently, write-optimized data structures have revolutionized the theory of
cache-efficient data structures [9, 33, 12, 4, 34, 7, 5]. A _write-optimized_
data structure handles inserts lazily: rather than traversing the data
structure to put newly-inserted items directly in place, up to $B$ items are
accumulated and moved through the data structure in large IOs. Write-optimized
data structures greatly improve insert performance in the DAM model. For
example, if the cache size $B$ is much larger than the height of the data
structure, a write-optimized data structure requires $o(1)$ IOs per insertion.
This improvement in write cost comes at no asymptotic cost to query time.

This performance improvement has also been realized in practice. LSM-trees,
$B^{\varepsilon}$-trees, and their variants are popular WODs that have been
used to implement file systems [22, 23, 44, 24, 38, 37, 14], key-value stores
[16, 40, 30, 35], and other applications where cache efficiency is critical.

####  $B^{\varepsilon}$-trees

In this paper, our model and algorithmic results are specifically tailored to
flushes in the $B^{\varepsilon}$-tree, a classic WOD originally presented in
[9]. Nonetheless, it is likely that similar strategies to those presented here
would apply to other WODs, such as LSM-trees. For example, see the discussion
in [5] of the similarities between LSM compaction strategies and
$B^{\varepsilon}$-tree flushing policies.

We now briefly describe the structure of $B^{\varepsilon}$-trees as well as
$B^{\varepsilon}$-tree insert and query operations. See e.g. [9, 6] for more
detailed descriptions.

$B^{\varepsilon}$-trees, like $B$-trees, are trees of nodes of size $B$. All
$B^{\varepsilon}$-tree leaves are at the same height, all
$B^{\varepsilon}$-tree keys are stored in binary search tree order, and every
$B^{\varepsilon}$-tree node has $\Theta(B^{\varepsilon})$ children.
$B^{\varepsilon}$-tree nodes maintain internal state so that these invariants
can be maintained efficiently.

Each $B^{\varepsilon}$-tree node has a _buffer_ in which messages can be
stored. (Thus, a node can be read or written in a single IO.) We ignore the
internal state of a node: we assume the tree is static and that we always know
the leaf where any key should be stored. Thus we treat each node as consisting
solely of a buffer of size exactly $B$.

To insert an item into a $B^{\varepsilon}$-tree, place the item in the root
node’s buffer. Then, recursively flush as follows: if the buffer of a node $v$
is full, go through all $B$ items in the buffer and determine which child they
would be flushed to next. The child with the most such items is flushed to,
moving every possible item to that child; recurse if the child now has $B$ or
more items.

To query an item, traverse the root-to-leaf path $p$ of the tree using the
binary search tree ordering. The binary search tree ordering guarantees that
the queried item is stored along this path. For each node $v$ in $p$,
determine if any of the $B$ items in the buffer of $v$ are the queried item.

#### Parallelism

Modern large-scale systems can often access several disjoint cache lines in
parallel. This directly models the behavior of SSDs [11, 3]. These parallel
accesses have been implemented for flushes in practical WODs-based databases
such as RocksDB [41].

Following the DAM model [2], $P$ denotes the number of accesses that can be
performed in parallel. Thus, up to $P$ disjoint flushes can be performed in a
single IO. Generally, $P$ is a small constant on real-world systems; however,
we do not assume that $P$ is a constant in our results (i.e. our
$O(1)$-approximation holds for any $P$).

#### Upserts and Write-Optimization

Crucially, WOD performance features read-write asymmetry: write-optimization
drastically speeds insertions, whereas queries cannot be write-optimized and
are therefore much more expensive. This asymmetry follows from a distinction
in what each operation requires. Insertions are flexible: the only requirement
for newly inserted items is that they are findable by subsequent queries.
Queries, on the other hand, must immediately and correctly return. We
therefore cannot amortize standard query costs.

This observation leads to the question: what operations can we write optimize,
i.e., encode the operations as data that is lazily flushed down the tree? Such
operations are called _upserts_. A classic example is deletes: rather than
finding and removing the element, we can insert a “tombstone” message that is
slowly flushed down the tree, only truly removing the item when the tombstone
meets the actual element [6]. This approach does not affect query correctness
so long as queries search for tombstone elements—a query that finds a
tombstone acts as if the element was already deleted. With this improvement,
deletes can enjoy write-optimized-insert performance. Recent work has given
similar results for a class of queries that can be deferred [21]; by encoding
a query as a deferred query—or “derange query”—message, a WOD can delay
answering the query until the time that the derange query message meets the
data of interest.

#### Flushing a Root-to-Leaf Path

This paper addresses a broad issue that arises when using upserts to achieve
write-optimized performance: _some WOD operations may remain incomplete until
an entire root-to-leaf path has been flushed_. We call these _root-to-leaf
operations_.

As already discussed, deferred queries fall under this category: we cannot
answer a deferred query for an item until we have checked every buffer along
its path. However, subtler issues may also arise. Consider deletion. As
explained above, $B^{\varepsilon}$-tree items are deleted by inserting a
tombstone to signal that the item is no longer valid. However, many
applications demand a _secure delete_ , where even an adversary who is given
access to the system is unable to recover an item [36]. Tombstone messages do
not realize secure deletion. To see why, consider an adversary that is able to
examine the data structure’s contents offline; although a tombstone renders an
item _logically_ invalid, the item remains _physically_ present until it is
removed from the tree. To realize secure deletion, a $B^{\varepsilon}$-tree
must therefore flush a tombstone along an entire root-to-leaf path, purging
the physical data from the leaf.

#### A New Kind of Latency

Root-to-leaf operations motivate a new latency consideration for WODs.
Traditionally, the latency for $B^{\varepsilon}$-tree operations fall into two
categories: read operations (e.g., queries) must be answered immediately via
multiple IOs, whereas write operations (e.g., inserts, upserts) benefit from
write-optimized batching and the flexibility to delay flushes indefinitely.

This leaves open the question: what happens when there is a backlog of root-
to-leaf operations? For example, a large number of deferred queries may have
nearby deadlines. Or, a firm may want to perform nightly purges of sensitive
information by querying for outdated data and then secure deleting it—thus
producing a large batch of root-to-leaf operations at the end of each working
day.

When a large number of root-to-leaf operations arrive simultaneously, we want
to complete the operations as quickly as possible. These circumstances provide
a new (and, we will see, structurally rich) set of considerations for how to
flush items in a $B^{\varepsilon}$-tree. There is some notion of write-
optimization: since many operations are being completed simultaneously, we can
group similar operations together to improve the amount of work done per IO.
But there is also a notion of latency: we must complete operations as quickly
as possible, which may entail performing less-efficient flushes lower in the
tree before performing flushes higher in the tree. Known flushing techniques
do not suffice: handling operations one by one (as traditionally done for
queries) leads to pessimal throughput, whereas greedily grouping operations
(as traditionally done for inserts/upserts) leads to terrible latency.

This poses a scheduling problem. We can view the running of the data structure
as proceeding in a sequence of _time steps_ , with 1 IO—and therefore $P$
flushes—per time step. The goal is to schedule flushes to complete all
operations as quickly as possible.

We emphasize that in many applications, it is crucial to minimize the average
(as opposed to maximum) completion time. For example, this maximizes the
throughput of the $B^{\varepsilon}$-tree if it is experiencing a temporary
backlog. Alternatively, it gives the strongest security guarantee possible for
secure deletes: as many items are deleted as possible if the data structure is
compromised before all deletes could be completed.

In this paper we give an algorithm to complete an offline set of root-to-leaf
operations as quickly as possible. We model these operations as _messages_ :
each message must be flushed to some leaf in the tree, and the message does
not complete until it reaches that leaf. The goal is to minimize the average
completion time (since the number of messages is fixed, we equivalently
minimize the total completion time).

###  1.1 Results

We give an $O(1)$-approximation algorithm for the problem of scheduling write
optimized tree flushes so that messages reach the leaf as quickly as possible
on average. We show that this problem is NP-hard, so a constant approximation
factor is the best we can hope for in the worst case.

Our solution works by reducing this problem to a classic scheduling
problem:111We formally define this scheduling problem below. In short, the
goal is to schedule tasks on $P$ machines to minimize total weighted
completion time. All tasks can be completed in one time step. The tasks have
precedence constraints, where the graph of precedence constraints must be an
out-directed forest. $P|outtree,\allowbreak p_{j}=1|\sum wC$. We give a
$4$-approximation algorithm for this scheduling problem. This is not as good
as the best known approximation factor of approximately $2.41$ by Li [28], but
our algorithm is simpler.

###  1.2 Related Work

As mentioned above, previous work on write-optimizing non-insert operation has
focused on upsert operations like deferred range queries [21] and deletes [6].

A wider variety of work has focused on improved flushing methods for
$B^{\varepsilon}$-trees and compaction strategies for LSMs. Indeed, much past
work has benefited practical implementations (i.e. [41]) in addition to
published research [13, 35, 43, 29].

A long line of work has focused on engineering traditional (not write-
optimized) external-memory trees to improve performance on access sequences
that are fully or partially known in advance; for example [31, 8, 17, 1, 39,
25, 15, 10]. This line of work generally focuses on changing the shape of the
tree and/or updating pivots rather than efficiently moving elements down a
static tree.

A long line of scheduling work has examined problems similar to
$P|outtree,\allowbreak p_{j}=1|\sum wC$. A classic result of Horn gives an
optimal algorithm for $1|outtree|\sum wC$ [19]. Meanwhile, $P|outtree|\sum wC$
is known to be NP-hard [27]. A line of work on $P|prec,p_{j}=1|\sum wC$ [18,
32] lead to the best-known approximation ratio of $1+\sqrt{2}$ by Li [28];
this remains the best known approximation ratio for $P|outtree,\allowbreak
p_{j}=1|\sum wC$. Other work has focused on practical heuristics for parallel
scheduling with precedence constraints; see e.g. [26] for a survey.

Recently, Jager and Warode gave a simple algorithm for $P|prec,\allowbreak
pmtn|\sum wC$ independently of this work [20]. Their algorithm is more general
(it works for arbitrary rather than outtree precedence constraints, and for
preemption rather than assuming $p_{j}=1$) and achieves a better approximation
ratio. However, while this result is simpler and faster than the state-of-the-
art LP-rounding-based method in [28], it uses parametric flows, resulting in
$O(n^{4})$ running time compared to our simple greedy $O(n\log n)$ result. We
believe both results have independent merit.

##  2 Preliminaries

###  2.1 Problem Definition

An instance of the problem consists of a (static) tree $T$, a set of messages
$M$, and two DAM model parameters $P$ and $B$.222The classic DAM model has an
additional parameter called $M$ denoting the size of cache. We ignore this
parameter as it does not affect our results; we only use $M$ to denote
messages. We give our running times in terms of $n=|M|+|T|$.

For each node $v\in T$, we denote the number of edges on the path between $v$
and the root as $h(v)$; we call this the _height_ of $v$. We denote the height
of $T$ as $h=\max h(v)$. We say that a node $v^{\prime}$ is a descendant of
$v$ if $v^{\prime}=v$ or $v^{\prime}$ is the child of a descendant of $v$. An
edge $e=(v_{1},v_{2})$ is a descendant of $v$ if $v_{1}$ and $v_{2}$ are
descendants of $v$.

Each message $m$ has a _target leaf_ representing the final leaf where $m$
must be sent.333We assume that all messages are being sent to leaves for
simplicity; our techniques likely extend to handle messages with internal
targets. We assume that all leaves in the tree are at height $h$.444Our
results generalize immediately so long as the average height of a target leaf
is $\Omega(h)$.

We assume that all parameters remain unchanged through the execution of the
algorithm: in particular, the structure of $T$ is not changed due to
rebalances, and the target leaf of each message remains the same. Since the
structure of a $B^{\varepsilon}$-tree only changes on inserts, we can
alternatively assume that there are no inserts while messages are being
flushed (or that rebalances caused by inserts are delayed until after flushes
are completed). We leave to future work to find an algorithm that can handle
inserts interleaved with message flushes.

#### Flushes

A schedule $S$ consists of a sequence of flushes, with at most $P$
simultaneous flushes per _time step_.

A _flush_ $f$ is defined by an edge $(v,v^{\prime})\in T$ where $v^{\prime}$
is a child of $v$, and a set of at most $B$ messages $M_{f}$.555Each flush has
at most $B$ messages; the parameter $B$ additionally constrains the number of
messages stored in each node below. We also use flush as a verb: the schedule
flushes the messages in $M_{f}$ from $v$ to $v^{\prime}$. No message may be in
two different flushes in the same time step. Thus, a flush in a schedule $S$
at time step $t$ is a _valid flush_ if all messages in $M_{f}$ are in $v$ at
$t$, and every other flush $f^{\prime}$ at $t$ has $M_{f}\cap
M_{f^{\prime}}=\emptyset$. All messages in $M_{f}$ are moved to $v^{\prime}$
after the flush ends—thus, they are in $v^{\prime}$ at time step $t+1$.

#### Node sizes

The nodes in a write-optimized tree have a size limit: any internal non-root
node $v\in T$ can contain up to $B$ messages at any time.

However, write-optimized data structures do not obey a strict size limit when
there are _cascades_ : a large number of messages flushed down a path toward
the same node. Consider, for example, two internal nodes, $v_{1}$ and $v_{2}$,
and a leaf $\ell$, where $v_{1}$ is the parent of $v_{2}$ and $v_{2}$ is the
parent of $\ell$. One may want to take all messages in $v_{1}$ with target
leaf $\ell$ and flush them to $v_{2}$; then, flush all messages in $v_{2}$
with target leaf $\ell$ to $\ell$ (see Figure 1). These cascades are
fundamental to write optimized tree flushing; for example, the work of Bender
et al. [5] is dedicated entirely to limiting the size of these cascades.

Notice, however, that a cascade may cause $v_{2}$ to _temporarily_ overflow in
this example if $v_{2}$ already contained close to $B$ messages. Because the
overflow is temporary, tree implementations permit cascades in practice
(overflowing messages can be handled with a small amount of scratch space).

AAAA$v_{1}$AAAA$v_{2}$AAAA$\ell$$t$Time step:

AAAA$v_{1}$AAAAI$v_{2}$AAAA$\ell$$t+1$

AAAA$v_{1}$AAAA$v_{2}$AAAA$\ell$$t+2$

Figure 1: This figure shows three successive time steps during a cascade of
three nodes $v_{1}$, $v_{2}$, and $\ell$. The flush that will occur in the
next time step is shown with an orange dotted line. Messages that have $\ell$
as a target leaf are represented in red; all others are represented in green
or blue. $v_{2}$ temporarily overflows on the second time step, allowing all
messages to be flushed in two time steps.

To allow for schedules that include cascades, nodes may _overflow_ : a node
may contain more than $B$ messages, so long as at most $B$ of them remain in
the node at the next time step. Allowing overflows this way reflects the usage
of write optimized trees with cascades: only $B$ messages can be written to a
node, but a cascade of flushes to a common location can take place even if the
cascade causes nodes to temporarily have size more than $B$. We emphasize that
the limit that only $B$ messages can participate in a flush remains a strict
limit.

Thus, we formally define the _space requirement_ of each node as follows. For
each internal, non-root node $v\in T$ and each time step $t$, there can be at
most $B$ messages that are in $v$ at both time steps $t$ and $t+1$. We allow
the root and the leaves to hold an unlimited number of messages.

#### Valid Schedules and Cost

We say that a schedule $S$ is _valid_ if all flushes are valid, all messages
are flushed to their target leaf during $S$, and all nodes satisfy the space
requirement.

A schedule $S$ is _overfilling_ if all flushes are valid and all messages are
flushed to their target leaf during $S$. An overfilling schedule may have
nodes that do not satisfy the space requirement. An overfilling schedule is
not a solution to our problem, but building an overfilling schedule is a
useful intermediate step in our results.

Let $c(S,m)$ denote the completion time of any message $m$ (i.e. the time when
$m$ reaches its target leaf) in a schedule $S$. We also say that $m$
_finishes_ at $c(S,m)$ in $S$. The cost of a schedule is the total completion
time: ${c(S)=\sum_{m\in M}c(S,m)}$.

The goal of this model is to, for any $(T,M,P,B)$, find the valid schedule
that minimizes the total completion time. Throughout the paper we call this
model _write-optimized root-to-leaf message scheduling_ , or _WORMS_.

###  2.2 Scheduling with Tree Precedence Constraints

Our algorithm works by reducing WORMS to a classic scheduling problem,
$P|outtree,\allowbreak p_{j}=1|\sum wC$, which we define and discuss here.

An instance of $P|outtree,\allowbreak p_{j}=1|\sum wC$ consists of a set of
_tasks_. Each task $t$ has processing time $1$ (i.e. $p_{j}=1)$; therefore, a
task can be completed by assigning it to one machine for one time step. Each
task $j$ has a weight $w(j)$. The objective $\sum wC$ is to minimize the total
weighted completion time of all tasks: if task $j$ completes at time
$c(\sigma,j)$ under any schedule $\sigma$, the cost of a schedule $\sigma$ is
$cost(\sigma)=\sum_{j}c(\sigma,j)w(j)$. The goal is to find the schedule
$\sigma_{O}$ minimizing $cost(\sigma_{O})$.

The $P$ in $P|outtree,\allowbreak p_{j}=1|\sum wC$ represents that there are
$P$ machines, and therefore up to $P$ tasks can be completed at each time
step. (This is a slight abuse of notation as $P$ also represents the number of
parallel flushes in the WORMS model. However, $P$ has the same value in both:
a WORMS instance with parameter $P$ results in a $P|outtree,\allowbreak
p_{j}=1|\sum wC$ instance with $P$ machines.)

The $outtree$ in $P|outtree,p_{j}=1|\sum wC$ represents that the tasks have
_outtree precedence constraints_. For each task $j$, there is at most one task
$j^{\prime}$ such that $j$ cannot be processed until $j^{\prime}$ is
completed; thus $j^{\prime}$ must be scheduled in a time step strictly before
$j$ in any schedule. There cannot be cycles in these constraints (as no task
in a cycle can ever be completed). The limitations that there is at most one
$j^{\prime}$, and no cycles, are why these are “outtree” precedence
constraints. We refer to one task as a parent/child/descendant (etc.) of
another in the natural way according to the precedence constraints in this
tree.

##  3 Using $P|outtree,\allowbreak p_{j}=1|\sum wC$ to Solve WORMS

In this section we reduce WORMS to a classic scheduling problem:
$P|outtree,\allowbreak p_{j}=1|\sum wC$. We proceed in two steps. First, we
show how to convert any overfilling schedule to a valid schedule while losing
only a constant factor in cost. With this result in hand, we show that every
overfilling schedule is reducible to to an instance of $P|outtree,\allowbreak
p_{j}=1|\sum wC$.

###  3.1 Converting Overfilling Schedules to Valid Schedules

In this section we show that overfilling schedules can be converted to valid
schedules while only increasing the cost by a constant factor.

######  Lemma 1.

There is a constant $c_{1}$ such that for any overfilling schedule $S$ for a
WORMS instance $(T,M,P,B)$, we can in $O(n\log n)$ time give a valid schedule
$\hat{S}$ for WORMS satisfying $cost(\hat{S})\leq c_{1}\cdot cost(S)$.

The remainder of this subsection is dedicated to proving this lemma. We fix an
overfilling schedule $S$ for a WORMS instance $(T,M,P,B)$ and build a valid
schedule $\hat{S}$.

#### Defining Packed Nodes

We define the packed nodes of $(T,M,P,B)$ via a bottom-up traversal of $T$ as
follows. For each $h^{\prime}$ from $h$ to $1$, for each node $v$ at height
$h^{\prime}$, let $C(v)$ be the set of all messages $m$ such that: (1) the
target leaf of $m$ is a descendant of $v$, and (2) $m$ is not in
$C(v^{\prime})$ for any packed node $v^{\prime}$ with
$h(v^{\prime})>h^{\prime}$. Then $v$ is a _packed node_ if $|C(v)|\geq B/6$.
We call $C(v)$ the _packed contents_ of $v$. The root is a packed node, and
its packed contents are all messages that are not in another packed node.
Therefore, each message is in the packed contents of exactly one packed node.

#### Packed Sets

We further subdivide packed nodes based on $S$. For any packed node $v$ with
packed contents $C(v)$, if $v$ is a leaf, order messages in $C(v)$ by their
completion time in $S$, and then partition $C(v)$ arbitrarily into packed sets
with total weight between $B/6$ and $B/2$. If $v$ is an internal node, order
the messages within $C(v)$ by the time when the messages are flushed from $v$
to one of its children in $S$. Then, partition the messages into sets with
total weight between666This can be done greedily: consider each child of $v$
in turn, adding to the current packed set until it has size at least $B/6$;
since each child of $v$ has at most $B/6$ remaining messages, each resulting
set has size at most $B/3$. There may be extra children at the end with at
most $B/6$ total messages; add them to the final packed set, giving size at
most $B/2$. $B/6$ and $B/2$ such that if two messages are flushed to the same
child of $v$ at the same time they are in the same packed set. We call these
the _packed sets_ of $v$, and we say that $v$ is the _packed parent_ of each
such set, as well as each message in each set. We will use the term “packed
sets” (without referring to a specific packed node) to refer to all packed
sets of all packed nodes.

For any node $v$, let $\mathcal{C}(v)=C_{1},C_{2},\ldots$ be the sequence of
packed sets of $v$, sorted by the last time any message in the packed set is
flushed out of $v$.

for tree=inner sep=0pt, circle, minimum size=2ex, draw, s sep=1.2ex, ,
[,label=left:$3$,name=l1,color=black,draw, thick [,color=nicepurple,fill
[,color=black,draw [,color=black,draw
[,label=below:$40$,color=black,draw,thick] [,label=below:$3$,color=black,draw]
] [,label=right:$11$,color=black,draw,thick
[,label=below:$5$,color=niceblue,fill ] [,label=below:$6$,color=niceblue,fill
] ] ] [,label=right:$36$,color=black,draw,thick [,color=niceorange,fill
[,label=below:$6$,color=black,draw ] [,label=below:$3$,color=black,draw ] ]
[,color=niceorange,fill [,label=below:$9$,color=black,draw ] ]
[,color=niceyellow,fill [,label=below:$9$,color=black,draw ] ]
[,color=niceyellow,fill [,label=below:$4$,color=black,draw ]
[,label=below:$5$,color=black,draw ] ] ] ]
[,label=right:$23$,color=black,draw,thick [,color=purple,fill
[,color=black,draw [,label=below:$5$,color=black,draw ]
[,label=below:$3$,color=black,draw ] ] [,color=black,draw
[,label=below:$1$,color=black,draw ] ] ] [,color=purple,fill
[,label=right:$14$,color=black,draw,thick
[,label=below:$6$,color=nicegreen,fill ]
[,label=below:$8$,color=nicegreen,fill ] ] [,color=black,draw
[,label=below:$3$,color=black,draw] [,label=below:$3$,color=black,draw] ] ] ]
] [right=7ex of l1,minimum width=6ex,minimum height=3ex] (label) $B=60$;

Figure 2: Packed sets of an example WORMS instance. Each leaf $\ell$ is
labelled with the number of messages that have $\ell$ as a target leaf. Packed
parents are bolded and labelled with the size of their packed contents.
Children of an internal packed parent are filled and are colored according to
the packed set their messages belong to.

Consider a packed node $v$ with packed sets $\mathcal{C}(v)$; let $C_{i}$ be a
packed set in $\mathcal{C}(v)$. If $v$ is a leaf, define the starting time of
$C_{i}$ to be the time step when the $B/12$th message in $C_{i}$ arrives at
$v$. If $v$ is an internal if $i>1$, define the _starting time_ of $C_{i}$,
denoted $\tau_{i}$, to be the time step when the last message in $C_{i-1}$ is
flushed out of $v$ in $S$. If $i=1$, define the starting time to be the time
step $\tau_{1}$ after which at least $B/12$ messages in $C_{1}$ have been
flushed out of $v$.

When building $\hat{S}$, the plan will be for all messages in a packed set to
arrive at their packed parent at their starting time. This may delay the
message’s finishing time in $\hat{S}$ past its finishing time in $S$. Thus, we
give two properties of the starting time of a packed set that allow us to
charge these delays. First, by a packed set’s starting time, $\Omega(B)$
messages must have been flushed to a packed parent. Second, the total starting
times lower bound the cost of $S$.

######  Lemma 2.

If $C_{i}\in\mathcal{C}(v)$ is a packed set with packed parent $v$ and start
time $\tau$, at least $B/12$ messages in $C_{i}$ or $C_{i-1}$ were flushed to
$v$ strictly before $\tau$ in $S$.

###### Proof.

By definition: if $v$ is internal, we define the starting time such that
$B/12$ messages from $C_{i}$ or $C_{i-1}$ were flushed _out_ of $v$ by $\tau$;
since $S$ is overfilling they must have been flushed to $v$ before this time.
If $v$ is a leaf, $B/12$ messages in $C_{i}$ were flushed to $v$ by $\tau$. ∎

######  Lemma 3.

For any message $m$, let $\tau(m)$ be the starting time of the packed set of
$m$. Then $\sum_{m\in M}\tau(m)\leq 2c(S)$.

###### Proof.

Consider a packed set $C_{i}\in\mathcal{C}(v)$ with starting time $\tau_{i}$
and packed parent $v$. If $i>1$ and $v$ is internal, then each message $m\in
C_{i}$ must finish after time step $\tau_{i}$ by construction. If $i=1$, or
$v$ is a leaf, then all but the first $B/12$ messages in $C_{i}$ must finish
after $\tau_{i}$ by construction. Since $|C_{i}|\geq B/6$, at least half the
messages in $C_{i}$ must finish after $\tau_{i}$.

In other words, $\sum_{m\in C_{i}}c(S,m)\geq\tau_{i}(|C|/2)$. Thus,

$\sum_{m\in M}\tau(m)=\sum_{C_{i}}\tau_{i}|C_{i}|\leq\sum_{C_{i}}\sum_{m\in
C_{i}}2c(S,m)=2c(S).\qed$

#### Three Partial Schedules

We define $\hat{S}$ using three schedules of flushes: $U$, $U_{r}$ and $L$.
Intuitively, $U$ handles all flushes of messages from the root to their packed
node and $U_{r}$ is a modification of $U$ that can be more easily merged with
$L$; $L$ handles all flushes of messages from their packed node to their
target leaf.

Notice that none of $U$, $U_{r}$, or $L$ are necessarily valid or overfilling:
$U$ and $U_{r}$ may not flush a message to its target leaf, and $L$ may flush
a message $m$ from a node $v$ without flushing $m$ to $v$ first. Only when we
combine $U_{r}$ and $L$ will we create a valid schedule $\hat{S}$.

First, we define $U$. In short, we greedily schedule flushes of each packed
set to its packed parent in order by its starting time. More formally,
consider each packed set $C$ in order by its starting time $\tau$, breaking
ties arbitrarily. Let $h(C)$ be the height of $v$, the packed node containing
$C$. We would like to schedule $h(C)$ flushes, each containing the messages in
$C$, from the root to $v$ beginning at $\tau-h+1$; thus the messages in $C$
arrive in $v$ at $\tau$. If this is possible—there are not $P$ flushes already
scheduled at time $\tau-h(C)+1$—then we add these flushes to $U$. Otherwise,
we add these flushes to $U$ at the earliest time step when there are less than
$P$ already-scheduled flushes. Creating $U$ in this way requires $O(n\log n)$
time.

Inductively, all flushes of a packed set $C$ are in $h(C)$ consecutive time
steps in $U$. In particular, because we schedule using increasing time steps,
if we find an empty slot on some machine, there will be no later non-empty
slots on that machine, so we can always schedule all $h$ time steps
consecutively in $U$ on the same machine.

This greedy schedule guarantees that each packed set arrives at its packed
node close to its starting time.

######  Lemma 4.

For any packed set ${C}$ with starting time $\tau$ and packed parent $v$, all
messages in ${C}$ arrive at $v$ in $U$ on or before time step $13\tau$.

###### Proof.

Let $\delta(C)$ be the difference between $\tau-h(C)+1$ and the time when the
first flush of $C$ begins. It is sufficient to prove that $\delta({C})\leq
12\tau$.

By construction there are $P$ flushes scheduled during all time steps between
$\tau-h(C)+1$ and $\tau-h(C)+\delta({C})$. Let $\mathcal{C}_{t}$ be the set of
packed sets that have a flush during one of these time steps. Any packed set
$C$ has at most $h(C)$ flushes in $U$, and $P$ flushes are performed in that
$\delta({C})-1$ time steps starting at $\tau$. Then we have that

$\delta({C})-1\leq\sum_{C\in\mathcal{C}_{t}}h(C)/P.$

Let $\mathcal{C}_{E}$ consist of all packed sets with starting times before
$\tau$, or equal to $\tau$ with an earlier tiebreaker. Then
$\mathcal{C}_{t}\subseteq\mathcal{C}_{E}$.

By Lemma 2, for any $C$ in $\mathcal{C}_{E}$, there must have been at least
$B/12$ messages flushed $h(C)$ times by $\tau$. $S$ can flush at most $PB$
messages in a single time step; thus

$\left(\sum_{C\in\mathcal{C}_{E}}\frac{B}{12}\cdot
h(C)\middle/PB\right)=\sum_{C\in\mathcal{C}_{E}}h(C)/12P\geq\tau.$

Combining, $\delta({C})\leq 12\tau$. ∎

Now, we define $L$. To begin, we define vocabulary based on $S$. We call a
message $m$ in a flush $f\in S$ on an edge $(v_{1},v_{2})$ a _lower message_
if $m\in C(v)$ for a packed node $v$ where $v_{1}$ is a descendant of $v$. We
call $f$ a _lower flush_ if it contains a lower message. By the definition of
a packed set, all lower messages in a flush have the same packed parent.

To define $L$, iterate through the time steps $t$ of $S$ from $t=1$ to the
end. Consider each of the $\leq P$ flushes $f_{i}$ from $v_{i}$ to
$v_{i}^{\prime}$ at $t$. For each such $f_{i}$, if $v_{i}$ is the packed
parent of all lower messages in $f_{i}$, schedule a flush in $L$ from $v_{i}$
to $v_{i}^{\prime}$

in the earliest available time step777I.e. the first time step with fewer than
$P$ flushes already scheduled. after $27\tau_{i}$, consisting of all lower
messages in $f_{i}$. Otherwise, let $t^{\prime}$ be the earliest time step in
$L$ after which all lower messages in $f_{i}$ are in $v_{i}$; schedule a flush
in $L$ from $v_{i}$ to $v_{i}^{\prime}$ in the earliest available time step
after $t^{\prime}$, consisting of all lower messages in $f_{i}$. $L$ can be
created in $O(n\log n)$ time.

We define $L$ this way to ensure the following lemma bounding the time step
when each lower flush is scheduled.

######  Lemma 5.

Any message $m$ that is a member of a packed set $C$ with starting time $\tau$
reaches its target leaf in $L$ by time step $27\tau+h+c(S,m)$.

###### Proof.

Consider the flushes of $m$ in $L$. We say that $m$ is _delayed_ each time a
flush containing $m$ cannot be scheduled in the desired time slot in $L$. If
$m$ is not delayed, it completes at time step $27\tau+(h-h(v))$ in $L$. If all
flushes containing $m$ are delayed a total of $\delta$ time steps, $m$
completes at time $27\tau+(h-h(v))+\delta$.

Each time $m$ is delayed, a flush $f$ (in $S$) containing $m$ cannot be
scheduled due to $P$ other flushes in $L$ already being scheduled at some time
step $t$. Each of those flushes in $L$ must occur before, or at the same time
as, $f$ in $S$; thus each flush must occur at or before $c(S,m)$ in $S$. There
can be at most $Pc(S,m)$ such flushes. Thus, $\delta\leq c(S,m)$. ∎

Now, we want to combine $U$ and $L$ to obtain a valid schedule. To begin we
observe the following: combining the flushes from both schedules gives a valid
sequence of flushes for any individual message.

######  Observation 6.

For any message $m$, create a schedule $S_{m}$, such that if $m$ is flushed
from $v_{1}$ to $v_{2}$ in $U$ or $L$, then $m$ is flushed from $v_{1}$ to
$v_{2}$ in $S_{m}$. Then in $S_{m}$, if $m$ is flushed from a node $v$ at time
step $t$ then $m$ is flushed to $v$ at some time step $t^{\prime}<t$;
furthermore, $m$ is flushed to its target leaf $\ell_{m}$ by the end of
$S_{m}$.

###### Proof.

Let $C$ be the packed set of $m$ and $v$ be its packed parent; let $\tau$ be
the starting time of $C$. Then all messages in $C$ are flushed to $v$ by time
step $13\tau$ in $U$ by Lemma 4. Each message in $C$ is flushed out of $v$ at
time step $27\tau$ or later by definition.

Since $S$ is overfilling, there is a sequence of flushes containing $m$ from
$v$ to its target leaf; each flush in $S$ from node $v_{1}$ to $v_{2}$ occurs
at a time step when $m$ is in $v_{1}$. Since we add flushes to $L$ in order of
time steps in $S$ (waiting for any messages in the flush to arrive if
necessary), all flushes in $S$ are in $L$, and they are in the same order they
were in $S$, and we do not flush a lower message out of a out of a node until
it is flushed into the node. ∎

However, there remains an issue which motivates us to alter $U$. As-is, when a
packed set arrives at an internal packed node $v$ in $U$, it may be that there
are still messages in the node that were not flushed out of $v$; thus, there
may not be room for these new messages. (This is because a flush in $L$ may be
delayed far past the corresponding flush in $S$.)

To resolve this, we modify $U$ to create a schedule $U_{r}$ that ensures there
is enough room in each packed parent for an arriving packed set. In short, to
create $U_{r}$, we add additional flushes to $U$ to guarantee that each node
flushed to has space.

Specifically, for each packed set $C_{i}$ with an internal packed parent, let
$\hat{\tau_{i}}$ be the time step that $C_{i}$ arrives at its packed node
$v_{i}$. Perform the following for all packed sets, in order by
$\hat{\tau_{i}}$. Immediately before $\hat{\tau_{i}}$, insert all flushes in
$L$ from $v_{i}$ that are performed after time step $\hat{\tau_{i}}-h$. (We
subtract $h$ because, in short, we will delay flushes in $L$ by up to $h$ time
steps when constructing $\hat{S}$ below.) These flushes can all be performed
in parallel; thus, if we insert $x$ flushes, all later flushes in $U$ are
delayed by $\lceil x/P\rceil$ time steps. We can create $U_{r}$ in $O(n\log
n)$ time.

Let $U_{r}$ be the schedule obtained after this modification. By construction,
every time a packed set arrives at its packed parent $v$ in $U_{r}$, $v$
contains no other messages from a packed set of $v$. Furthermore, $U_{r}$
satisfies the following lemma.

######  Lemma 7.

For any packed set $C$ with starting time $\tau$, all messages in $C$ arrive
at their packed parent $v$ in $U_{r}$ at time step $\hat{\tau}$ satisfying
$\hat{\tau}\leq 27\tau+h$.

###### Proof.

For any time step $t$, let $x_{t}$ be the number of flushes inserted
immediately before $t$ into $U$ to obtain $U_{r}$—i.e. $x_{t}$ is the sum,
over all packed parents $v_{\ell}$ with packed sets arriving at $t$, of the
number of flushes out of $v_{\ell}$ in $L$ that occur after $t-h$. By
definition, if a flush occurs at time step $t^{\prime}$ in $U$, it occurs at
time step $t^{\prime}+\sum_{t\leq t^{\prime}}\lceil x_{t}/P\rceil$ in $U_{r}$.
Let $t_{U}$ be the time step when all messages in $C$ arrive at $v$ in $U$;
thus we want to show that $t_{U}+\sum_{t\leq t_{U}}\lceil x_{t}/P\rceil\leq
27\tau$.

Let $C_{i},C_{i+1}\in\mathcal{C}(v^{\prime})$ be two packed sets of some node
$v^{\prime}$; let $\tau_{i+1}$ be the starting time of $C_{i+1}$. By
definition, all flushes of messages in $C_{i}$ out of $v$ occur before
$\tau_{i+1}$ in $S$. Then, since the time step at which all packed sets in $U$
arrive at their packed parent is in order by starting time, $\lceil\sum_{t\leq
t_{U}}x_{t}/P\rceil\leq\tau+h$.

By Lemma 4, $t_{U}\leq 13\tau$. Then we can upper bound when $C$ arrives in
$U_{r}$.

$\displaystyle t_{U}+\sum_{t\leq t_{U}}\lceil x_{t}/P\rceil$
$\displaystyle\leq t_{U}+\left\lceil\sum_{t\leq t_{U}}x_{t}/P+1\right\rceil$
$\displaystyle\leq t_{U}+(\tau+h+t_{U})$ $\displaystyle\leq 27\tau+h.\qed$

#### Defining $\hat{S}$

Divide $U_{r}$ and $L$ into _epochs_ of $h$ time steps; we use epoch
$i\in\\{0,1,\ldots\\}$ to refer to time steps $\\{hi+1,\ldots,hi+h\\}$. Each
flush in epoch $i$ of $U_{r}$ or $L$ will occur at some time step in
$\\{3hi+1,\ldots,3hi+4h\\}$ of $\hat{S}$.

Iterate through the epochs starting at $0$. Consider a sequence of flushes
from the root to some packed node $v$ in $U_{r}$ where the first flush occurs
at time step $hi+t$ in $U_{r}$ for $1\leq t\leq h$; perform these flushes
starting at time step $3hi+h+t$ in $\hat{S}$. These flushes are all performed
by time step $3hi+2h$.

For any flush $f$ from $v_{1}$ to $v_{2}$ in $L$ at time step $hi+t$ in $L$,
obtain $M_{f}^{\prime}$ by removing all messages in $M_{f}$ that are flushed
from $v_{1}$ to $v_{2}$ in $U_{r}$. Then schedule a flush in $\hat{S}$ of all
messages in $M_{f}^{\prime}$ at time step $3hi+2h+t$. These flushes all
complete by time step $3hi+3h$.

Creating $\hat{S}$ from $U_{r}$ and $L$ requires $O(n)$ time.

#### Analysis of $\hat{S}$

From the above, $\hat{S}$ can be created (including the time to create $U_{r}$
and $L$) in $O(n\log n)$ total time. We are left to prove that $\hat{S}$ is a
valid schedule, and that its cost is bounded by the cost of $S$.

###### Proof of Lemma 1.

To show that $\hat{S}$ is valid, we must first show that each flush only
consists of messages that are already in the correct node, and that all
messages are flushed to their leaf.

Consider the flushes containing a message $m$. By construction, all flushes
containing $m$ in $U_{r}$ occur in the same order in $\hat{S}$ and all flushes
containing $m$ in $L$ occur in the same order in $\hat{S}$. Let $i$ be the
epoch in which $m$ is flushed to its packed parent. By Observation 6, there is
a flush containing $m$ for each edge from the root to its target leaf, all
flushes containing $m$ in $U$ occur in epoch $i$ or earlier, and all flushes
containing $m$ in $L$ occur in epoch $i$ or later. All flushes in $L$ in epoch
$i$ occur later than all flushes in $U_{r}$ in epoch $i$. Therefore, all
flushes contain messages already in the correct node, and all messages are
flushed to their leaf.

In each of $U_{r}$ and $L$, there are at most $P$ flushes in any time step,
and each flush contains $B$ messages. Each time step of $\hat{S}$ contains
messages from flushes in from exactly one of $U_{r}$ or $L$, so $\hat{S}$ also
has at most $P$ flushes in each time step, and each flush contains at most $B$
messages.

Thus, $\hat{S}$ is overfilling; we must further show that it is valid.
Consider a node $v$ at time step $t$. There can be at most $B/2$ messages with
a packed parent that is an ancestor $v^{\prime}$ of $v$ with $v^{\prime}\neq
v$, because every descendant of a packed parent contains at most $B/2$
messages from that packed parent from the definition of the packed sets. If a
message $m$ has a packed parent $v^{\prime}$ that is a descendant of $v$ with
$v^{\prime}\neq v$, then $m$ will be flushed out of $v$ at time step $t+1$ by
definition of $U$, $U_{r}$, and $\hat{S}$—in particular, all flushes of
messages to their packed parent in $\hat{S}$ are consecutive. (Thus, $v$ may
overflow, but still satisfies the space requirement.) Finally, if the packed
parent of $m$ is $v$, let $C_{i}$ be the packed set of $m$. Let $t^{\prime}$
be the time when $m$ arrives at $v$ in $U_{r}$. By definition of $U_{r}$, any
message not in $C_{i}$ is either (1) flushed out of $v$ in $U_{r}$ before
$t^{\prime}$, in which case it is flushed out before $t$ in $\hat{S}$, or (2)
flushed out of $v$ in $L$ by time step $t^{\prime}-h$; this is an earlier
epoch than $t^{\prime}$, so again this flush occurs before $t$. Putting the
above together, the messages in $v$ at time step $t$ that are still in $v$ at
time step $t+1$ consist of at most $B/2$ messages whose packed parent is $v$,
and at most $B/2$ messages whose packed parent is an ancestor of $v$, for $B$
messages total.

Finally, we show the cost. If a message $m$ is completed at time step $c(m,S)$
in $S$, then by Lemma 5 it is completed at time step $27\tau+c(m,S)+h$ in $L$
or $U_{r}$ ($m$ is completed in $U_{r}$ if its packed parent is a leaf);
therefore it is completed by time step $3(27\tau+c(m,S)+h)+3h$ in $\hat{S}$.
For all $m$, $c(m,S)\geq h$. Thus we can bound

$c(\hat{S})\leq\sum_{m\in M}81\tau_{m}+7c(S,m).$

Replacing with Lemma 3,

$c(\hat{S})\leq 162c(S)+\sum_{m\in M}7c(S,m)\leq 169c(S).$

Setting $c_{1}=169$ we are done. ∎

###  3.2 Reduction

Now we are ready to show how to reduce WORMS—in particular, the problem of
finding an overfilling schedule for WORMS—to $P|outtree,\allowbreak
p_{j}=1|\sum wC$.

To begin, we describe the reduction. For any WORMS instance $(T,M,P,B)$, we
describe how to create an instance of $P|outtree,\allowbreak p_{j}=1|\sum wC$
which we denote $\mathcal{T}(T,M,P,B)$. First, we define the _oblivious packed
sets_ —these serve a function similar to the packed sets in Section 3.1;
however, the packed sets are defined using a schedule $S$, whereas the
oblivious packed sets depend only on $(T,M,P,B)$. To create the oblivious
packed sets, for each internal packed node $v\in T$, we partition the children
of $v$ arbitrarily into sets such that the total number of descendants of all
children in a set is between $B/6$ and $B/2$. (This can be done using the same
method as the packed sets, but we no longer order the children of $v$ by the
time step they are flushed in some schedule $S$.) If $v$ does not have
children, we partition the messages arbitrarily into sets of size between
$B/6$ and $B/2$.

For each oblivious packed set $C$ with packed parent $v\in V_{P}$, we create a
chain of $h(v)$ tasks with weight $0$ in $\mathcal{T}(T,M,P,B)$; each has the
previous as a precedence constraint. The first task in the chain has no
precedence constraint. Let888We use $j$ to denote tasks since $t$ denotes
time. $j^{\prime}$ be the last task in the chain.

If $v$ is an internal node, we recursively copy the subtree rooted at $v$ in
$T$ to $\mathcal{T}(T,M,P,B)$. Specifically, if $c$ is the number of children
of $v$ in $T$, create $c$ tasks with weight $0$ and $v$ as a precedence
constraint (one for each outgoing edge of $v$ in $T$), then do the same
recursively for each such child. When $v$ is a leaf $\ell\in T$, we create a
task $j_{v}$ in $\mathcal{T}(T,M,P,B)$ representing the in-edge of $v$; set
the weight of this task to be the number of messages that have $v$ as their
target leaf.

for tree=inner sep=0pt, circle, minimum size=2ex, draw, s sep=1ex, edge=-¿ ,
[,name=l1,phantom [,color=black,draw [,color=black,draw [,color=black,draw
[,color=black,draw [,label=below:$30$,color=red,fill] ] ] ] ]
[,color=black,draw [,color=black,draw [,color=black,draw [,color=black,draw
[,label=below:$10$,color=red,fill] ] ] ] ] [,color=black,draw
[,color=nicepurple,fill [,color=black,draw [,color=black,draw
[,label=below:$3$,color=black,draw] ] ] ] ] [,color=black,draw
[,color=black,draw [,color=black,draw [,color=black,draw
[,label=below:$5$,color=niceblue,fill ] [,label=below:$6$,color=niceblue,fill
] ] ] ] ] [,color=black,draw [,color=black,draw [,color=black,draw
[,color=niceorange,fill [,label=below:$6$,color=black,draw ]
[,label=below:$3$,color=black,draw ] ] [,color=niceorange,fill
[,label=below:$9$,color=black,draw ] ] ] ] ] [,color=black,draw
[,color=black,draw [,color=black,draw [,color=niceyellow,fill
[,label=below:$9$,color=black,draw ] ] [,color=niceyellow,fill
[,label=below:$4$,color=black,draw ] [,label=below:$5$,color=black,draw ] ] ]
] ] [,color=black,draw [,color=black,draw [,color=black,draw
[,color=black,draw [,label=below:$6$,color=nicegreen,fill ]
[,label=below:$8$,color=nicegreen,fill ] ] ] ] ] [,color=black,draw
[,color=black,draw [,color=purple,fill [,color=black,draw
[,label=below:$5$,color=black,draw ] [,label=below:$3$,color=black,draw ] ]
[,color=black,draw [,label=below:$1$,color=black,draw ] ] ]
[,color=purple,fill [,color=black,draw [,label=below:$3$,color=black,draw]
[,label=below:$3$,color=black,draw] ] ] ] ] ]

Figure 3: This figure shows the precedence constraints of tasks in
$\mathcal{T}(T,M,P,B)$ for the WORMS instance in Figure 2; the coloring of
each packed set matches between the figures, except the red packed sets which
had a leaf packed parent. All internal tasks have weight $0$; the leaves are
labelled with their weight. If all descendant leaves of a task have weight $0$
the task is omitted.

If $v$ is a leaf, set the weight of $j^{\prime}$ to be the number of messages
in $C$. In Figure 3 we show an example of $\mathcal{T}(T,M,P,B)$, where
$(T,M,P,B)$ is as given in Figure 2.

######  Lemma 8.

Given a solution $\sigma$ to a $P|outtree,\allowbreak p_{j}=1|\sum wC$
instance $\mathcal{T}(T,M,P,B)$, there exists an overfilling schedule
$S^{\prime}$ for $(T,M,P,B)$ with $c(S^{\prime})=cost(\sigma)$.

###### Proof.

Each task $j$ in $\mathcal{T}(T,M,P,B)$ was created for a packed set $C$ and
an edge $e\in T$. When $j$ is processed in $\sigma$, we flush all messages in
$C$ across $e$ in $S$. The precedence constraints guarantee that the flushes
are valid. We have $c(S^{\prime})=cost(\sigma)$ because each time a task with
nonzero weight completes in $\sigma$, all messages that contribute to the
weight of that task reach their leaf in $S^{\prime}$. ∎

######  Lemma 9.

Given an overfilling solution $S$ to a WORMS instance $(T,M,P,B)$, there is a
solution $\sigma$ to $\mathcal{T}(T,M,P,B)$ such that $cost(\sigma)\leq
c_{1}\cdot c(S)$, with $c_{1}$ as defined in Lemma 1.

###### Proof.

Let $\hat{S}$ be as defined in Section 3.1 using $S$ and the oblivious packed
sets of $(T,M,P,B)$. Note that all flushes in $\hat{S}$ are of messages from a
single oblivious packed set. For $U$ this is by definition; for $L$ this is
because all messages whose target leaf is a descendant of a given child of
their packed parent are a part of the same oblivious packed set; for $U_{r}$
and $\hat{S}$ this follows from $L$ and $U$. Thus, all flushes in $\hat{S}$
correspond to a task in $\mathcal{T}(T,M,P,B)$. The lemma follows from Lemma
1. ∎

Together, Lemmas 8 and 9 (with Lemma 1) show that solving
$\mathcal{T}(T,M,P,B)$ is equivalent, up to constant factors, to solving
$(T,M,P,B)$.

##  4 Solving $P|outtree,\allowbreak p_{j}=1|\sum wC$

In this section we discuss how to solve any instance $\mathcal{T}$ of
$P|outtree,\allowbreak p_{j}=1|\sum wC$. We will use this to give an
$O(1)$-approximate solution for $\mathcal{T}\leftarrow\mathcal{T}(T,M,P,B)$ to
solve a WORMS instance $(T,M,P,B)$.

###  4.1 Single-Machine Case

For the single-processor case (i.e. $P=1$) we are done: an optimal algorithm
for $1|outtree|\sum wC$, Horn’s algorithm, was given in [19].

We give an exposition of Horn’s algorithm here. While the algorithm is already
known, we will modify Horn’s algorithm to create a parallel algorithm below.

Let $\mathcal{T}$ be a set of tasks with tree precedence constraints.

For any subtree999A subtree $\mathcal{T}^{\prime}$ of $\mathcal{T}$ must be a
tree (as opposed to a forest—$\mathcal{T}^{\prime}$ can have only one root
node), and must be contiguous—for any non-root $j\in\mathcal{T}^{\prime}$, the
parent of $j$ must also be in $\mathcal{T}^{\prime}$. $\mathcal{T}^{\prime}$,
its _weight_ , denoted $w(\mathcal{T}^{\prime})$, is the total weight of all
tasks in $\mathcal{T}^{\prime}$; the _size_ $s(\mathcal{T}^{\prime})$ is the
number of tasks in $\mathcal{T}^{\prime}$. The _density_ of
$\mathcal{T}^{\prime}$ is $w(\mathcal{T}^{\prime})/s(\mathcal{T}^{\prime})$.

For any task $j\in\mathcal{T}$, let $F_{j}$ be the highest density subtree of
$\mathcal{T}$ rooted at $j$. We define the _task density_ of $j$ to be the
density of $F_{j}$. Horn gives a algorithm for calculating the task density
for all tasks $j$ [19].

Horn’s algorithm can be defined as follows on an instance $\mathcal{T}$.
First, for each task $j\in\mathcal{T}$, calculate the task density of $j$.
Then, add all tasks in $\mathcal{T}$ with no precedence constraints to a
priority queue $PQ$, where the priority of a task is its task density. At each
time step, remove the highest-priority task $j^{\prime}$ from $PQ$ (breaking
ties arbitrarily) and process $j^{\prime}$. Then, add all children of
$j^{\prime}$ to $PQ$.

######  Lemma 10 ([19]).

Horn’s algorithm is an optimal schedule for any instance $\mathcal{T}$ of
$P|outtree,\allowbreak p_{j}=1|\sum wC$ with $P=1$.

The running time of Horn’s algorithm is not given in [19]. However, a priority
queue implementation allows both the calculation of all task densities, and
the decision of when to run each task, in $O(|\mathcal{T}|\log|\mathcal{T}|)$
time.

###  4.2 Multiple Machines

While Horn’s algorithm is optimal when $P=1$, in general
$P|outtree,\allowbreak p_{j}=1|\sum wC$ is known to be strongly NP-hard [42,
27]. The best-known approximation algorithm for $P|outtree,\allowbreak
p_{j}=1|\sum wC$ is the $(1+\sqrt{2})$-approximation algorithm of [28] (i.e. a
$2.415$-approximation).

However, there are downsides to using known algorithms as a black box to solve
our problem. The known approximation algorithms for $P|outtree,\allowbreak
p_{j}=1|\sum wC$ are LP-rounding-based algorithms for $P|prec|\sum wC$. That
is to say, they work for general, not just tree, precedence constraints; for
this reason, they are complicated, and do not give structural insight into
designing effective algorithms for the tree case specifically. Here, we give a
$4$-approximation algorithm that is based on Horn’s algorithm: we choose what
task to process (i.e. what to flush) based on the density of available tasks.

To begin, we define an intermediate algorithm. We define an algorithm
_Parallel Heaviest Tree First (PHTF)_ , which generalizes Horn’s algorithm to
multiple processors. As before, we calculate the task density of all tasks in
$\mathcal{T}$, and add all tasks without a precedence constraint to a priority
queue $PQ$. At each time step, we remove the $P$ highest-density tasks from
$PQ$ (or all tasks from $PQ$ if fewer than $P$ are available) and process all
of them; then, we add the children of any processed tasks to $PQ$. Our goal is
to use PHTF as an intermediate algorithm to give a $4$-approximation algorithm
for $P|outtree,\allowbreak p_{j}=1|\sum wC$.

As a first step towards that goal, we show that PHTF is optimal under a
slightly relaxed cost function. The idea of this cost function is that it
gives a fractional notion of completion time.

We define the _Horn’s trees_ for a given instance $\mathcal{T}$. In short, the
Horn’s trees partition all tasks into dense subtrees processed by Horn’s
algorithm. We formally define them recursively: for an instance
$\mathcal{T}^{\prime}$, find a task $j$ with no parent in
$\mathcal{T}^{\prime}$; then $F_{j}$ is a Horn’s tree. Remove all tasks in
$F_{j}$ from $\mathcal{T}^{\prime}$ and recurse. This continues until
$\mathcal{T}^{\prime}$ has no remaining tasks.

Fix an instance of $P|outtree,\allowbreak p_{j}=1|\sum wC$ and denote it
$\mathcal{T}$; we denote the set of Horn’s trees for $\mathcal{T}$ as
$\mathcal{H}$. By definition, every task in $\mathcal{T}$ is in exactly one
Horn’s tree $T\in\mathcal{H}$.

We repeatedly use the following observation about Horn’s trees in our proof.

######  Observation 11.

If $T$ and $T^{\prime}$ are two subtrees of $\mathcal{T}$, and both $T$ and
$T^{\prime}$ have a common root $r$, then if $T^{\prime}$ is denser than $T$,
$T$ cannot be a Horn’s tree.

###### Proof.

If $T$ is a Horn’s tree, then $T=F_{r}$ by definition. But this is not
possible since the density of $F_{r}$ must be at least the density of
$T^{\prime}$. ∎

For any schedule $\sigma$ for $\mathcal{T}$, any Horn’s tree
$T_{i}\in\mathcal{H}$, and any time step $t$, let $U_{i}^{t}(\sigma)$ be the
subset of tasks in $T_{i}$ that are unfinished in $\sigma$ at time step $t$.
Observe that we can denote the weighted completion time of $\sigma$ as

$cost(\sigma)=\sum_{t}\sum_{T_{i}\in\mathcal{H}}\left(\sum_{j\in
U_{i}^{t}(\sigma)}w(j)\right).$

Then we define $cost^{f}(\sigma)$ for any schedule $\sigma$ as

$cost^{f}{}(\sigma)=\sum_{t}\sum_{T_{i}\in\mathcal{H}}\left(\frac{|U_{i}^{t}(\sigma)|}{s(T_{i})}\sum_{j\in
T_{i}}w(j)\right)$

In other words, in this notion of cost, the algorithm gets credit for the
portion of each tree it completes, where the trees are defined using Horn’s
algorithm. We can equivalently write
$cost^{f}(\sigma)=\sum_{t}\sum_{T_{i}\in\mathcal{H}}|U_{i}^{t}(\sigma)|w(T_{i})/s(T_{i})$.

######  Lemma 12.

PHTF is optimal for $cost^{f}$.

###### Proof.

Assume by contradiction that the optimal schedule $\sigma$ under $cost^{f}$
satisfies $cost^{f}(\sigma)<cost^{f}(\sigma_{H})$.

Since $\sigma\neq\sigma_{H}$, there must be some first time step $t$ where
there is a task $j_{i}$ from the Horn’s tree $T_{i}$ that is one of the $P$
densest trees in the priority queue, but $\sigma$ instead schedules a task
from a tree that is strictly less dense than $T_{i}$. Let $t_{\ell}>t$ be the
time step when $j_{i}$ is scheduled in $\sigma$.

Let $t^{\prime}$ be the _last_ time step before $t_{\ell}$ such that a task
$j^{\prime}$ is processed at $t^{\prime}$ where $j^{\prime}$ is from a Horn’s
tree $T^{\prime}$ that is strictly less dense than $T_{i}$. There must be such
a $t^{\prime}\geq t$ because $t^{\prime}=t$ always satisfies the requirement.

We obtain a new schedule $\sigma^{\prime}$ by swapping $j_{i}$ and
$j^{\prime}$. To achieve a contradiction, we must prove that $\sigma^{\prime}$
is a valid schedule (the tasks it performs satisfy the precedence
constraints), and that $cost^{f}(\sigma^{\prime})<cost^{f}(\sigma)$.

First, we show that $\sigma^{\prime}$ is valid. By definition, any precedence
constraint for $j_{i}$ is satisfied at $t$, and thus is satisfied at
$t^{\prime}$. Similarly, if any precedence constraint is satisfied for
$j^{\prime}$ at $t^{\prime}$, it satisfied at $t_{\ell}>t$. Further, all tasks
processed at time steps later than $t_{\ell}$ or earlier than $t^{\prime}$
obviously remain valid. Now, we must show that all tasks other than
$j^{\prime}$ and $j_{i}$ executed between $t^{\prime}$ and $t_{\ell}$ in
$\sigma^{\prime}$ are valid. Consider a task $j^{\prime\prime}$ processed
between $t^{\prime}$ and $t_{\ell}$ such that $j^{\prime\prime}$ is a
descendant of $j^{\prime}$. Since $j^{\prime\prime}$ is processed between
$t^{\prime}$ and $t_{\ell}$, by definition, $j^{\prime\prime}$ must be from
some Horn’s tree $T^{\prime\prime}$ that is more dense than $T_{i}$, and thus
more dense than $T^{\prime}$. However, this is not possible by Observation 11,
because then $T^{\prime}\cup T^{\prime\prime}$ would be denser than
$T^{\prime}$ and share a common root.

Finally, we must show that $cost^{f}(\sigma^{\prime})<cost^{f}(\sigma)$. Let
$\delta_{i}$ and $\delta^{\prime}$ be the density of $T_{i}$ and $T^{\prime}$
respectively. We have that
$cost^{f}(\sigma)-cost^{f}(\sigma^{\prime})=(t_{\ell}-t)(\delta_{i}-\delta^{\prime}).$
But this is positive since $t_{\ell}>t$ and $\delta_{i}>\delta^{\prime}$.
Thus, $\sigma^{\prime}$ has lower cost than $\sigma$, giving a contradiction.
∎

It’s not immediately clear how to compare $cost{}$ and $cost^{f}{}$. On the
one hand, for a tree $T$ that is a path of tasks of increasing weight,
$cost^{f}{}$ always gives a smaller cost than $cost{}$. On the other hand, for
a non-path $T$, completing a particularly heavy node immediately decreases
$cost{}$ by a large amount, while $cost^{f}{}$ only reduces proportionally to
how much of $T$ has been flushed—it is easy to come up with trees (that are
not Horn’s trees) where $cost$ is far less than $cost^{f}{}$. Perhaps
surprisingly, we show in the next lemma that despite this tradeoff,
$cost^{f}{}$ is always smaller. The main proof idea is to use the definition
of the Horn’s trees: if completing a portion of $T_{i}\in\mathcal{H}$ has
smaller cost under $cost{}$ than under $cost^{f}{}$, then $T_{i}$ can be split
into two trees $T^{\prime}$ and $T^{\prime\prime}$ where $T^{\prime}$ shares a
root with $T_{i}$, but is denser than $T_{i}$, violating Observation 11.

######  Lemma 13.

For any schedule $\sigma$, $cost^{f}(\sigma)\leq cost(\sigma)$.

###### Proof.

Consider some Horn’s tree $T_{i}$ and some time step $t$ for the remainder of
the proof. Let $T^{f}_{i}$ be the tasks in $T_{i}$ that are completed by $t$,
and $T^{u}_{i}$ be the unfinished tasks in $T_{i}$. Then it is sufficient to
show that for any $T_{i}$ and $t$, for all $\sigma$,

$w(T_{i})\frac{s(T^{u}_{i})}{s(T_{i})}\leq w(T^{u}_{i}).$ (1)

Since $\sigma$ is a schedule, $T^{f}_{i}$ is a subtree of $T_{i}$ with the
same root as $T_{i}$. By Observation 11, $w(T^{f}_{i})/s(T^{f}_{i})\leq
w(T_{i})/s(T_{i})$. We must have $s(T^{f}_{i})+s(T^{u}_{i})=s(T_{i})$ and
$w(T^{f}_{i})+w(T^{u}_{i})=w(T_{i})$, so we can write

$\frac{w(T_{i})-w(T^{u}_{i})}{s(T_{i})-s(T^{u}_{i})}\leq\frac{w(T_{i})}{s(T_{i})}.$

For any $x,y,a,b>0$, if $(x-a)/(y-b)\leq x/y$ then $x/y\leq a/b$. Thus, we
have $w(T_{i})/s(T_{i})\leq w(T^{u}_{i})/s(T^{u}_{i})$. Rearranging we obtain
Equation 1. ∎

#### A $4$-Approximation Algorithm

We are now ready to define our algorithm, Modified Parallel Heaviest Tree
First (MPHTF). At each time step $t$, let $\mathcal{T}_{t}$ be the set of at
most $P$ tasks flushed by PHTF. For every task $j\in\mathcal{T}_{t}$, let
$T_{j}$ be the Horn’s tree containing $j$. Then MPHTF performs a task from
$T_{j}$ (with satisfied precedence constraints) at time step $t$, and performs
a task (with satisfied precedence constraints) from $T_{j}$ at time step
$t+1$. If all tasks in $T_{j}$ are completed MPHTF does nothing.

######  Lemma 14.

If $\sigma_{M}$ is the solution given by MPHTF on an instance $\mathcal{T}$ of
$P|outtree,\allowbreak p_{j}=1|\sum wC$, then for any other schedule
$\sigma^{\prime}$ for $\mathcal{T}$, we have $cost(\sigma_{M})\leq
4cost(\sigma^{\prime})$.

###### Proof.

Let $\sigma_{H}$ be the schedule given by PHTF on $\mathcal{T}$. By Lemma 10
we have that $cost^{f}(\sigma_{H})\leq cost^{f}(\sigma^{\prime})$.
Furthermore, from Lemma 13, $cost^{f}(\sigma^{\prime})\leq
cost(\sigma^{\prime})$. Therefore, we need only to show $cost(\sigma_{M})\leq
4cost^{f}(\sigma_{H})$ to prove the lemma.

At time step $t$, let $\mathcal{H}_{t}$ be the set of Horn’s trees which have
had at most half their edges flushed by PHTF. Then

$\displaystyle cost^{f}{}(\sigma_{H})$
$\displaystyle=\sum_{t}\sum_{T_{i}\in\mathcal{H}}\left(\frac{|U_{i}^{t}(\sigma_{H})|}{s(T_{i})}w(T_{i})\right)$
$\displaystyle=\sum_{t}\sum_{T_{i}\in\mathcal{H}_{t}}\left(\frac{|U_{i}^{t}(\sigma_{H})|}{s(T_{i})}w(T_{i})\right)$
$\displaystyle\qquad+\sum_{t}\sum_{T_{i}\in\mathcal{H}\setminus\mathcal{H}_{t}}\left(\frac{|U_{i}^{t}(\sigma_{H})|}{s(T_{i})}w(T_{i})\right)$
$\displaystyle\geq\sum_{t}\sum_{T_{i}\in\mathcal{H}_{t}}\left(\frac{1}{2}w(T_{i})\right)+\sum_{t}\sum_{T_{i}\in\mathcal{H}\setminus\mathcal{H}_{t}}0$

Let $t_{h}(i)$ be the first time step when at least half the tasks in Horn’s
tree $T_{i}$ completed in PHTF. Replacing in the above,
$cost^{f}(\sigma_{H})\geq\sum_{T_{i}\in\mathcal{H}_{t}}t_{h}(i)w(T_{i})/2$.

Since MPHTF flushes any Horn’s tree twice when PHTF flushes it once, for any
time step $t^{\prime}$, all tasks in Horn’s trees
$T_{i}\in\mathcal{H}\setminus\mathcal{H}_{t}$ are finished by $2t^{\prime}$ in
$\sigma_{M}$. Therefore,

$\displaystyle cost(\sigma_{M})$
$\displaystyle=\sum_{t}\sum_{T_{i}\in\mathcal{H}}\sum_{j\in
U^{t}_{i}(\sigma)}w(j)$
$\displaystyle=\sum_{T_{i}\in\mathcal{H}}\sum_{t}\sum_{j\in
U^{t}_{i}(\sigma)}w(j)$
$\displaystyle=\sum_{T_{i}\in\mathcal{H}}\sum_{t=1}^{2t_{h}(i)}\sum_{j\in
U^{t}_{i}(\sigma)}w(j)$ $\displaystyle\leq 2\sum_{T_{i}\in
H_{t^{\prime}}}2t_{h}(i)w(T_{i}).$

Putting the above together, $cost(\sigma_{M})\leq 4cost^{f}(\sigma_{H})$. ∎

We immediately obtain that MPHTF is a $4$-approximation algorithm.

###  4.3 Putting it All Together

We are ready to show how to give, for any WORMS instance $(T,M,P,B)$, a
sequence of flushes that $O(1)$-approximates the optimal sequence of flushes.

To begin, we use $(T,M,P,B)$ to calculate $\mathcal{T}(T,M,P,B)$. By Lemma 9
the best solution to $\mathcal{T}(T,M,P,B)$ is at most $c_{1}$ greater than
the best solution to $(T,M,P,B)$. We use MPHTF to $4$-approximate the best
solution to $\mathcal{T}(T,M,P,B)$; call this solution $\sigma_{M}$. We then
use Lemma 8 to convert $\sigma_{M}$ to an overfilling sequence of flushes $S$,
where $S$ has the same cost as $\sigma_{M}$; at most $4c_{1}$ of optimal.
Finally, we use Lemma 1 to convert $S$ to $\hat{S}$, a valid sequence of
flushes for $(T,M,P,B)$, where $c(\hat{S})$ is at most $4c_{1}^{2}$ the
optimal cost for $(T,M,P,B)$. Thus we achieve a schedule $\hat{S}$ that
$O(1)$-approximates the optimal schedule for $(T,M,P,B)$. Each of these
operations requires $O(n\log n)$ time, so $\hat{S}$ can be obtained in
$O(n\log n)$ total time.

###  4.4 NP-hardness

We show that WORMS is NP hard even on a single processor. This justifies that
our results give an approximation of the optimal solution. The proof has been
moved to the appendix for space.

######  Lemma 15.

WORMS is NP hard even if $P=1$.

###### Proof.

We reduce from $3$-partition. In $3$-partition, we are given a set of
$3n^{\prime}$ integers $I$, where $\sum_{i\in I}i=n^{\prime}K$ for some $K$,
and all $i\in I$ are between $K/4$ and $K/2$. $3$-partition remains strongly
NP-hard even if all $i\in I$ are between $K/4$ and $K/2$ and the integers in
$I$ are given in unary.101010This is important because our instance will have
$|M|$ polynomial in $\sum_{i\in I}i$. The problem is to decide whether there
exists a partition of $I$ into $n^{\prime}$ sets $\mathcal{P}$, such that each
set $\hat{P}\in\mathcal{P}$ has $\sum_{i\in\hat{P}}i=K$. (Since all $i$ are
between $K/4$ and $K/2$, there must be exactly $3$ items in every set
$\hat{P}\in\mathcal{P}$.)

We proceed in two parts. First, we give an instance of WORMS
$(T_{1},M_{1},1,B)$ such that $I$ has a $3$-partition if and only if there is
a schedule $S_{1}$ such that: (1) the _maximum_ completion time of any message
in $(T_{1},M_{1},1,B)$ in $S_{1}$ is at most $4n^{\prime}$ and (2) the cost of
$S_{1}$ on $(T_{1},M_{1},1,B)$ is at most $C_{1}$. Then, we give a WORMS
instance $(T,M,1,B)$ that has a schedule of cost at most $C_{2}$ if and only
if $(T_{1},M_{1},1,B)$ has such a schedule $S_{1}$.

First, let us define $T_{1}$, $M_{1}$, $B$ and $C_{1}$. Let $B=3X+K$
where111111$X$ is a large number added to each integer in $I$—intuitively,
adding a large number to each integer means that the integers are
proportionately much closer in value; thus, small perturbations in a schedule
in our reduction have a minimal impact on cost. $X=12n^{\prime 2}K$. To begin,
let $T_{1}$ consist of a root node $r$ and a child $x$ of $r$. Then, create
$3n^{\prime}$ leaves, all of which are children of $x$: in particular, for
each $i\in I$, create a leaf $\ell_{i}$ in $T_{1}$, and create $X+i$ messages
in $M_{1}$ that have $\ell_{i}$ as their target leaf. We call these $X+i$
messages the _representative messages_ of $i$. Note that therefore
$|M_{1}|=n^{\prime}K+3n^{\prime}X$. Finally, we define:

$C_{1}=\sum_{i=1}^{n^{\prime}}\left(4(i-1)(3X+K)+X(2+3+4)+4K\right).$

We show that there is a schedule $S_{1}$ for $(T_{1},M_{1},1,B)$ with maximum
completion time $4n^{\prime}$ and cost at most $C_{1}$ if and only if $I$ has
a $3$-partition.

If $I$ has a $3$-partition $\mathcal{P}$, then for each
$\hat{P}\in\mathcal{P}$, we can flush all representative messages of any
$i\in\hat{P}$ to $x$; then, for the three $i\in\hat{P}$, we flush the
representative messages of each to their leaf. The messages fit in $x$ because
$\sum_{i\in\hat{P}}i=K$, so $3X+K$ messages are flushed. This requires $4$
flushes; since $|\mathcal{P}|=n^{\prime}$ and $P=1$, the maximum completion
time of any message is $4n^{\prime}$. The sum of completion times of such a
schedule is smaller than the one of a virtual schedule that would finish
sequentially 0, $X$, $X$, and $X+K$ messages, repeatedly every 4 time steps,
which corresponds to the value of $C_{1}$. (The $i$th set of messages flushed
must wait $4(i-1)$ time steps for the previous sets to finish, after which $X$
messages are completed at time steps $2$, $3$, and $4$, and $K$ messages are
completed at time step $4$.)

On the other hand, assume $(T_{1},M_{1},1,B)$ has a schedule $S_{1}$ that
requires at most $4n^{\prime}$ flushes and a sum of completion times at most
$C_{1}$. Then $S_{1}$ must have at most $n^{\prime}$ flushes to $x$ (since
each of the $3n^{\prime}$ leaves must also be flushed to at least once). Call
a schedule for $(T_{1},M^{\prime},1,B)$ _canonical_ if it has at most
$4n^{\prime}$ total flushes, and every flush from $r$ to $x$ contains exactly
the representative messages of three leaves of $T_{1}$. Thus, if $S_{1}$ is
canonical, then the flushes from $r$ to $x$ constitute a $3$-partition. We now
show that $S_{1}$ is canonical.

Consider a simpler instance with a set of messages $M^{\prime}\subset M_{1}$,
where each leaf in $T_{1}$ has exactly $X$ messages in $M^{\prime}$ (thus,
$M^{\prime}$ corresponds to an instance where all $i\in I$ have $i=0$). We can
see that by ignoring messages in $M_{1}\setminus M^{\prime}$, ${S}$ is a valid
schedule for $(T_{1},M^{\prime},1,B)$.

Let’s lower bound the cost of any schedule for $(T_{1},M^{\prime},1,B)$ that
requires at most $4n^{\prime}$ total flushes. Note that since $t$ flushes are
required to bring the contents of $3t$ leaves to $x$, no schedule can complete
more than $3t$ leaves by time step $4t$ for any $t\geq 0$. Thus, any schedule
for $(T_{1},M^{\prime},1,B)$ has cost

$\displaystyle C_{0}$
$\displaystyle=\sum_{i=1}^{n^{\prime}}4(i-1)(3X)+X(2+3+4)$
$\displaystyle=C_{1}-\sum_{i=1}^{n^{\prime}}4Ki>C_{1}-X.$

Clearly, $S_{1}$ on $(T_{1},M^{\prime},1,B)$ has cost $C_{0}$ if and only if
it is canonical. If $S_{1}$ has cost more than $C_{0}$ then all messages in
some leaf are delayed past their finishing time in a canonical
schedule121212Recall that since there are $4n^{\prime}$ flushes each leaf can
be flushed to once—if one message is delayed, all messages in that leaf must
be delayed as well. in which case the total completion time of $S_{1}$ on
$M^{\prime}$ (and thus, the total completion time of $S_{1}$ on $M$) is $\geq
C_{0}+X>C_{1}$, which contradicts the definition of $S_{1}$. Thus, $S_{1}$ is
canonical, and the messages in each flush from $r$ to $x$ constitute a
$3$-partition.

Thus, $(T_{1},M_{1},1,B)$ has a valid schedule $S_{1}$ with total completion
time $C_{1}$ and $4n^{\prime}$ total flushes if and only if $I$ has a
$3$-partition. To finish the reduction, we alter $T_{1}$ and $M_{1}$ to obtain
a $T$ and $M$ so that $(T,M,1,B)$ has a valid schedule with total completion
time $C_{2}$ if and only if $I$ has a $3$-partition.

To create $T$ and $M$, add another $8n^{\prime}|M_{1}|+C_{1}$ leaves to
$T_{1}$ to obtain $T$; these leaves all have a unique parent (thus we add many
paths of length $2$ to $T_{1}$). For each leaf $\ell$ created, add a message
with $\ell$ as its target leaf. Let $M_{2}$ be all the messages created in
this way, and $M=M_{1}\cup M_{2}$. See Figure 4.

for tree=inner sep=0pt, minimum size=10pt, circle, draw , [,label=left:$r$
[,label=left:$x$,s sep=6ex [,label=below:$X+i_{1}$] [,label=below:$X+i_{2}$]
[$\ldots$,no edge,draw=none] [,label=below:$X+i_{3n^{\prime}}$] ] [,no
edge,phantom [,no edge,phantom]] [,edge=dashed [,label=below:$1$,edge=dashed]
] [,edge=dashed [,label=below:$1$,edge=dashed] ] [,phantom,no edge
[,label=above:$\ldots$,no edge,draw=none] ] [,edge=dashed
[,label=below:$1$,edge=dashed] ] ]

Figure 4: A diagram of $T$ in Lemma 15. Edges in $T_{2}$ are given as dotted
lines; edges in $T_{1}$ are solid. The number of all messages in $M$ with a
given target leaf is given below each leaf.

We define

$C_{2}=C_{1}+4n^{\prime}|M_{2}|+\sum_{i=1}^{|M_{2}|}2i.$

If all messages in $(T_{1},M_{1},1,B)$ can be finished by $4n^{\prime}$ and
with a sum of completion time at most $C_{1}$ by some schedule $S_{1}$, then
we can achieve a schedule that finishes with cost $C_{2}$: first, schedule all
messages in $M_{1}$ using $S_{1}$, then flush all messages in $M_{2}$ one at a
time. The weighted completion time of all messages in $M_{1}$ is $C_{1}$; the
messages in $M_{2}$ must wait at most $4n^{\prime}$ time steps for all
messages in $M_{1}$ to finish, after which they finish one at a time, each
requiring $2$ flushes.

Now, assume that all messages in $(T_{1},M_{1},1,B)$ can finish by time
$4n^{\prime}+1$ at the earliest. Let $S$ be the optimal schedule for
$(T,M,1,B)$. By an exchange argument, all messages in $M_{1}$ finish before
all messages in $M_{2}$ in $S$. Thus, all messages in $M_{2}$ must wait for
all messages in $M_{1}$ to complete, after which they can be finished one at a
time. Thus, the cost for messages in $M_{2}$ in $S$ is at least

$(4n^{\prime}+1)|M_{2}|+\sum_{i=1}^{|M_{2}|}2i>C_{2}$

since $|M_{2}|>4n^{\prime}|M_{1}|+C_{1}$.

Now, assume that all messages in $(T_{1},M_{1},1,B)$ cannot finish with a sum
of completion time at most $C_{1}$. We have seen that the maximum completion
time of these messages is at most $4n^{\prime}$. Let $S$ be the optimal
schedule for $(T,M,1,B)$. Again, by an exchange argument, all messages in
$M_{1}$ finish before all messages in $M_{2}$ in $S$. Thus, the cost for
messages in $M_{2}$ in $S$ is at least $C_{2}+1$.

Thus, $(T,M,1,B)$ has a schedule with cost $C_{2}$ if and only if $I$ has a
$3$-partition.

∎

##  5 Conclusion

This paper formalizes WORMS, a new model of root-to-leaf flushing in WODs.
WORMS captures a new notion of latency in write-optimized trees: some types of
operations complete only after they have flushed through their entire root-to-
leaf path in the tree. The goal is to complete these queries in the fewest
cache misses possible, thus minimizing the query latency.

We give a $O(1)$-approximation algorithm for WORMS via a reduction to a
closely-related scheduling problem, and we show that solving WORMS exactly is
NP-hard.

The natural next step is to generalize to the much more challenging online and
non-clairvoyant setting: messages arrive online, and the path each message
takes through the tree is not known to the scheduler. Our hope is that the
structure of the algorithms presented here can help inform strategies for this
more general problem.

##  6 Acknowledgments

This work was supported in part by NSF grants CCF 210381 and CNS 1938709.

## References

  * [1] Daniar Achakeev and Bernhard Seeger.  Efficient bulk updates on multiversion b-trees.  Proceedings of the VLDB Endowment, 6(14):1834–1845, 2013.
  * [2] Alok Aggarwal and S Vitter, Jeffrey.  The input/output complexity of sorting and related problems.  Communications of the ACM, 31(9):1116–1127, 1988.
  * [3] Michael A Bender, Alex Conway, Martín Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara Mcallister, Nirjhar Mukherjee, Prashant Pandey, Donald E Porter, Jun Yuan, and Yang Zhan.  External-memory dictionaries in the affine and PDAM models.  ACM Transactions on Parallel Computing (TOPC), 8(3):1–20, 2021\.
  * [4] Michael A. Bender, Alexander Conway, Martin Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara McAllister, Nirjhar Mukherjee, Prashant Pandey, Donald E. Porter, Jun Yuan, and Yang Zhan.  Small refinements to the DAM can have big consequences for data-structure design.  In Proceedings of the Thirteenth Annual Symposium on Parallel Algorithms and Architectures (SPAA), pages 265–274, 2019.
  * [5] Michael A Bender, Rathish Das, Martín Farach-Colton, Rob Johnson, and William Kuszmaul.  Flushing without cascades.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 650–669. SIAM, 2020.
  * [6] Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan.  An introduction to Be-trees and write-optimization.  :login; Magazine, 40(5):22–28, 10 2015.
  * [7] Michael A Bender, Martin Farach-Colton, Rob Johnson, Simon Mauras, Tyler Mayer, Cynthia A Phillips, and Helen Xu.  Write-optimized skip lists.  In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 69–78, 2017.
  * [8] Samuel W Bent, Daniel D Sleator, and Robert E Tarjan.  Biased search trees.  SIAM Journal on Computing, 14(3):545–568, 1985.
  * [9] Gerth Stølting Brodal and Rolf Fagerberg.  Lower bounds for external memory dictionaries.  In SODA, volume 3, pages 546–554. Citeseer, 2003.
  * [10] Xinyuan Cao, Jingbang Chen, Li Chen, Chris Lambert, Richard Peng, and Daniel Sleator.  Learning-augmented b-trees.  arXiv preprint arXiv:2211.09251, 2023.
  * [11] Feng Chen, Binbing Hou, and Rubao Lee.  Internal parallelism of flash memory-based solid-state drives.  ACM Trans. Storage, 12(3), may 2016.
  * [12] Niv Dayan, Manos Athanassoulis, and Stratos Idreos.  Optimal bloom filters and adaptive merging for LSM-trees.  ACM Transactions on Database Systems (TODS), 43(4):1–48, 2018.
  * [13] Niv Dayan and Stratos Idreos.  Dostoevsky: Better space-time trade-offs for LSM-tree based key-value stores via adaptive removal of superfluous merging.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, page 505–520, New York, NY, USA, 2018. Association for Computing Machinery.
  * [14] John Esmet, Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul.  The tokufs streaming file system.  In 4th USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage’12, Boston, MA, USA, June 13-14, 2012, 2012.
  * [15] Christos Faloutsos and HV Jagadish.  On B-tree indices for skewed distributions.  In Proceedings of the 18th International Conference on Very Large Data Bases, pages 363–374, 1992.
  * [16] Sanjay Ghemawat and Jeff Dean.  LevelDB: A fast and lightweight key/value database library by Google.  https://github.com/google/leveldb, Last Accessed October 1, 2023, 2014.
  * [17] Ofek Gila, Michael T Goodrich, and Robert E Tarjan.  Zip-zip trees: Making zip trees more balanced, biased, compact, or persistent.  In Algorithms and Data Structures Symposium, pages 474–492. Springer, 2023.
  * [18] Leslie A Hall, Andreas S Schulz, David B Shmoys, and Joel Wein.  Scheduling to minimize average completion time: Off-line and on-line approximation algorithms.  Mathematics of operations research, 22(3):513–544, 1997.
  * [19] WA Horn.  Single-machine job sequencing with treelike precedence ordering and linear delay penalties.  SIAM Journal on Applied Mathematics, 23(2):189–202, 1972.
  * [20] Sven Jäger and Philipp Warode.  Simple approximation algorithms for minimizing the total weighted completion time of precedence-constrained jobs.  In 2024 Symposium on Simplicity in Algorithms (SOSA), pages 82–96. SIAM, 2024.
  * [21] William Jannen, Michael Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter.  Lazy analytics: Let other queries do the work for you.  In Proceedings of the USENIX Conference on Hot Topics in Storage and File Systems (HotStorage), pages 301–315, 2016.
  * [22] William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, Leif Walsh, Michael Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter.  BetrFS: A right-optimized write-optimized file system.  In Proceedings of the USENIX Conference on File and Storage Technologies (FAST), pages 301–315, 2015.
  * [23] William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, Leif Walsh, Michael Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter.  BetrFS: Write-optimization in a kernel file system.  ACM Transactions on Storage (TOS), 11(4):18:1–18:29, 2015.
  * [24] Yizheng Jiao, Simon Bertron, Sagar Patel, Luke Zeller, Rory Bennett, Nirjhar Mukherjee, Michael A Bender, Michael Condict, Alex Conway, Martín Farach-Colton, Xiongzi Ge, William Jannen, Rob Johnson, Donald E Porter, and Jun Yuan.  BetrFS: a compleat file system for commodity SSDs.  In Proceedings of the 17th European Conference on Computer Systems, pages 610–627, 2022.
  * [25] Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis.  The case for learned index structures.  In Proceedings of the International Conference on Management of Data (SIGMOD), pages 489–504, 2018.
  * [26] Yu-Kwong Kwok and Ishfaq Ahmad.  Static scheduling algorithms for allocating directed task graphs to multiprocessors.  ACM Computing Surveys (CSUR), 31(4):406–471, 1999.
  * [27] Jan Karel Lenstra and AHG Rinnooy Kan.  Complexity results for scheduling chains on a single machine.  European Journal of Operational Research, 4(4):270–275, 1980.
  * [28] Shi Li.  Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations.  SIAM Journal on Computing, 49(4):FOCS17–409, 2020.
  * [29] Ruicheng Liu, Peiquan Jin, Xiaoliang Wang, Yongping Luo, Zhaole Chu, and Yigui Yuan.  Closing the performance gap between leveling and tiering compaction via bundle compaction.  In Proceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing, HPDC ’23, page 143–154, New York, NY, USA, 2023. Association for Computing Machinery.
  * [30] Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau.  WiscKey: Separating keys from values in SSD-conscious storage.  In 14th USENIX Conference on File and Storage Technologies (FAST 16), pages 133–148. USENIX Association, February 2016.
  * [31] Graham Lustiber.  E-tree: An ever evolving tree for evolving workloads.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 13–15, 2017.
  * [32] Alix Munier, Maurice Queyranne, and Andreas S Schulz.  Approximation bounds for a general class of precedence constrained parallel machine scheduling problems.  In Proc. 6th Annual Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 367–382. Springer, 1998.
  * [33] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil.  The log-structured merge-tree (LSM-tree).  Acta Informatica, 33(4):351–385, 1996.
  * [34] Prashant Pandey, Shikha Singh, Michael A Bender, Jonathan W Berry, Martín Farach-Colton, Rob Johnson, Thomas M Kroeger, and Cynthia A Phillips.  Timely reporting of heavy hitters using external memory.  In Proc. of the International Conference on Management of Data (SIGMOD), pages 1431–1446. ACM, 2020.
  * [35] Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham.  Pebblesdb: Building key-value stores using fragmented log-structured merge trees.  In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP ’17, page 497–514. ACM, 2017.
  * [36] Joel Reardon, David Basin, and Srdjan Capkun.  Sok: Secure data deletion.  In 2013 IEEE Symposium on Security and Privacy, pages 301–315, 2013\.
  * [37] Kai Ren and Garth A Gibson.  TABLEFS: Enhancing metadata efficiency in the local file system.  In USENIX ATC, pages 145–156, 2013.
  * [38] Pradeep J Shetty, Richard P Spillane, Ravikant R Malpani, Binesh Andrews, Justin Seyster, and Erez Zadok.  Building workload-independent storage with vt-trees.  In 11th USENIX Conference on File and Storage Technologies (FAST), pages 17–30, 2013.
  * [39] Adam Silberstein, Brian F Cooper, Utkarsh Srivastava, Erik Vee, Ramana Yerneni, and Raghu Ramakrishnan.  Efficient bulk insertion into a distributed ordered table.  In Proc. of the International Conference on Management of Data (SIGMOD), pages 765–778. ACM, 2008.
  * [40] Facebook Database Engineering Team.  RocksDB: A Persistent Key-Value Store for Flash and RAM Storage.  https://github.com/facebook/rocksdb, Last Accessed October 1, 2023, 2014.
  * [41] Facebook Database Engineering Team.  Rocksdb compaction.  https://github.com/facebook/rocksdb/wiki/Compaction, 2023.  Accessed: 2023-27-09.
  * [42] Vadim G Timkovsky.  Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity.  European Journal of Operational Research, 149(2):355–376, 2003\.
  * [43] Ting Yao, Jiguang Wan, Ping Huang, Yiwen Zhang, Zhiwen Liu, Changsheng Xie, and Xubin He.  GearDB: A GC-free Key-Value store on HM-SMR drives with gear compaction.  In 17th USENIX Conference on File and Storage Technologies (FAST 19), pages 159–171, Boston, MA, February 2019. USENIX Association.
  * [44] Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter.  Optimizing every operation in a write-optimized file system.  In FAST, pages 1–14, 2016.