Nondeterministic Queries in a Relational Grid Information Service

ABSTRACT

A Grid Information Service (GIS) stores information about the resources of a distributed computing environment and answers questions about it. We are developing RGIS, a GIS system based on the relational data model. RGIS users can write SQL queries that search for complex compositions of resources that meet collective requirements. Executing these queries can be very expensive, however. In response, we introduce the nondeterministic query, an extension to the SELECT statement, which allows the user (and RGIS) to trade off between the query's running time and the number of results. The results are a random sample of the deterministic results, which we argue is sufficient and appropriate. Herein we describe RGIS, the nondeterministic query extension, and its implementation. Our evaluation shows that a meaningful tradeoff between query time and results returned is achievable, and that the tradeoff can be used to keep query time largely independent of query complexity.

REFERENCES

• 1: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.186-201, December 12-15, 1999, Charleston, South Carolina, United States
• 2: Paul Albitz, DNS and BIND, O'Reilly & Associates, Inc., Sebastopol, CA, 2001
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 5: Steven Fitzgerald, Grid Information Services for Distributed Resource Sharing, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.181, August 07-09, 2001
• 6: [6] DINDA, P., AND PLALE, B. A unified relational approach to grid information services. Tech. Rep. GWD-GIS-012-1, Global Grid Forum, February. Informational Draft.
• 7: [7] DINDA, P. A., AND O'HALLARON, D. R. An extensible toolkit for resource prediction in distributed systems. Tech. Rep. CMU-CS-99-138, School of Computer Science, Carnegie Mellon University, July 1999.
• 8: [8] DOAR, M. A better model for generating test networks. In Proceedings of GLOBECOM '96 (November 1996).
• 9: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 10: Renato J. Figueiredo , Peter A. Dinda , José A. B. Fortes, A Case For Grid Computing On Virtual Machines, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.550, May 19-22, 2003
• 11: [11] FISHER, S. Relational model for information and monitoring. Tech. Rep. Informational Draft GWD-GP-7-1, Grid Forum, 2001.
• 12: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 13: Ian Foster , Carl Kesselman , Jeffrey M. Nick , Steven Tuecke, Grid Services for Distributed System Integration, Computer, v.35 n.6, p.37-46, June 2002 [doi>10.1109/MC.2002.1009167]
• 14: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 15: [15] GLOBAL GRID FORUM. Global grid forum web site. http://www.gridforum.org.
• 16: [16] IBM INTERNATIONAL TECHNICAL SUPPORT ORGANIZATION. Understanding LDAP. IBM Corporation, 1998.
• 17: [17] INTERNATIONAL TELECOMMUNICATION UNION. Information technology - open systems interconnection - the directory: Overview of concepts, models, and services, August 1997.
• 18: Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
• 19: [19] LIU, C., AND FOSTER, I. A constraint language approach to grid resource selection. Tech. Rep. TR-2003-07, Department of Computer Science, University of Chicago, March 2003.
• 20: Bruce Lowekamp , David O'Hallaron , Thomas Gross, Topology discovery for large ethernet networks, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.237-248, August 2001, San Diego, California, United States
• 21: Dong Lu , Peter A. Dinda, Synthesizing Realistic Computational Grids, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.16, November 15-21, 2003
• 22: Dong Lu , Peter A. Dinda , Jason A. Skicewicz, Scoped and Approximate Queries in a Relational Grid Information Service, Proceedings of the Fourth International Workshop on Grid Computing, p.192, November 17-17, 2003
• 23: [23] OBJECT MANAGEMENT GROUP. The common object request broker: Architecture and specification (version 2.3.1). Tech. rep., Object Management Group, 1999.
• 24: [24] OLKEN, F. Random Sampling from Databases. PhD thesis, University of California, Berkeley, 1993.
• 25: [25] PLALE, B., DINDA, P., AND VON LASZEWSKI, G. Key concepts and services of a grid information service. In Proceedings of the 15th International Conference on Parallel and Distributed Computing Systmes (PDCS 2002) (2002).
• 26: R. Raman , M. Livny , M. Solomon, Matchmaking: Distributed Resource Management for High Throughput Computing, Proceedings of the 7th IEEE International Symposium on High Performance Distributed Computing, p.140, July 28-31, 1998
• 27: Rajesh Raman , Miron Livny , Marvin Solomon, Resource Management through Multilateral Matchmaking, Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing, p.290, August 01-04, 2000
• 28: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 29: Warren Smith , Abdul Waheed , David Meyers , Jerry Yan, An Evaluation of Alternative Designs for a Grid Information Service, Cluster Computing, v.4 n.1, p.29-37, March 2001 [doi>10.1023/A:1011460125780]
• 30: 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
• 31: Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Query Rewriting for SWIFT (First) Answers, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.694-714, September 2000 [doi>10.1109/69.877503]
• 32: [32] THE OPEN GROUP. DCE 1.2.2: Introduction to OSF DCE. The Open Group, September 1997. http://www.opengroup.org/pubs/catalog/f201.htm.
• 33: Marvin Theimer , Michael B. Jones, Overlook: Scalable Name Service on an Overlay Network, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.52, July 02-05, 2002
• 34: [34] TRANSACTION PROCESSING COUNCIL. Tpc benchmarks. http://www.tpc.org.
• 35: Amin Vahdat , Michael Dahlin , Thomas Anderson , Amit Aggarwal, Active names: flexible location and transport of wide-area resources, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.14-14, October 11-14, 1999, Boulder, Colorado
• 36: J. Veizades , E. Guttman , C. Perkins , S. Kaplan, Service Location Protocol, RFC Editor, 1997
• 37: Jim Waldo, The Jini architecture for network-centric computing, Communications of the ACM, v.42 n.7, p.76-82, July 1999 [doi>10.1145/306549.306582]