Title :
On scheduling collaborative computations on the Internet, I: mesh-DAGs and their close relatives
Author :
Rosenberg, Arnold L.
Author_Institution :
Dept. of Comput. Sci., Massachusetts Univ., Amherst, MA, USA
Abstract :
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 (directed acyclic graph) for computing over the Internet, including a novel formal criterion for comparing the qualities of competing schedules. Within this formal setting, we identify a strategy for scheduling the task-nodes of a computation-DAG whose dependencies have the structure of a mesh of any finite dimensionality (a mesh-DAG), that is optimal to within a small constant factor (to within a low-order additive term for 2- and 3-dimensional mesh-DAG). We show that this strategy remains nearly optimal for a generalization of 2-dimensional mesh-DAG whose structures are determined by abelian monoids (a monoid-based version of Cayley graphs).
Keywords :
Internet; directed graphs; distributed programming; formal specification; grid computing; group theory; groupware; scheduling; 2-dimensional mesh-DAG; Cayley graphs; Grid computing; Internet; Web-based computing; abelian monoids; collaborative computing; competing schedules; computation-DAG; directed acyclic graph; formal criterion; pebble game; scheduling; task-nodes; Abstracts; Collaboration; Collaborative work; Computational complexity; Computer science; Contracts; Grid computing; Internet; Processor scheduling; Registers;
Conference_Titel :
Parallel and Distributed Processing Symposium, 2003. Proceedings. International
Print_ISBN :
0-7695-1926-1
DOI :
10.1109/IPDPS.2003.1213078