ML grid programming with ConCert

ABSTRACT

Grid computing has become increasingly popular with the growth of the Internet, especially in large-scale scientific computation. Computational Grids are characterized by their scale, their heterogeneity, and their unreliability, making the creation of Grid software quite a challenge. Security concerns make the deployment of Grid infrastructure similarly daunting.We argue that functional programming techniques, both well-known and new, make an excellent practical foundation for Grid computing. We present a prototype Grid framework called ConCert built entirely in Standard ML which allows for the trustless dissemination of Grid programs through the use of certified code. The framework is fault-tolerant and relatively easy to implement, owing to a simplified network abstraction. This network abstraction is tedious to program for directly, so we present a high level ML-like language Grid/ML and a compiler Hemlock for the language.

REFERENCES

• 1: GIMPS, the great internet mersenne prime search, http://mersenne.org/.
• 2: SETI@Home, http://setiathome.ssl.berkeley.edu/.
• 3: The third annual ICFP programming contest, http://www.cs.cornell.edu/icfp/.
• 4: Secure hash standard, August 2002. FIPS 180-2, National Institute of Standards and Technology.
• 5: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 6: Robert D. Blumofe and Philip A. Lisiecki. Adaptive and reliable parallel computing on networks of workstations. In Proceedings of the USENIX 1997 Annual Technical Conference on UNIX and Advanced Computing Systems, pages 133--147, 1997.
• 7: Bor-Yuh Evan Chang , Karl Crary , Margaret DeLap , Robert Harper , Jason Liszka , Tom Murphyø, VII , Frank Pfenning, Trustless Grid Computing in ConCert, Proceedings of the Third International Workshop on Grid Computing, p.112-125, November 18, 2002
• 8: Bor-Yuh Evan Chang. Iktara in ConCert: Realizing a certified grid computing framework from a programmer's perspective. Technical Report CMU-CS-02-150, Carnegie Mellon, 2002.
• 9: T. Chothia and D. Duggan. An architecture for secure fault-tolerant global applications. In Workshop on Principles of Dependable Systems (PODSY). IEEE Press, June 2003.
• 10: Silvain Conchon , Fabrice Le Fessant, Jocaml: Mobile Agents for Objective-Caml, Proceedings of the First International Symposium on Agent Systems and Applications Third International Symposium on Mobile Agents, p.22, October 03-06, 1999
• 11: Karl Crary. Toward a foundational typed assembly language. Technical Report CMU-CS-02-196, Department of Computer Science, Carnegie Mellon University, December 2002.
• 12: Michael W. Hicks , Stephanie Weirich , Karl Crary, Safe and Flexible Dynamic Linking of Native Code, Selected papers from the Third International Workshop on Types in Compilation, p.147-176, September 21, 2000
• 13: Karl Crary , Stephanie Weirich, Flexible type analysis, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.233-248, September 27-29, 1999, Paris, France
• 14: Ian Foster , Carl Kesselman, The globus project: a status report, Future Generation Computer Systems, v.15 n.5-6, p.607-621, Oct. 1999 [doi>10.1016/S0167-739X(99)00013-8 ]
• 15: Cédric Fournet , Georges Gonthier, The reflexive CHAM and the join-calculus, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.372-385, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237805]
• 16: Robert Harper , Greg Morrisett, Compiling polymorphism using intensional type analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199475]
• 17: Graham Hutton. Higher-order functions for parsing. Journal of Functional Programming, 2(3):323--343, July 1992.
• 18: David B. Johnson , Willy Zwaenepoel, Recovery in distributed systems using asynchronous message logging and checkpointing, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.171-181, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62575]
• 19: B. Kuszmaul. The StarTech massively parallel chess program. Journal of the International Computer Chess Association, 18(1):3--19, 1995.
• 20: Clarence Irving Lewis. A Survey of Symbolic Logic. University of California Press, 1918.
• 21: Greg Morrisett, Karl Crary, Neal Glew, Dan Grossman, Richard Samuels, Frederick Smith, David Walker, Stephanie Weirich, and Steve Zdancewic. TALx86: A realistic typed assembly language. In 1999 ACM SIGPLAN Workshop on Compiler Support for System Software, pages 25--35, Atlanta, Georgia, May 1999.
• 22: Tom Murphy, VII. Modal types for mobile code (thesis proposal). Technical Report CMU-CS-06-112, Carnegie Mellon, Pittsburgh, Pennsylvania, USA, Feb 2006.
• 23: Tom Murphy, VII, Karl Crary, Robert Harper, and Frank Pfenning. A symmetric modal lambda calculus for distributed computing. Technical Report CMU-CS-04-105, Carnegie Mellon University, Mar 2004.
• 24: Tom Murphy, VII and Amit K. Manjhi. Anonymous identity and trust in peer-to-peer networks. http://www.cs.cmu.edu/~tom7/papers/.
• 25: D. Plainfosse , M. Shapiro, Survey of Distributed Garbage Collection Techniques, University of Bologna, 1994
• 26: Peter Sewell , James J. Leifer , Keith Wansbrough , Francesco Zappa Nardelli , Mair Allen-Williams , Pierre Habouzit , Viktor Vafeiadis, Acute: high-level programming language design for distributed computation, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 27: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 28: Valery Trifonov , Bratin Saha , Zhong Shao, Fully reflexive intensional type analysis, ACM SIGPLAN Notices, v.35 n.9, p.82-93, Sept. 2000
• 29: Joseph Vanderwaart and Karl Crary. Foundational typed assembly language for grid computing. Technical Report CMU-CS-04-104, Department of Computer Science, Carnegie Mellon University, February 2004.
• 30: Xiaoyun Wang, Yiqun Yin, and Hongbo Yu. Finding collisions in the full sha-1. In Crypto '05, August 2005.
• 31: Stephanie Weirich, Type-safe cast: (functional pearl), Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.58-67, September 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Languages, Reliability, Security

Keywords:
certified code, compilers, distributed computing, functional programming, grid computing