  The performance of many large-scale and data-intensive distributed systems
critically depends on the capacity of the interconnecting network. This paper
is motivated by the vision of self-adjusting infrastructures whose resources
can be adjusted according to the workload they currently serve, in a
demand-aware manner. Such dynamic adjustments can be exploited to improve
network utilization and hence performance, by dynamically moving frequently
interacting communication partners closer, e.g., collocating them in the same
server or datacenter rack.
  In particular, we revisit the online balanced graph partitioning problem
which captures the fundamental tradeoff between the benefits and costs of
dynamically collocating communication partners. The demand is modelled as a
sequence $\sigma$ (revealed in an online manner) of communication requests
between $n$ processes, each of which is running on one of the $\ell$ servers.
Each server has capacity $k=n/\ell$, hence, the processes have to be scheduled
in a balanced manner across the servers. A request incurs cost $1$, if the
requested processes are located on different servers, otherwise the cost is 0.
A process can be migrated to a different server at cost $1$.
  This paper presents the first online algorithm for online balanced graph
partitioning achieving a polylogarithmic competitive ratio for the fundamental
case of ring communication patterns. Specifically, our main contribution is a
$O(\log^3 n)$-competitive randomized online algorithm for this problem. We
further present a randomized online algorithm which is $O(\log^2
n)$-competitive when compared to a static optimal solution. Our two results
rely on different algorithms and techniques and hence are of independent
interest.
