We revisit the design of self-adjusting single-source tree networks. The problem can be seen as a generalization of the classic list update problem to trees, and finds applications in reconfigurable datacenter networks. We are given a balanced binary tree T connecting n nodes V = {v1,…, vn}. A source node v0, attached to the root of the tree, issues communication requests to nodes in V , in an online and adversarial manner; the access cost of a request to a node v, is given by the current depth of v in T . The online algorithm can try to reduce the access cost by performing swap operations, with which the position of a node is exchanged with the position of its parent in the tree; a swap operation costs one unit. The objective is to design an online algorithm which minimizes the total access cost plus adjustment cost (swapping). Avin et al. [12] (LATIN 2020) recently presented RANDOM-PUSH, a constant competitive online algorithm for this problem, based on random walks, together with a sophisticated analysis exploiting the working set property.This paper studies analytically and empirically, online algorithms for this problem. In particular, we explore how to derandomize RANDOM-PUSH. In the analytical part, we consider a simple derandomized algorithm which we call ROTOR-PUSH, as its behavior is reminiscent of rotor walks. Our first contribution is a proof that ROTOR-PUSH is constant competitive: its competitive ratio is 12 and hence by a factor of five lower than the best existing competitive ratio. Interestingly, in contrast to RANDOM-PUSH, the algorithm does not feature the working set property, which requires a new analysis. We further present a significantly improved and simpler analysis for the randomized algorithm, showing that it is 16-competitive.In the empirical part, we compare all self-adjusting single-source tree networks, using both synthetic and real data. In particular, we shed light on the extent to which these self-adjusting trees can exploit temporal and spatial structure in the workload. Our experimental artefacts and source codes are publicly available.

Reconfigurable optical topologies are emerging as a promising technology to improve the efficiency of datacenter networks. This paper considers the problem of scheduling opportunistic links in reconfigurable datacenters such as ProjecToR. We study the online setting and aim to minimize flow completion times. The problem is a two-tier generalization of classic switch scheduling problems. We present a stable-matching algorithm which is O(ε^-2 )-competitive against an optimal offline algorithm, in a resource augmentation model: the online algorithm runs 2+ε times faster. Our algorithm and result are fairly general and allow for different link delays and also apply to hybrid topologies which combine fixed and reconfigurable links. Our analysis is based on LP relaxation and dual fitting.

The generalized k-server problem is an extension of the weighted k-server problem, which in turn extends the classic k-server problem. In the generalized k-server problem, each of k servers s_1, ..., s_k remains in its own metric space M_i. A request is a tuple (r_1,...,r_k), where r_i in M_i, and to service it, an algorithm needs to move at least one server s_i to the point r_i. The objective is to minimize the total distance traveled by all servers. In this paper, we focus on the generalized k-server problem for the case where all M_i are uniform metrics. We show an O(k^2 * log k)-competitive randomized algorithm improving over a recent result by Bansal et al. [SODA 2018], who gave an O(k^3 * log k)-competitive algorithm. To this end, we define an abstract online problem, called Hydra game, and we show that a randomized solution of low cost to this game implies a randomized algorithm to the generalized k-server problem with low competitive ratio. We also show that no randomized algorithm can achieve competitive ratio lower than Omega(k), thus improving the lower bound of Omega(k / log^2 k) by Bansal et al.