The k-server problem with parallel requests and the compound work function algorithm

In this paper we consider k-server problems with parallel requests where several servers can also be located on one point. We will distinguish the surplussituation where the request can be completely fulfilled by means of the k servers and and the scarcity-situation where the request cannot be completely met. First, we will give an example. It shows that the corresponding work function algorithm is not competitive in the case of the scarcity-situation. Until now, it remains an open question whether the work function algorithm is competitive or not in the case of the surplus-situation. Thats why, we will suggest the new "compound work function algorithm" in the following section and prove that this algorithm is also (2 k - 1)-competitive