Time-Optimal k-Server

We choose any connected set $S$ of $k+1$ vertices of $G$ and consider the metric subspace described by the induced subgraph $G[S]$. The algorithm is given an instance that always requests a point not occupied by any of its servers. We note that any configuration where all $k$ servers occupy $k$ distinct locations can be reached from any other such configuration at cost at most $1$, by moving servers along a path connecting two unoccupied points. This allows an optimal offline algorithm to serve any $k$ consecutive requests at cost $1$. $◀$

Note that, in contrast to the corresponding result for the distance model, it is unclear whether this result can be extended to arbitrary metric spaces with more than $k$ points.

Let alg be any online algorithm for the given metric space. For a finite unweighted cycle with an even number of $N\ge 2k+6$ vertices, label the vertices counterclockwise by $0,1,\mathrm{\dots },N-1$. For the sphere ${𝕊}^1$, choose $N=2k+6$ points evenly spaced along this metric space, label them $0,1,\mathrm{\dots },N-1$ counterclockwise, and re-scale the space such that the distance between consecutive points is $1$. For simplicity, we refer to the labeled points as integers and say that an integer neighbors another one if they are at distance $1$ from each other. In all cases, every even integer neighbors two odd ones and each odd one two even ones. We will construct an instance phase by phase such that there is an optimal algorithm opt satisfying the following invariant.

Without loss of generality, we assume for the following description that the integers occupied by opt at the start of the phase are all even by choosing an appropriate initial configuration and shifting the labels of the integers by one after each phase. Any phase will consist of potentially repeated requests for $k$ distinct odd integers, among which at least two are consecutive. Moreover, the requests will be chosen such that opt can cover all of them by moving all of its $k$ servers simultaneously, each by a distance $1$ and thus at total cost $1$, at the beginning of the phase and with no movements afterwards. Any phase constructed with these properties preserves the invariant for the next phase, allowing us to iterate the process to construct an arbitrarily long instance of arbitrarily high optimal cost.

Since opt does not move its servers anymore after its phase-initial synchronous movements, we can request any point covered by opt as many times as we would like without increasing the cost of opt or changing opt’s configuration at the end of the phase. We can thus enforce the following invariant for alg without loss of generality.

Assume that alg makes a move such that some integer previously requested in the current phase is no longer covered. Then the constructed instance could be extended by immediately requesting this integer again after this move, at no additional cost to opt. This can be continued until all the integers previously requested in the current phase are covered again by alg. $\mathrm{⊲}$

Using this invariant of alg, we can now also assume the following without loss of generality.

In summary, we can assume the following properties for each phase.

1. 1.

   At the beginning of the phase, the servers of alg occupy the same positions as the servers of opt, namely $k$ distinct even integers, at least two of which are consecutive (in the sense of being separated by a distance of $2$).

2. 2.

   During the phase, $k$ distinct odd integers are requested one by one. Each such integer must, once requested, be covered by alg during all subsequent requests of the phase.

3. 3.

   Moreover, there is a bipartite matching between the $k$ odd requested points and the $k$ phase-initially covered even integers where each edge of the matching has weight exactly $1$.

4. 4.

   Finally, opt moves its servers along this matching at cost $1$ when the first request of the phase appears and does not move its servers anymore for the rest of the phase.

We now describe how the $k$ requests for any given phase are chosen depending on alg’s behavior in a way that guarantees Invariant 7 to hold for the following phase.

Consider any phase. Partition the phase-initial server positions (which are the same for opt and alg) into $\mathrm{\ell }\ge 1$ maximal, pairwise disjoint, nonempty sets $S_1,\mathrm{\dots },S_{\mathrm{\ell }}$ of consecutive even integers. We define $k_i≔|S_i|$ and note that ${\sum }_{i=1}^{\mathrm{\ell }}{k}_i=k$. Given a metric space $ℳ=(M,d)$, a point $c\in M$, and radius $\rho \ge 0$, we call the open ball and $D_{\rho }[c]≔\{p\in M\mid d(p,c)\le \rho \}$ the closed ball. For any $m\in [\mathrm{\ell }]$, we call $R_m≔{\bigcup }_{i\in S_m}{D}_2(i)$ the range of $S_m$; Figure 1 shows an example for $k=5$.

