9 by Springer-Verlag 1978 Time-Space Trade-Offs in a Pebble Game

Summary. A certain pebble game on graphs has been studied in various contexts as a model for the time and space requirements of computations [1, 2, 3, 8]. In this note it is shown that there exists a family of directed acyclic graphs G, and constants cl, c2, c 3 such that (1) G, has n nodes and each node in G, has indegree at most 2. (2) Each graph G, can be pebbled with c a l /n pebbles in n moves. (3) Each graph G, can also be pebbled with c21/ ~ pebbles, c 2<cl, but every strategy which achieves this has at least 2 c3 v ~ moves. Let S(k, n) be the set of all directed acyclic graphs with n nodes where each node has indegree at most k. On graphs GeS(k, n) the following one person game is considered. The game is played by putting pebbles on the nodes of G according to the following rules: (i) an input node (i. e., a node without a predecessor) can always be pebbled; (ii) if all immediate predecessors of a node c have pebbles one can put a pebble on c; (iii) one can always remove a pebble from a node. The goal of the game is to put a pebble on some output node (i.e., a node without a successor) of G in such a way that the total number of pebbles which are simul-taneously on the graph is minimized. The game models the time and space requirements of computations in the following sense. The nodes of G correspond to operations and the pebbles cor-respond to storage locations. If a pebble is on a node this means that the result of the operation to which the node corresponds i stored in some storage location. Thus the rules have the following meaning