  The generalized k-server problem is a far-reaching extension of the k-server
problem with several applications. Here, each server $s_i$ lies in its own
metric space $M_i$. A request is a k-tuple $r = (r_1,r_2,\dotsc,r_k)$ and to
serve it, we need to move some server $s_i$ to the point $r_i \in M_i$, and the
goal is to minimize the total distance traveled by the servers. Despite much
work, no f(k)-competitive algorithm is known for the problem for k > 2 servers,
even for special cases such as uniform metrics and lines.
  Here, we consider the problem in uniform metrics and give the first
f(k)-competitive algorithms for general k. In particular, we obtain
deterministic and randomized algorithms with competitive ratio $O(k 2^k)$ and
$O(k^3 \log k)$ respectively. Our deterministic bound is based on a novel
application of the polynomial method to online algorithms, and essentially
matches the long-known lower bound of $2^k-1$. We also give a
$2^{2^{O(k)}}$-competitive deterministic algorithm for weighted uniform
metrics, which also essentially matches the recent doubly exponential lower
bound for the problem.