Note that the range $R_m$ contains exactly $k_m+1$ odd integers. Exactly $k_m$ of them are requested during a phase in the instance family described below. This guarantees that opt can indeed move all its servers from their phase-initial positions to the points request during this phase at cost $1$, and then keep them there for the remainder of the phase, which proves the first part of Invariant 7. We call the range $R_m$ saturated if the instance has already requested $k_m$ out of the $k_m+1$ odd integers of $R_m$ during the current phase, and unsaturated otherwise. Recall that once an integer is requested, a server occupies it during all remaining requests of the phase; thus any saturated $R_m$ contains at least $k_m$ servers. A phase ends when all ranges are saturated.

Since there are two consecutive even integers in the phase-initial configuration of opt, by renaming we can assume without loss of generality that $k_1\ge 2$ and that $S_1=\{2,4,\mathrm{\dots },2k_1\}$. Since $R_1$ contains exactly $k_1+1\ge 3$ consecutive odd integers and $k_1$ of them are requested during the phase, at least two consecutive odd integers are requested. This proves the second part of Invariant 7.

We now describe what the requests in the considered phase depend on. For this, we will call a point distant if and only if it has distance at least $1$ from all current servers, i.e., if it lies outside of all open unit balls around the current server locations. The first request is $3$, which is indeed a distant point since all servers are phase-initially at even integers. From then on, a further request is chosen according to the following selection procedure until $k-1$ odd integers have been requested during the phase or the procedure becomes impossible: Request an arbitrary distant odd integer not previously requested during the phase from any unsaturated range $R_m$ except for the integer $1$. The sequence of such requests ends only when $k_m$ requests have been made in each range $R_m$ with $1\ne m\in [\mathrm{\ell }]$ and $k_1-1$ requests have been made in $R_1$, or if no such request is possible anymore. We will show that once this process ends, there must be a point in $R_1$ that no server can reach with cost less than $2$ using the following simple claim.

A unit ball can contain at most one odd integer. Moreover, unit balls around points outside of a range $R_m$ cannot contain odd integers inside this range, and analogously for the truncated range $R_1^{\prime }$. Hence, the range $R_m$ for any $m\in [\mathrm{\ell }]$ containing at most $k_m$ servers means that at most $k_m$ out of the $k_m+1$ odd integers in it are not distant and thus that there is a distant odd integer in $R_m$. Analogously, the truncated range $R_1^{\prime }$ containing at most $k_1-2$ servers means that at most $k_1-2$ out of the $k_1-1$ odd integers in it are not distant, and thus that there is a distant odd integer in $R_1^{\prime }$. $\mathrm{⊲}$

By this claim, if the selection procedure ends, any range $R_m$ with $1\ne m\in [\mathrm{\ell }]$ must contain at least $k_m$ servers, whether or not it is saturated, and $R_1^{\prime }$ must contain at least $k_1-2$ servers. We consider two different cases.

• $\mathrm{■}$

  Case 1: $R_1^{\prime }$ contains at least $k_1-1$ servers. In this case, $R_1$ contains at least $k_1$ servers (including the server positioned on $3$). This means that all ranges $R_m$ with $1\ne m\in [\mathrm{\ell }]$ must contain exactly $k_m$ servers and must therefore be saturated. Thus, these servers all occupy odd integers and have a distance of at least $2$ to the odd integer $1$. The same holds for any servers in $R_1^{\prime }$.

