Electrical computers and digital processing systems: multicomput – Distributed data processing
Reexamination Certificate
1999-05-05
2003-04-22
Dinh, Dung C. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Distributed data processing
C707S793000
Reexamination Certificate
active
06553402
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system and method for coordinating activities and sharing information between networked software entities. More specifically, the invention is directed towards implementing data exchange for such purposes using a data definition language.
2. Background of the Related Art
The continuing development of parallel and distributed computing models brings with it issues of how to efficiently share information between networked or linked processors. One possible solution to this problem is Linda, a coordination language (as opposed to a computation language such as C or FORTRAN) proposed by Nicholas Carriero and David Gelernter of Yale University. Linda is based on a logically associative object memory model called a tuple space. A tuple space is a virtual shared memory model which provides interprocess communication and synchronization logically independent of the underlying computer system or network on which it resides. It uses a small number of simple operations on the tuple space to create and coordinate parallel processes which can simply exchange information.
The tuple space is so named because the fundamental data structure which populates it is called a tuple. A tuple is an ordered set of one or more fields with values, e.g., (sweater, wool, xxl-tall). Linda may use pattern-tuples, which are partially-specified tuples denoted with wild cards, e.g., (sweater, wool, ?). There are four basic operations on tuples in tuple space:
for tuple generation, the operation out(tuple) is a non-blocking call (it does not stall program execution) that generates a data tuple (a tuple having static data) having specified values and puts it into tuple space. Control then returns to the invoking program. For example, the operation call
out(shirt, cotton, med)
puts a tuple (shirt, cotton, med) into a given tuple space.
also for tuple generation, the operation eval(tuple) generates a process tuple (a tuple under active evaluation) and returns. For arguments of the tuple which are a function call, conceptually processes are created to evaluate the functions. The results returned by the functions are substituted for the function calls in the tuple, and the tuple is placed into tuple space. For example, the operation call
eval(‘inventory’, ii, inventory(ii))
might create a tuple which calls the function inventory to inventory the number of tuples having a certain field value of i. The result would be a data tuple in the tuple space which has the inventory result as its last field value.
for tuple extraction, the operation in(pattern-tuple) is a blocking call (it may stall program execution) which uses pattern-tuple to retrieve a tuple from the tuple space. The tuple is removed from the tuple-space and is no longer available for use by other processes. If no matching tuple is in the tuple space, the operation will stall until one becomes available. For example, the operation call
in(pants, ?material, large) might look for all “large pants” tuples regardless of the material from which they are made. When and if it matches a tuple in tuple space, the value of the tuple's middle field will be assigned to material.
also for tuple extraction, the operation rd(pattern-tuple) is a blocking call that retrieves a copy of a matching tuple from the tuple space but leaves the original tuple in the tuple space. Thus, it may be thought of as a non-destructive version of in.
The Linda paradigm is both powerful and elegant, subsuming and organizing in a clean way some important issues in parallel and distributed computation and coordination. It has demonstrated its utility in a variety of applications involving coordinated software entities. For example, Linda forms the basis for a number of network device attachment and operation models. In particular, Linda features have been incorporated into several Java-based systems such as JavaSpaces, which forms a part of Sun Microsystems' Jini system; T Spaces from IBM Almaden Research laboratories; Java Paradise from Scientific Computing Associates, and Jada from the University of Bologna.
Unfortunately, these various Java implementations of Linda are not compatible with one another in the particulars of the entries which they store in their respective tuple spaces. This diminishes the potential for harmonious interoperation between systems speaking the various different dialects of Linda. Even if the different derivative implementations were mutually compatible, they all assume a language-based tuple space of Java objects and are not compatible with, e.g., non-Java based implementations.
SUMMARY OF THE INVENTION
With the above problems of the prior art in mind, it is an object of the present invention to provide a system and method for coordinating activities and sharing information among networked software entities.
It is a further object of the present invention to provide a unifying framework and standard for coordination and information sharing among networked software entities.
It is yet another object of the present invention to provide a system and method for combining networked tuple-spaces into larger distributed tuple-spaces without limit by exploiting the uniform representation which all tuple spaces share.
The above objects are achieved according to a first aspect of the invention by applying a widely-used data definition language such as the Extensible Markup Language (XML) to the domain of tuple space-based coordination mechanisms. With XML, for example, entries and template entries (similar to tuples and pattern tuples in Linda) are instances of XML Document Type Definitions (DTDs). These entries can represent any type of networked or network-proxied resource, object or service. Using this framework, diverse entry spaces can be aggregated and operated upon as though they were a single large entry space. The flexibility and power of XML constructs can be leveraged to make such aggregation straightforward and efficient.
REFERENCES:
patent: 5774660 (1998-06-01), Brendel et al.
patent: 5860010 (1999-01-01), Attal
patent: 5963947 (1999-10-01), Ford et al.
patent: 5964841 (1999-10-01), Rekhter
patent: 5974420 (1999-10-01), Lehman et al.
patent: 6029160 (2000-02-01), Cabrera et al.
patent: 6094673 (2000-07-01), Dilip et al.
patent: 6112242 (2000-08-01), Jois et al.
patent: 6115715 (2000-09-01), Traversat et al.
patent: 6119157 (2000-09-01), Traversat et al.
patent: 6151624 (2000-11-01), Teare et al.
patent: 6195652 (2001-02-01), Fish
patent: 6301584 (2001-10-01), Ranger
Sun, J.; Mayfield, J.; “Searching the World-Wide Web Using Signature Files,” Computer Science and EE Dept., University of Maryland Baltimore County, Baltimore, MD (no date).
Linda User's Guide & Reference Manual, Version 0.3,Scientific Computing Associates, 1/95.
Internet Publication http://www.w3.org/TR/REC-xml, Apr. 3, 1999, pp. 1-37.
A. I. T. Rowstron et al., “Bonita: A set of tuple space primitives for distributed coordination,” IEEE System Sciences Proceedings 1997, pp. 379-388.
Widergren et al., “XML for Data Exchange,” Power Engineering Society Meeting, Jul. 1999, IEEE pp. 840-842.
Downs Heather L.
Fitzwilson Robert C.
Makarios Selene K.
Dinh Dung C.
Nextpage, Inc.
Skjerven Morrill LLP
LandOfFree
Method for coordinating activities and sharing information... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for coordinating activities and sharing information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for coordinating activities and sharing information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3062340