We introduce and study the minimum-backlog problem (MBP). The MBP arises in sensor networks and is related to the classic k-server problem. It can be understood as a 2-person game played on a graph G = (V, E). The “player” moves along the edges of the graph; the opponent is the “adversary.” The game proceeds in timesteps. In each timestep the adversary pours a total of one unit of water into “cups” that are located on the vertices of the graph, arbitrarily distributing the water among the cups. The player then moves from her current vertex to an adjacent vertex and empties the cup at that vertex. The player's objective is to minimize the maximum amount of water (the backlog) in any cup at any time.

We show that the competitive ratio of any algorithm for the MBP has a lower bound of Ω(Δ), where Δ is the diameter of the graph. Thus, we focus on determining a strategy for the player that guarantees a uniform upper bound on the backlog. In general graphs, the deamortization analysis of Dietz and Sleator gives a bound of O(Δ log |V|).

Our main result is that in geometric settings (e.g., sensor fields), one can obtain substantially better bounds on the maximum backlog. In particular, for a 2-dimensional n-by-n grid, we achieve a backlog of O(n (log log n)^1/2), improving the O(n log n) upper bound for general graphs, and coming close to the naive Ω(n) lower bound. Then, in a model of continuous motion of the player and continuous pouring by the adversary, for cups placed at m points in the plane we show that the backlog can be bounded by O(D (log log m)^1/2), where D is the diameter of the point set. Our methods apply also to higher (fixed) dimensions.

We study also the variant of the MBP in which the adversary has a location within the graph and must act locally (filling cups) with respect to his position, just as the player acts locally (emptying cups) with respect to her position. We prove that deciding the value of this game is PSPACE-hard.