• $\mathrm{■}$

  Case 2: $R_1^{\prime }$ contains exactly $k_1-2$ servers. In this case, $R_1^{\prime }$ contains a distant point. Since the selection procedure ended, a total of $k_1-1$ requests must have already been made to $R_1$ and served. Thus, the $k_1-2$ servers in $R_1^{\prime }$ occupy distinct odd integers and cannot reach any other odd integer in $R_1$ with cost less than $2$. Of the other ranges $R_m$ with $1\ne m\in [\mathrm{\ell }]$, all but possibly one must be saturated, since they contain exactly $k_m$ servers. Therefore, these servers occupy odd integers and cannot reach odd integers in $R_1$ with cost less than $2$. Finally, one range $R_m$ with $1\ne m\in [\mathrm{\ell }]$ may contain $k_m+1$ servers, or a single server may occupy a point outside a range. Such a server can only reach either the odd integer $1$ or the odd integer $2k_1-1$ in $R_1$ with cost less than $2$. This is clear if the metric space is a line.

  If it is a cycle or the continuous sphere, the two ranges would have to meet at both ends. However, this would mean that they contain all odd integers in the metric space, of which there are at least $k+3$, while they contain a maximum of $(k_1+1)+(k_m+1)\le k+2$ odd integers. Thus, since there are two odd integers in $R_1$ that have not been requested yet, one of them cannot be reached by any server with cost less than $2$.

We thus have, in both cases, an odd integer in $R_1$ that is at distance at least $2$ from all servers. Such an integer is requested next, forcing alg to incur a cost of at least $2$ when serving it. From then on, additional distant points in unsaturated ranges $R_m$ with $m\in [\mathrm{\ell }]$ (including $R_1$) are requested. Such points exist by Claim 10. Once $k$ distinct odd integers have been requested, all ranges are saturated and the phase ends.

Recall that the first request was to the odd integer $3$. Since $R_1$ contains $k_1+1$ odd integers, $k_1$ of which have been requested, at least one of the odd integers $1$ or $5$ must have been requested, and thus indeed at least two consecutive odd integers. This means that the final configuration of the phase is such that Invariant 7 is satisfied for an immediately following phase.

We can thus iterate the process and construct arbitrarily many new phases such that for each phase alg incurs a cost of at least $k+1$ while opt has a cost of exactly $1$. $◀$

Note that Theorem 6 generalizes the lower bound of $3$ given by Koutsoupias and Taylor for the special case of $k=2$ servers on the real line [22, Thm. 4]. In contrast to the distance model, lower bounds in the time model do not trivially extend to arbitrary metric superspaces. However, this particular result can be extended to other metric spaces, e.g., the Euclidean plane.

We first give the general idea of the proof. Consider a star with $k$ rays of length $2$, and assume that there is a server at each midpoint of a ray. The center of the star is requested first. Any algorithm must move one server there at cost $1$. With one of the $k$ servers at the center, one ray no longer contains a server. Its outer point is requested next, causing a cost of at least $2$. This process is then repeated $k-1$ times, always requesting the outer point of an unoccupied ray, for a total cost of $2k-1$.

The main challenge lies in simulating this instance while making the process repeatable. To this end, we construct a metric space given by a finite, unweighted graph.

The metric space is a tripartite graph $G=(V,E)$, i.e., its vertices can be partitioned into three disjoint layers $L_1\cup L_2\cup L_3=V$ such that the edges can be partitioned as $E_1\cup E_2\cup E_3=E$ with $E_1\subseteq L_1\times L_2$, $E_2\subseteq L_2\times L_3$, and $E_3\subseteq L_3\times L_1$.

On the instances we describe later, the three layers will be used cyclically by any optimal solution: its servers will all move synchronously first from $L_1$ to $L_2$, then to $L_3$, then back to $L_1$, and so on. Moreover, the three subgraphs $(L_1\cup L_2,E_1)$, $(L_2\cup L_3,E_2)$, and $(L_3\cup L_1,E_3)$ are all isomorphic. In particular, the layers all have the same size. Each layer is partitioned into $B≔k{(k-1)}^{k-1}$ uniformly sized blocks. Each block in turn consists of one special vertex called its hub and $k(k-1)$ vertices that we call its fringe points, grouped into $k$ groups each of size $k-1$. We identify the blocks with the integers $[B]$, and similarly denote the groups of each block by $[k]$ and the points of a group by $[k-1]$. We denote the hub of block $b$ in layer $L_{\mathrm{\ell }}$ by $h(\mathrm{\ell },b)$ and the fringe point $n$ in group $g$ of the same block by $f(\mathrm{\ell },b,g,n)$. Thus, the vertex set is given by

