Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-15
2004-06-15
Le, Uyen (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S203000
Reexamination Certificate
active
06751619
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to distributed computer systems and, more particularly, to the management of entries in a data structure that are accessible by multiple entities.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright© 1999-2000, Microsoft Corporation, and All Rights Reserved.
BACKGROUND OF THE INVENTION
A distributed computer system, such as but not limited to the Internet, is characterized by rapid, real-time interchange among many dissimilar processes executing simultaneously on a large array of dissimilar and geographically diverse processors. A distributed computer system's resources are usually spatially separated, and the execution of its applications often involves multiple execution threads that can be widely separated in time. To address some of the challenges of writing applications for use on distributed computer systems, tuple space based coordination languages were developed.
The first tuple space based coordination language was Linda, a language that was originally developed by Dr. David Gelernter. See, for example, “Linda In Context”, N. Carriero and D. Gelernter, Communications of the ACM, 32(4): 444-458, 1989; and N. Carriero and D. Gelernter, “Tuple Analysis and Partial Evaluation Strategies in the Linda Precompiler”, in
Languages and Compilers for Parallel Computing, Research Monographs in Parallel and Distributed Computing,
D. Gelernter, A. Nicolau, and D. Padua, editors, MIT Press, 1990, pages 114-125.
A “tuple space” is a globally shared, associatively addressed memory space that is organized as a grouping of tuples. A “tuple” is the basic element of a tuple space system. In the context of a tuple space based coordination language like Linda, a tuple is a vector having fields or values of certain types. In a broader sense, a “tuple” is an entry in an information storage system. For example, a row in a relational database system can be referred to as a tuple.
In Linda-like languages, constructs called “templates” are used to associatively address tuples via matching techniques. A template matches a tuple if they have an equal number of fields and if each template field matches the corresponding tuple field.
Tuple space based coordination languages provide a simple yet powerful mechanism for inter-process communication and synchronization, which is the crux of parallel and distributed programming. A process with data to share generates a tuple and places it into the tuple space. A process requiring data simply requests a tuple from the tuplespace.
Although not quite as efficient as message-passing systems, tuple space programs are typically easier to write and maintain for a number of reasons including the following:
(1) Destination uncoupling (fully anonymous communication)—the creator of a tuple requires no knowledge about the future use of that tuple or its destination.
(2) Spatial uncoupling—because tuples are retrieved using an associative addressing scheme, multiple address-space-disjoint processes can access tuples in the same way.
(3) Temporal uncoupling—tuples have their own life span, independent of the processes that generated them or any processes that may read them. This enables time-disjoint processes to communicate seamlessly.
Research into tuple space systems has proceeded at a steady pace for the past fifteen years, but its focus has been primarily on high-performance parallel computing systems. Recently, interest in tuple space has developed among researchers in distributed systems. For example, SUN Microsystems, Inc. has released as part of the Jini connection technology, a language based on a tuple space based coordination language called Javaspaces, as described in the JavaSpaces Specification, Version 1.0.1, Sun Microsystems, Inc., 1999. Some other known implementations and derivatives of the Linda language are WCL, PageSpace, TuSCon, Jada, TSpaces, KLAIM, Lime, C-Linda, Paradise, Melinda, Ease, Lucinda, FORTRAN-Linda, LindaLISP, and Prolog-Linda.
Tuple space based coordination languages can provide the essential features (spatial and temporal separation) required for many different types of distributed applications, especially for use over the Internet. Developed by scientists and academicians, the Internet was originally used to share research information and to collaborate. However, the Internet now encompasses millions of world-wide computers networked together.
The Internet functions as an object-based multimedia system. It allows for the creation, storage, and delivery of multimedia objects. Numerous on-line service providers, such as Microsoft Network, CompuServe, Prodigy, and America Online, have linked to the Internet. This enables their customers to access a variety of products and services available from independent content providers and other Internet users. For example, a typical customer can access electronic mail, news services, travel services, investment and banking services, online stores and malls, entertainment services, and many other services on the Internet.
There are two distinct types of implementations of tuple space based coordination languages (e.g. Linda), characterized as being either “closed” or “open”. The closed implementations use compile time analysis of object and source code to provide highly efficient closed programs. The open implementations allow processes, agents, and programs to coordinate through tuple spaces without the run-time system requiring any prior knowledge. Essentially, the open implementations provide a persistent data store.
The Linda language uses three standard instructions or primitives. These are (with their informal semantics):
(1) out(tuple) Insert a tuple into a tuple space.
(2) in(template) If a tuple exists that matches the template, then remove the tuple and return it to the agent performing the in. If no matching tuple is available, then the primitive blocks until a matching tuple is available.
(3) rd(template) If a tuple exists that matches the template, then return a copy of the tuple to the agent that performed the rd. If there is no matching tuple, then the primitive blocks until a matching tuple is available.
The informal semantics of the in primitive leads implementers to remove the tuple that is returned to the agent from the tuple space when the in primitive is performed. However, this causes an efficiency problem in a distributed computer system where multiple users may be concurrently trying to access a particular tuple, because they can be blocked from accessing the tuple until a matching tuple is available.
Thus there is a significant need to modify existing tuple space based coordination languages to improve their efficiency of execution on large, open implementations, particularly on distributed computer systems, so that users are not unnecessarily blocked from accessing tuples.
There is also a significant need to modify existing tuple space based coordination languages to improve their efficiency of execution on closed implementations, particularly on high-performance parallel computer systems, so that users are not unnecessarily blocked from accessing tuples.
SUMMARY OF THE INVENTION
The above-mentioned shortcomings, disadvantages, and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
The present invention includes a number of different aspects for improving the performance of a data processing system. For the purposes of describing this invention, the term “performance” is intended to include within its meaning not only the operational performance, but also the function, structure, operatio
De Nicola Rocco
Rowstron Antony Ian Taylor
Amin & Turocy LLP
Chen Te Yu
Le Uyen
Microsoft Corporation
LandOfFree
Methods and apparatus for tuple management in data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for tuple management in data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for tuple management in data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338728