A Pebble Game for Internet-Based Computing

  • Grzegorz Malewicz
  • Arnold L. Rosenberg
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


Advances in technology have rendered the Internet a viable medium for employing multiple independent computers collaboratively in the solution of a single computational problem, leading to the new genre of collaborative computing that we term Internet-based computing (IC). Scheduling a computation for IC presents challenges that were not encountered with earlier modalities of collaborative computing, especially when the computation’s constituent tasks have interdependencies that constrain their order of execution. This paper surveys an ongoing study of (an abstraction of) the scheduling problem for such computations for IC. The work employs a “pebble game on computation-dags,” that abstracts the process of allocating a computation’s interdependent tasks to participating remote computers. The goal of a schedule, motivated by two related scheduling challenges, is to maximize the production rate of tasks that are eligible for execution. First, in many modalities of IC, remote computers become available at unpredictable times. Always having a maximal number of execution-eligible tasks enhances the utilization of available resources. Second, the fact that remote computers are often not dedicated to this IC computation, hence, may be more dilatory than anticipated, can lead to a type of “gridlock” that results when a computation stalls because (due to dependencies) all execution-eligible tasks are already allocated to remote computers. These motivating challenges raise the hope that the optimality results presented here within an abstract IC setting have the potential of improving efficiency and fault-tolerance in real IC settings.


Schedule Problem Optimal Schedule Schedule Strategy Priority Relation Remote Computer 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Buyya, R., Abramson, D., Giddy, J.: A case for economy Grid architecture for service oriented Grid computing. In: 10th Heterogeneous Computing Wkshp (2001)Google Scholar
  2. 2.
    Cirne, W., Marzullo, K.: The Computational Co-Op: gathering clusters into a metacomputer. In: 13th Intl. Parallel Processing Symp. pp. 160–166 (1999)Google Scholar
  3. 3.
    Cook, S.A.: An observation on time-storage tradeoff. J. Comp. Syst. Scis. 9, 308–316 (1974)zbMATHCrossRefGoogle Scholar
  4. 4.
    Cordasco, G., Malewicz, G., Rosenberg, A.L.: On scheduling expansive and reductive dags for Internet-based computing (2005) (Submitted for publication)Google Scholar
  5. 5.
    Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)zbMATHGoogle Scholar
  6. 6.
    Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a New Computing Infrastructure, 2nd edn. Morgan-Kaufmann, San Francisco (2004)Google Scholar
  7. 7.
    Foster, I., Kesselman, C., Tuecke, S.: Tuecke: The anatomy of the Grid: enabling scalable virtual organizations. Intl. J. High Performance Computing Applications 15, 200–222 (2001)CrossRefGoogle Scholar
  8. 8.
    Gerasoulis, A., Yang, T.: A comparison of clustering heuristics for scheduling dags on multiprocessors. J. Parallel Distr. Comput. 16, 276–291 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    He, L., Han, Z., Jin, H., Pan, L., Li, S.: DAG-based parallel real time task scheduling algorithm on a cluster. In: Intl. Conf. on Parallel and Distr, Processing Techniques and Applications pp. 437–443 (2000)Google Scholar
  10. 10.
    Hong, J.-W., Kung, H.T.: I/O complexity: the red-blue pebble game. In: 13th ACM Symp. on Theory of Computing, pp. 326–333 (1981)Google Scholar
  11. 11.
    Hopcroft, J.E., Paul, W., Valiant, L.G.: On time versus space. J. ACM 24, 332–337 (1977)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Hsu, H.T.: An algorithm for finding a minimal equivalent graph of a digraph. J. ACM 22, 11–16 (1975)zbMATHCrossRefGoogle Scholar
  13. 13.
    Kondo, D., Casanova, H., Wing, E., Berman, F.: Models and scheduling guidelines for global computing applications. In: Intl. Parallel and Distr. Processing Symp., vol. 79 (2002)Google Scholar
  14. 14.
    Korpela, E., Werthimer, D., Anderson, D., Cobb, J., Lebofsky, M.: SETI@home: massively distributed computing for SETI. In: Dubois, P.F. (ed.) Computing in Science and Engineering, IEEE Computer Soc. Press, Los Alamitos (2000)Google Scholar
  15. 15.
    Malewicz, G., Rosenberg, A.L.: On batch-scheduling dags for Internetbased computing. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol. 3648, pp. 262–271. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  16. 16.
    Malewicz, G., Rosenberg, A.L., Yurkewych, M.: Toward a theory for scheduling dags in Internet-based computing. IEEE Trans. Comput. (2005); See also: On scheduling complex dags for Internet-based computing. Intl. Parallel and Distributed Processing Symp. (2005) (to appear)Google Scholar
  17. 17.
    Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Project MAC Conf. on Concurrent Systems and Parallel Computation, pp. 119–127. ACM Press, New York (1970)Google Scholar
  18. 18.
    Pippenger, N.J.: Pebbling. In: 5th IBM Symp. on Math, Foundations of Computer Science (1980)Google Scholar
  19. 19.
    Rosenberg, A.L.: On scheduling mesh-structured computations for Internetbased computing. IEEE Trans. Comput. 53, 1176–1186 (2004)CrossRefGoogle Scholar
  20. 20.
    Rosenberg, A.L., Sudborough, I.H.: Bandwidth and pebbling. Computing 31, 115–139 (1983)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Rosenberg, A.L., Yurkewych, M.: Guidelines for scheduling some common computation-dags for Internet-based computing. IEEE Trans. Comput. 54, 428–438 (2005)CrossRefGoogle Scholar
  22. 22.
    Sun, X.-H., Wu, M.: Grid Harvest Service: a system for long-term, application-level task scheduling. In: IEEE Intl. Parallel and Distributed Processing Symp. vol. 25 (2003)Google Scholar
  23. 23.
    White, S.W., Torney, D.C.: Use of a workstation cluster for the physical mapping of chromosomes. SIAM NEWS, 14–17 (March 1993)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Grzegorz Malewicz
    • 1
  • Arnold L. Rosenberg
    • 2
  1. 1.Google, Inc. 
  2. 2.Dept. of Computer ScienceUniversity of MassachusettsAmherstUSA

Personalised recommendations