For notational convenience we define $L_4≔L_1$ and $L_0≔L_3$. To describe the edges of $G$, we first highlight some uniform aspects of the construction. For each $\mathrm{\ell }\in [3]$, the edges $E_{\mathrm{\ell }}$ between $L_{\mathrm{\ell }}$ and $L_{\mathrm{\ell }+1}$ are constructed identically.

Moreover, the edges from any layer to the next are block-uniform in the following sense: for any $\mathrm{\ell }\in [3]$, $g\in [k]$, and $n\in [N]$, the neighborhood in $L_{\mathrm{\ell }+1}$ is the same for every fringe point $f(\mathrm{\ell },b,g,n)$ and for any hub $h(\mathrm{\ell },b)$ independent of $b\in [B]$.

Now consider any block $b$ of $L_{\mathrm{\ell }}$. To each possible choice of $k-1$ fringe points from $k-1$ distinct groups, we assign one block $c\in [B]$ from $L_{\mathrm{\ell }+1}$ by an arbitrary but fixed bijection. Such a bijection exists, because there are $k$ possibilities to choose $k-1$ fringe groups and ${(k-1)}^{k-1}$ ways to choose one fringe point from each of these groups, which means that the total number of possible choices is exactly $B$, the number of blocks in $L_{\mathrm{\ell }+1}$.

Fix such a choice and the corresponding block $c$ in $L_{\mathrm{\ell }+1}$. Each of the $k-1$ chosen fringe points, as well as the hub of $b$, is assigned injectively to one of the $k$ groups of fringe points of $c$ and then made adjacent to all $k-1$ points of the assigned group. For concreteness, let the chosen fringe point of group $g$ in $b$ be assigned to group $g$ in block $c$, while the hub is assigned to the remaining group of block $c$ that is not represented in the $k-1$ chosen ones. Finally, all $k-1$ chosen fringe points and the hub of $b$ are made adjacent to the hub of $c$ in $L_{\mathrm{\ell }+1}$.

More formally, identify the possible choices of $k-1$ fringe points in a block of $L_{\mathrm{\ell }}$ with $[B]$. For each choice $c\in [B]$, denote by $g_c\in [k]$ the unique index of the group without a chosen point. For any $g\in [k]$ with $g\ne g_c$, denote by $n_c^g\in [k-1]$ the index of the unique point chosen from group $g$. This means that the fringe points in choice $c$ are exactly $f(\mathrm{\ell },b,g,n_c^g)$ for $g\in [k]$ and $g\ne g_c$. Then we have the following edges between block $b$, which is in $L_{\mathrm{\ell }}$, and $L_{\mathrm{\ell }+1}$:

The full edge set is then

A visual representation of the graph $G=(V,E)$ for $k=2$ is shown in Figure 3. For $k=3$, an example of one block in $L_1$ and two blocks in $L_2$ is given in Figure 2, while the full graph is shown in Figure 3. The following claim summarizes some important properties of $G$. It follows directly from the construction of the edges.

We now show that no online algorithm can be better than $(2k-1)$-competitive on the metric space described by $G$.

Let alg be any deterministic online algorithm. We describe an instance consisting of distinct phases. In each phase, exactly $k$ distinct points, all from the same layer, are requested, potentially with many repetitions. The instances are designed such that opt can move all its $k$ servers by a distance of $1$ at the beginning of each phase and then serve all requests within this phase at no additional cost, while alg has cost at least $2k-1$.

At the start of each phase, the servers of opt are located in a single block $b$ of $L_{\mathrm{\ell }}$ and more specifically at one of its hub points and $k-1$ points chosen from $k-1$ distinct fringe groups in it.

The phase consists of vertices from the block $c$ in $L_{\mathrm{\ell }+1}$ corresponding to the choice of fringe points in block $b$ that form the configuration of opt at the start of the phase. Specifically, it consists of the hub of block $c$ and $k-1$ fringe points chosen from distinct groups. This means that the process can be repeated since the final configuration is equivalent to the starting position. It also means that opt can reach the configuration at cost $1$: it can move $k-1$ of its servers in block $b$ to fringe points in block $c$ in the unique group they are adjacent to, and move the final server to the hub of block $c$.

We can assume that within each phase, alg keeps a server on each previously requested point. Otherwise, the instance will simply request that point again, at no additional cost to opt.

