Advancing technology has rendered the Internet a viable medium for collaborative computing, via mechanisms such as Web-Based Computing and Grid-Computing. We present a ``pebble game'' that abstracts the process of scheduling a computation-dag for computing on the Internet, including a novel formal criterion for comparing the qualities of competing schedules. We illustrate the formal setting by studying the Internet-scheduling problem for computation-dags whose dependencies have the structure of a mesh of any finite dimensionality (a mesh-dag, for short). We prove that the strategy of scheduling task-nodes for execution along successive ``diagonal levels'' of the mesh-dags is optimal for two-dimensional mesh-dags and within a constant factor of optimal for mesh-dags of higher dimensionalities. We show also that this scheduling strategy remains optimal for a generalization of two-dimensional mesh-dags whose structures are determined by abelian monoids (a monoid-based version of Cayley graphs).
(I probably will not get through all of this in 1 hour; if time gets
close, I shall omit the Cayley dags.)
Last modified 10 March 2003