  This paper studies a fundamental algorithmic problem related to the design of
demand-aware networks: networks whose topologies adjust toward the traffic
patterns they serve, in an online manner. The goal is to strike a tradeoff
between the benefits of such adjustments (shorter routes) and their costs
(reconfigurations). In particular, we consider the problem of designing a
self-adjusting tree network which serves single-source, multi-destination
communication. The problem has interesting connections to self-adjusting
datastructures. We present two constant-competitive online algorithms for this
problem, one randomized and one deterministic. Our approach is based on a
natural notion of Most Recently Used (MRU) tree, maintaining a working set. We
prove that the working set is a cost lower bound for any online algorithm, and
then present a randomized algorithm RANDOM-PUSH which approximates such an MRU
tree at low cost, by pushing less recently used communication partners down the
tree, along a random walk. Our deterministic algorithm MOVE-HALF does not
directly maintain an MRU tree, but its cost is still proportional to the cost
of an MRU tree, and also matches the working set lower bound.