The instance starts the phase with a request to the hub of block $c$. alg must now move a server to that vertex and thus incurs cost $1$. Assume that $s\in [k-1]$ fringe points in block $c$ have already been requested by the instance in this phase. We claim that there is at least one fringe point $n$ in block $c$ such that

1. (a)

   no vertex from the group in block $c$ containing $n$ was requested in this phase before, and

2. (b)

   no server of alg can reach $n$ with cost less than $2$.

By assumption, $s+1$ servers of alg already occupy requested points in block $c$. These points are not adjacent to any other point in $L_2$, and thus in particular not to any point in block $c$. There are $k-s$ groups in block $c$ that are not yet represented by a request in this phase. Since there are only $k-s-1$ remaining servers, by Claim 13˜i and ii, there is at least one group in block $c$ such that no fringe point in this group is adjacent to a server that is in $L_{\mathrm{\ell }-1}$ or on a fringe point in $L_{\mathrm{\ell }+1}$. Within this group, there are $k-1$ points. Any server of alg that can reach such a point with cost at most $1$ is either on that point (in which case it cannot reach any other point in block $c$ with cost at most $1$) or on a hub in $L_{\mathrm{\ell }+1}$ (in which case, by Claim 13˜iii, the same holds).

Since there are $k-s-1$ remaining servers, this means that such a point $n$ exists, unless $s=0$, i.e., if the only point requested in this phase has been the hub, and all servers of alg occupy hubs in $L_{\mathrm{\ell }+1}$ or fringe points in $L_{\mathrm{\ell }}$. In this case, by Claim 13˜iii, a server on a hub in $L_{\mathrm{\ell }+1}$ can reach at most $k-1$ fringe points with cost $1$. A server on a fringe point in block $c$ can only reach one such point. Therefore, the total number of fringe points in block $c$ that can be reached in distance $1$ by servers on such vertices is at most ${(k-1)}^2$. This is strictly smaller than the total number of $k\cdot (k-1)$ fringe points in block $c$; so again, a point $n$ with the required properties must exist.

The instance now requests this point, which alg must serve with cost at least $2$. After $k-1$ such requests, the phase ends. alg and opt are in the promised final configuration, and the total cost of alg in this phase is $1+(k-1)\cdot 2=2k-1$. $◀$

It follows by Observation 4 that there is a $3k$-competitive algorithm on this graph.

The metric space is described by a graph $G=(V,E)$ that extends the construction used in the proof of Theorem 12. Instead of a single hub point $h(\mathrm{\ell },b)$, each block contains a hub group of $N$ hub points $h(\mathrm{\ell },b,n)$ for some large number $N$. Each of the $k$ fringe groups also contains $N$ fringe points. Correspondingly, the number of blocks is $B=k{N}^{k-1}$.

We describe a distribution over hard instances on which no deterministic algorithm alg can be better than $(k+H_k-1-\epsilon )$-competitive, and then apply Yao’s principle. The instances are again partitioned into phases, and in each phase, points are requested from the block corresponding to the positions of the servers of opt, so that opt has cost $1$ per phase.

The instances start with a hub point chosen uniformly at random from this block. The expected cost alg incurs serving this request is approximately $1$ since there are $N\gg k$ possible choices. From then on, one of the $k+1$ groups (either the hub group or a fringe group) is chosen uniformly at random. If no point from that group has been requested yet in that phase, a point from the group is chosen uniformly at random and requested; otherwise, the previous point is requested again.

We then show that, if $s$ distinct points with have been requested, the expected cost of alg is at least $(k+1-s)/(k+1)+1/(k+1)$, by using the equivalent of Claim 13. The expected number of requests until the next distinct point is requested is $(k+1)/(k+1-s)$, so the expected cost of alg in that timeframe is at least $1+1/(k+1-s)$. Summing up over all $s$ and adding the expected cost of $1$ for the first request to a hub point, the expected cost of alg is therefore

$◀$

Note that it can be shown that the graph used in the proof of Theorem 16 has diameter $3$, analogously to Observation 14. Thus there is also a deterministic algorithm with competitive ratio $3k$ on that metric space.