System and method for distributed computation based upon the movement, execution, and interaction of processes in a network

Abstract

A distributed computing environment in which agent processes direct their own movement through a computer network. Place processes provide a computing context within which agent processes are interpreted. An agent process controls its movement from one place process to another within the network by using a ticket. An agent process which moves from one place process to another transports definitions of classes of which objects included in the agent process are members. An agent process which moves from one place process to a second place process avoids unnecessary transportation of objects included in the agent process by substituting equivalent objects which are found in the second place process. An agent process sends clones of the agent process to several place processes simultaneously. If two clones travel along paths which are coextensive for an initial portion thereof, a single clone is transported along the initial portion of the paths and other clones are formed from the single clone, thereby avoiding transferring redundant information along communications media. Two agent processes, which occupy a single place process, interact by exchanging references to one another. The single place process ensures that neither agent process receives a reference to the other agent process without simultaneously giving to the other agent process a reference to the former agent process. Unauthorized or inadvertent excessive use of network resources by an agent process, or a place process, is prevented by associating with each process a permit which defines various capabilities and resource allowances of the process.

Claims

What is claimed is:

1. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer, said method comprising:

(a) executing a process on said first computer wherein said process comprises instructions from a computer instruction set and said process owns an object; and

(b) transferring said object to said second computer in response to an instruction in said instructions so that said object can be utilized on said second computer.

2. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 1 wherein said object is said process.

3. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 1 wherein said object is a class.

4. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 1 wherein said object is a message.

5. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 1 wherein said computer instruction set is an object-oriented computer instruction set.

6. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 5 wherein said object is defined by said object-oriented computer instruction set.

7. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 1 wherein said instruction is a go instruction.

8. In a heterogeneous computer network having one or more computers, a method for transferring objects from a first computer to a second computer as in claim 1 wherein said instruction is a send instruction and transferring said object comprises transferring a clone of said object.

9. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer, said method comprising:

(a) executing a process on a first computer wherein said process comprises instructions from a computer instruction set and said process owns said data;

(b) suspending execution of said process on said first computer in response to an instruction in said instructions;

(c) transferring said process including said data from said first computer to said second computer; and

(d) resuming execution of said process on said second computer to affect transfer of said data to said second computer.

10. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer as in claim 9 wherein said data includes an object.

11. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer as in claim 9 wherein said data includes a class.

12. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer as in claim 9 wherein said data includes a message.

13. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer as in claim 9 wherein said computer instruction set is an object-oriented computer instruction set.

14. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer as in claim 9 wherein said instruction is a go instruction.

15. In a computer network having one or more computers, a method for transferring data from a first computer to a second computer as in claim 9 wherein said instruction is a send instruction and transferring said process comprises transferring a clone of said process.

Description

CROSS REFERENCE TO MICROFICHE APPENDIX

Appendix E, which is a part of this disclosure, is a microfiche appendix consisting of one (1) sheet of microfiche having a total of five (5) frames. Microfiche Appendix E describes the interchange of objects during the movement of a process through a network in one embodiment of the present invention, which is described more completely below.

Appendix F, which is a part of this disclosure, is a microfiche appendix consisting of one (1) sheet of microfiche having a total of 51 frames. Microfiche Appendix F describes the transfer of data between computer systems interconnected via a network in one embodiment of the present invention.

Appendix G, which is a part of this disclosure, is a microfiche appendix consisting of 13 sheets of microfiche having a total of 1,185 frames. Microfiche Appendix G is a list of computer programs and related data in one embodiment of the present invention, which is described more completely below.

A portion of the disclosure of this patent document contains material which 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 files or records, but otherwise reserves all copyright rights whatsoever.

FIELD OF THE INVENTION

This invention relates to a distributed computing environment and in particular, to an improved distributed computing environment wherein processes are created in an object oriented environment and direct their own movement throughout a computer network.

BACKGROUND OF THE INVENTION

Many different computing systems are available today, but most of these systems are built around fundamental components such as those illustrated in FIG. 1. Typically, a computer system 20 includes a central processing unit 10 (CPU), which is connected through an input bus 11 to an input module 12 and through an output bus 13 to an output module 14. CPU 10 is also connected through data buses 15, 16 to a memory unit 17.

CPU 10 provides control and computing functions. Input and output modules 12, 14 are used to communicate between the computer user and CPU 10. Input module 12 supplies information to CPU 10. Typical input devices are a keyboard and a mouse. Output module 14 displays information from central processing unit 10. Typical output modules include video display monitors, printers, plotters and other visual display means. Input unit 12 and output unit 14 are frequently referred to as input/output (I/O) units.

Memory unit 17 typically contains two general types of information, instructions and data. A computer program is a sequence of instructions that are executed by the computer to perform a specific function. Data in memory unit 17 are processed by CPU 10 in response to the instructions from a computer program which is executing in CPU 10. An executing computer program is called a computer process.

Memory unit 17 typically includes mass memory 17A, sometimes called secondary memory, and main memory 17B. Main memory 17B is usually used to store at least a portion of a program currently being executed by CPU 10 and data required by the program. Mass memory 17A, e.g. magnetic disk or tape, is used to store programs, data, or portions of either programs or data which are not needed immediately by CPU 10 or which cannot be accommodated in main memory 17B because of size limitations of main memory 17B.

The operating system of a computer is a computer process which coordinates operation of CPU 10, I/O devices 12, 14 and 17A and main memory 17B and which provides an interface between user applications (defined below) and computer hardware. As is used herein, the term computer hardware refers to the physical components of the computer system. As an operating system is necessary for the orderly operation of a computer system, the operating system is loaded into main memory 17B and executed during power up of the computer system (a process called "booting") and remains in main memory 17B and in execution until the computer system is ultimately deactivated.

A user application generally refers to a computer process which executes in addition to, and is generally considered distinct from, the operating system. A user application begins at some point in time as source code, i.e., computer instructions in a form intelligible to human beings. This source code is translated or "compiled" into object code, which is a form intelligible to computer system 20, particularly CPU 10. Several object code modules may be linked to form a single executable image, which is in a form which can be processed by CPU 10 of computer system 20. The program is executed by copying the executable image into main memory 17B and instructing CPU 10 to carry out the instructions, one by one, of the executable image. As stated above, a computer program in such state of execution is called a process.

The instructions executed by a process executing within computer system 20 generally manipulate the resources of computer system 20. For example, instructions can manipulate data stored in mass memory 17A, accept data from input module 12 or display data on output module 14. Some processes, which are designed to execute on a first computer system, are configured to issue computer instructions which manipulate resources of a second computer system.

It is well-known in the art of computer communications to connect two or more computer systems such that data can be transferred between two or more computer systems. Two or more computer systems so connected are collectively called a "network". In such a network, each computer system treats each other computer system as an I/O device to which data can be sent and from which data can be received.

A first process executing on a first computer system can issue instructions to a second process executing on a second computer system. The second process then manipulates the resources of the second computer system in accordance with the instructions received from the first process. The second process is called a "server" process because the second process provides a service to the first process, which is called a "client" process. The service provided is the manipulation of resources of the second computer system.

Many computer communication systems implement what is called "remote procedure calling". In remote procedure calling, a client process, which is executing on a first computer system and which seeks to manipulate data on a second computer system, requests action through a server process, which is executing on the second computer system and which manipulates data in response to requests from the client process. The server process performs any of an inevitably finite list of operations on behalf of the client process. Often it is the case that the precise function requested by the client process is not among the particular operations performed by the server process. To perform a function for which no server process operation is defined requires several requests to and responses from the server process that require substantial use of communications media which in turn involves considerable expense and time.

Logic flow diagram 200 (FIG. 2A) illustrates an example of remote procedure calling. Logic flow diagram 200 is described in the context of computer systems 20A and 20B (FIG. 2B), which are interconnected through network 256. Suppose a client process 252 on computer system 20A is to delete all files on computer system 20B whose names match a given pattern, e.g., file names ending in ".TMP", and which have not been modified in at least 30 days. Client process 252 sends to server process 254 which is executing on computer system 20B a request to list all files in step 21 (FIG. 2A). Arrow 260 (FIG. 2B) represents that request. Processing transfers from step 21 (FIG. 2A) to step 22 in which client process 252 (FIG. 2B) receives the list from server process 254, as shown as arrow 262. Steps 21 and 22 (FIG. 2A) involve two transfers across network communications media.

Double rectangles in FIGS. 2A and 3A indicate information transfer across network 256 (FIG. 2B). Whereas execution of an instruction within either computer 20A or computer 20B takes between several nanoseconds to several microseconds, transfer of information across network 256 generally takes seconds or minutes depending on the configuration of network 256 and on the amount of information. In some networks, transfer of a large amount of data can take an hour or more.

Processing transfers from step 22 (FIG. 2A) to for each filename step 23. For each filename step 23 and next steps 23a, 23b and 23c define a loop within which each filename of the list of filenames is processed by the client process. For each filename of the list, processing transfers from for each filename step 23 to a test step 24 in which client process 252 (FIG. 2B) compares the filename to a pattern. If the filename does not match the pattern, processing transfers from test step 24 (FIG. 2A) through next step 23a to for each filename step 23 and the next filename is processed.

Conversely, if the filename matches the pattern, processing transfers from test step 24 to step 25. In step 25, client process 252 (FIG. 2B) sends to server process 254 an instruction to provide the date that the particular file was last modified as shown by arrow 264. Processing transfers from step 25 (FIG. 2A) to step 26 in which client process 252 (FIG. 2B) receives from server process 254 the date requested as represented by arrow 266. Steps 25 and 26 (FIG. 2A) involve two more transfers across network communications media for each such matching filename.

Processing transfers from step 26 to a second test step 27 in which client process 252 (FIG. 2B) compares the date received with the current date less 30 days. If the date indicates that the file has been modified within the preceding 30 days, processing transfers from second test step 27 (FIG. 2A) through next step 23b to for each filename test step 23 in which the next filename is processed. Conversely, if the date indicates that the file has not been modified within the preceding 30 days, processing transfers from second test step 27 to step 28.

In step 28, client process 252 (FIG. 2B) sends to server process 254 an instruction directing server process 254 to delete the file from computer system 20B as represented by arrow 268. Processing transfers from step 28 to step 29 (FIG. 2A), in which client process 252 (FIG. 2B) receives from server process 254 acknowledgement of the deletion as represented by arrow 270. Thus, steps 28 and 29 (FIG. 2A) involve two further transfers across network 256 (FIG. 2B) for each file to be deleted.

Processing transfers from step 29 through next step 23C to for each filename step 23. If all filenames in the list have been processed, processing transfers from for each filename step 23 to terminal step 20b in which processing terminates. Thus, processing according to logic flow diagram 200 (FIG. 2A) requires a multitude of information transfers across network 256. Such heavy use of network communications media is both costly and time consuming.

An alternative approach to remote procedure calling is "remote programming". In remote programming, a process, which is called a "client process" and which executes on a first computer system, sends to a server process executing on the second computer system a list of instructions. The instructions are then carried out by the server process effectuating the goal of the client process. The instructions which the server process is designed to carry out must have some degree of generality; i.e., the instructions must provide some degree of decision-making capabilities.

Logic flow diagram 300 (FIG. 3A) illustrates an example of remote programming. To effectuate the example given above with respect to FIGS. 2A and 2B in a remote programming environment, client process 352 (FIG. 3B) in step 31 (FIG. 3A) builds a program whose instructions are represented by logic flow diagram 31-P. Logic flow diagram 31-P is described below.

Processing transfers from step 31 to step 32, in which the program is transferred to computer 30B (FIG. 3B) through network 356 as represented by arrow 358. Processing transfers from step 32 to step 33 (FIG. 3A) in which the program is executed within computer 30B. During execution, the program is process 352A (FIG. 3B) within computer 30B. The instructions of program 352A are executed according to logic flow diagram 300.

In step 31-B (FIG. 3A), a list of filenames is created. Processing transfers from step 31-B to for each filename step 31-C. For each filename step 31-C and next steps 31-H, 31-I, and 31-J form a loop within which each filename in the list of filenames is processed. For each filename, processing transfers from for each filename step 31-C to test step 31-D in which the filename is compared to a pattern. If the filename does not match the pattern, processing transfers from test step 31-D through next step 31-H to for each step 31-C. Conversely, if the filename matches the pattern, processing transfers from test step 31-D to step 31-E.

In step 31-E, process 352A retrieves the date of last modification of the file having the filename. Processing transfers from step 31-E to a second test step 31-F in which the date is compared to the current date less 30 days. The date of last modification of the file is retrieved from server process 354 (FIG. 3B). If the date of last modification is more recent than the date of 30 days prior, processing transfers from second test step 31-F (FIG. 3A) through next step 31-I to for each filename step 31-C. Conversely, if the date of last modification is prior to the date of 30 days prior, processing transfers from second test step 31-F to step 31-G. In step 31-G, the file is deleted by issuing an appropriate instruction to server process 354 (FIG. 3B). Processing transfers from step 31-G (FIG. 3A) through next step 31-J to for each filename step 31-C. If all filenames in the list have been processed, processing transfers from for each filename step 31-C to terminal step 31-K in which process 352A terminates. As indicated by arrows 360 (FIG. 3B), all interaction between process 352A and server process 354 transpired entirely within computer 30B without use of network 356.

After successful completion of the program, processing transfers from step 33 to step 34 (FIG. 3A) in which server process 354 (FIG. 3B) reports to client process 352 that the program completed successfully as represented by arrow 362. Note that this remote programming procedure involves only two uses of network communications media: a first to send the program or list of instructions to server process 354 as represented by arrow 358 and a second to receive from server process 354 notification of successful completion of the program as represented by arrow 362. Note also that client process 352 was able to request of server process 354 an operation not explicitly provided by, and perhaps not even anticipated by the developers of, server process 354.

However, remote programming encounters the same inefficiencies of remote procedure calling when a computer process seeks to coordinate manipulation of data on two or more computer systems. For example, a process on computer X may seek to delete all files on computer system Y or computer system Z which have the same name, date of last modification and size as any file on computer X. Since server process 354 described above with respect to FIGS. 3A and 3B is capable of directly manipulating resources on the computer system on which the server process is executing, i.e. computer system Y, the server process is unable to coordinate data management spanning more than one computer system without producing the inefficiencies discussed above in conjunction with remote process calling.

An improvement over remote programming is described by C. Daniel Wolfson, et al., "Intelligent Routers", 9th International Conference on Distributed Computing Systems at pp. 371-375 (1989). Woltson et al. disclosed a system wherein a process could move from one computer system to another within a network. The process directed its own movement through the network by issuing an instruction whose execution caused the process to be moved. The instruction specified to which computer system the process was to be moved.

However, the solution in the form disclosed in Wolfson et al. was of limited functionality. Processes were required to be configured to comport with the specific requirements of the computer system to which the respective processes moved. Processes were not able to communicate with one another; processes instead directly stored or directly retrieved data from the mass memory of the computer system within which the respective processes were executing. One process could only interact with another process only if both processes knew the precise location within mass memory where messages were to be stored and/or retrieved.

The system disclosed by Wolfson et al. did not provide any security. Thus, to the extent that the Wolfson et al. system allowed one process to interact with another process, a malicious process could interfere with the execution of a second process. In addition, the set of instructions provided to processes of the system disclosed by Wolfson et al. was very limited; only character string data and numerical data representing real numbers were provided for.

Another system similar to that disclosed by Wolfson et al. was that described by D. Tsichritzis et al., "KNOs: KNowledge Acquisition, Dissemination, and Manipulation Objects", ACM Trans. on Office Information Systems, vol. 5, no. 1, pp. 96-112 (1987). The system described by Tsichritzis et al. added to the system described by Wolfson et al. the generality of object-oriented programming.

Object-oriented programming organizes data and instructions into "objects" in which data represent the "state" of an object and instructions are grouped into tasks or "operations" that the object can "perform". Object-oriented programming represents a very useful conceptual framework in which problems solved by a computer may be more easily reduced to a series of computer instructions.

Objects created in an object-oriented environment are grouped into classes. Objects of a class have states of the same structure and perform the same operations. The system disclosed by Tsichritzis et al. did not provide for the mobility of class definitions; therefore, objects of a given class created within the environment described by Tsichritzis et al. could only travel to those computer systems for which the given class was defined. Additionally, objects in the environment described by Tsichritzis et al. were represented in a form that required that the computer systems of the network, within which objects could travel, were homogeneous.

The system taught by Tsichritzis et al. further described an instruction by which a first process, i.e., a "head" process, could create copies of itself. The copies were called "limbs". Tsichritzis et al. taught that limbs could be sent to remote computer systems at the direction of the head process. However, the limbs were not active; the computer instructions of a limb were executed only at the direction of the head process. Directing the activity of a limb process positioned in a remote computer system required that the head process issue commands to the limbs across network communications media, involving considerable time and expense in large networks.

Further inefficiencies were found in the system taught by Tsichritzis et al. when a small computer, e.g., a personal computer, was connected to a large network through a large computer, e.g., a mainframe computer. For example, to send many limbs to various computers of the network, the small computer was required to send many identical limbs between the small computer and the large computer. As limbs, which are copies of the head process, could be quite large, inefficiencies in such a system could have been quite substantial.

Tsichritzis et al. taught a system wherein a first process communicated with a second process by giving to the second process a reference to the first process. A reference is data which identifies an object and which grants access to the object identified. As the second process contained a reference to the first process, the second process could request that the first process execute specific computer instructions which were contained within the first process. However, as the first process provided the second process with a reference to the first process without simultaneously obtaining a reference to the second process, the second process had access to the first process and the first process did not have reciprocal access to the second process. Such a system permitted a "malicious" process, i.e., a process designed by a malicious programmer or inadvertently designed to harm other processes, to gain access to a second process without granting reciprocal access.

Thus, in spite of the achievements of Wolfson et al. and Tsichristzis et al., neither discloses a system in which new classes of objects and processes can be created and can be transported to and processed by computer systems within the network which do not contain class definitions for the new classes. Neither does either Wolfson et al. or Tsichristzis et al. disclose a mechanism for implementing a complex and hierarchical security scheme. Furthermore, neither Wolfson et al. nor Tsichristzis et al. disclose computer processes which can interact with one another but which cannot gain access to other processes without granting reciprocal access.

Furthermore, neither Wolfson et al. nor Tsichristzis et al. disclose computer processes which can travel to several computer systems simultaneously by creating several autonomous clones of a process and transporting the clones to respective computer systems. The limbs taught by Tsichristzis et al. are not autonomous as the computer process controls the actions of limbs at remote computer systems. Furthermore, neither Wolfson et al. nor Tsichristzis et al. disclose efficient transportation of the clones to the respective computer systems in which transportation of redundant information across network communication media is minimized.

SUMMARY OF THE INVENTION

According to the principles of this invention, a set of interpreted, object-oriented computer instructions is used to create novel computer processes that are executed in a distributed computer system. A particular process that utilizes the set of computer instructions is activated by an engine that is executing within the distributed computer system. The engine interprets and effectuates the instructions of the particular process within the distributed computer system.

Each engine in the distributed computer system interprets the instructions that define a process uniformly. In other words, the instructions which comprise a process and which are interpreted by a first engine do not depend on the particular configuration of the computer system within which the first engine is executing. The instructions, therefore, can be moved to and interpreted by a second engine, even if the first and second engines are executing within two separate computer systems whose operating systems and hardware are otherwise generally incompatible. The interpreted instructions are implemented by using interfaces to communication, storage, computing and other subsystems of the computer system within which the engine is executing. These interfaces, which collectively form part of one embodiment of the present invention, are described in Appendix C, which is a part of this disclosure and is incorporated in its entirety herein by reference.

Two or more engines are interconnected to form a network. The network is a universe within which computer processes of this invention travel. In one embodiment, the network encompasses computer systems that would normally be considered clients of, and not part of, other networks. For example, one embodiment of the network of this invention encompasses the workstations which are connected by the network. The term "workstation" is used herein to describe a computer system which is used for purposes other than the transportation of information to other computer systems. The engines of this invention are interconnected so that engines are capable of moving computer processes among themselves.

To transport a particular computer process, the computer process is suspended and the execution state of the computer process is preserved. The instructions of the computer process, the preserved execution state, and objects owned by the computer process are packaged, or "encoded", to generate a string of data that is configured so that the string of data can be transported by all standard means of communication used to form a network. In one embodiment, the string of data is transported between engines as specified by the protocol described in Appendix D, which is a part of this disclosure and is incorporated herein in its entirety by reference.

Once transported to a destination computer system of the network, the string of data is decoded to generate a computer process within the destination computer system. The decoded computer process includes those objects encoded as described above and has the preserved execution state. The destination computer system resumes execution of the computer process. The instructions of the computer process are executed by the destination computer system to perform complex operations, including defining, creating and manipulating data objects and interacting with other computer processes executed by the destination computer system. As computer processes are uniformly interpretted throughout the network and are encoded and decoded for transport between computer systems, the computer processes of this invention provide a new level of functionality and versatility in intercomputer communication.

In one embodiment, two classes built into the set of computer instructions of this invention are an agent class and a place class. Instructions formed using the agent class are interpreted by an engine to form an "agent process", sometimes referred to herein simply as "an agent". An agent is an active object in that an engine initiates execution of an agent upon creation of the agent. The agent class provides instructions which enable an agent to (i) examine and modify itself, (ii) transport itself from a first place process, which is described more completely below, in the network to a second place process in the network, and (iii) interact with other agents found at the second place process. The first and second place processes can execute within two separate computer systems of the network. Thus, an agent can travel from a first computer system to a second computer system.

An agent can contain information which is carried with the agent from the first place process to the second place process. Additionally, the extensibility, generality and functionality of the set of computer instructions discussed more completely below provide tremendous flexibility and control in determining, according to the instructions which comprise an agent, how and to what destination the agent, and the information contained therein, travels.

The power of agents is counterbalanced by "permits". A permit limits the particular capabilities of a particular agent on particular occasions. The permit of an agent specifies which of several of the operations defined for the agent class can or cannot be performed by the agent. The permit further limits the amount of processing resources the agent can consume and the time at which the agent expires. Additionally, the permit specifies the priority of execution of the agent relative to other agents.

Instructions formed using the place class are interpreted by an engine to form a "place process", sometimes referred to herein simply as "a place". A place is also an active object, and the place class provides instructions which enable a place to examine and modify itself and to serve as a venue for agents and a context in which agents can interact. Agents each occupy a respective single place. Additionally, each place can occupy a single other place.

Places provide a degree of privacy and security for agents. For example, an agent, which is configured to avoid contact with other agents, can occupy a place which is not generally known to other agents, or which denies ingress to other agents. Conversely, an agent, which is configured to provide services publicly to a large number of agents, can occupy a place which is widely known to other agents and which grants ingress to other agents.

Agents cannot interact at a distance; i.e., no two agents can interact unless both occupy the same place. To interact with a second agent occupying a second place, a first agent, which occupies a first place, issues a command causing the first agent to be transported to the second place as discussed below with respect to the "go" operation. While both the first and second agents occupy the second place, the first agent can interact with the second agent.

Thus, the processes of this invention are a novel implementation of "remote programming," and not the more familiar "remote procedure calling" paradigm. Remote programming improves upon remote procedure calling by (i) enabling processes to interact without communicating across network communications media and (ii) improving the performance of the interactions between processes by eliminating communication across network communications media which often has high-latency.

The movement of an agent process, from a first place process in a first computer system to a second place process either in the first computer system or in a second computer system is called a trip. The agent initiates the trip by using a "go" operation, which is defined in the agent class. The agent controls the movement either through the network or within the computer system by creating and submitting, as an argument to the "go" operation, a ticket which defines the trip. In one embodiment, the ticket specifies the place to which the agent is to travel, the "way" by which the agent is to travel, the amount of time in which the trip must be completed, and an indication of the urgency of the trip, i.e., the priority of the trip relative to other trips by other agents that may be concurrently scheduled.

The ticket can identify the destination place by specifying the address, name, class or any combination of the address, name and class of a place to which the agent is to travel. The destination of the trip is any place of the specified address, name and/or class which grants the agent ingress within the time permitted by the ticket.

In the "go" operation, the agent is moved from a first place to a second place as follows: (i) the agent is suspended and the execution state of the first agent is preserved; (ii) the agent is represented in a standardized form, i.e., an octet string, which includes representation of the agent's preserved execution state; (iii) the standardized form is transported from the first place to the second place, potentially involving the transfer of the standard form from a first computer to a second computer; (iv) the agent at the second place is formed from the standardized form, including the execution state represented in the standardized form; and (v) interpretation of the agent is resumed, the agent initially having the execution state represented in the standardized form.

As mentioned above, the set of computer instructions of the present invention is object-oriented. Therefore, all objects formed according to the present invention are organized into classes. All classes in the present invention are represented by data objects which can be moved along with an agent. Thus, classes, which are not defined within a place, can nevertheless be used by an agent travelling to the place simply by the agent defining the classes and transporting the corresponding class objects to the place.

Every object in one embodiment of the present invention is owned by a process, i.e., either an agent or a place. When an agent travels from a first place to a second place, all objects owned by the agent are effectively moved to the second place along with the agent. However, as discussed below, objects which are equivalent to objects already occupying the second place are not transported in one embodiment of the present invention. In addition to the objects owned by the agent, all class objects defining classes of which those objects are members are moved along with the agent to the second place. A class object is an object constructed in accordance with the set of computer instructions described below and in Appendix A which represents a class of objects.

Thus, if an object owned by an agent travelling to a second place is a member of a class not defined in the second place, the object can still travel with the agent as the agent also carries to the second place class objects defining the classes of which the object is a member. In the prior art, a process which travelled from a first computer to a second computer could only process data objects which belonged to classes defined on the second computer. Class definitions were not typically transported with migrating processes in the prior art. As new classes can be formed within a first place and members of those new classes are free to travel to other places for which those new classes are not defined, the present invention provides agents a level of extensibility, mobility and generality not found in the prior art.

In the present invention, many classes of objects are defined at multiple places and therefore do not need to be moved to such places. Class objects and any other objects, which are likely to be found at many places are made interchangeable in one embodiment of the present invention.

Interchangeable objects each have a digest. An interchangeable object, which is owned by an agent that is travelling from a first place to a second place, does not travel with the agent. Rather, the digest of the interchangeable object is moved with the agent to the second place. When the agent arrives at the second place, interchangeable objects in the computer system which contains the second place are examined to determine whether any of the interchangeable objects has a digest equal to the digest transported with the agent. If such an interchangeable object is found in the computer system which contains the second place, the interchangeable object is substituted for the interchangeable object, which was left behind at the first place.

If, however, no such interchangeable object is found at the second place, the interchangeable object left behind at the first place is moved to the second place. In this way, the movement of objects across network communications media is avoided when equivalent objects are present at the destination place. In particular, as class objects are interchangeable, an agent travelling to a second place causes the movement to the second place of only those class objects defining classes which are not defined within the second place. Avoiding unnecessary movement of class objects through the network makes practical the movement of objects owned by an agent to places which contain no definition of one or more classes to which those objects belong.

In one embodiment of the present invention, classes are identified by citations. In a computer network having many computer systems supplied by different vendors, various versions of the disclosed instruction set can be implemented on various computer systems to which and from which agent processes can travel. A citation is an object which is used to identify classes or objects which are forward- or backward-compatible with one another. Therefore, an instruction requiring use of an object of a first class, or the first class itself, can use an object of a second class, or the second class itself, depending on the particular requirements of the instruction, if the second class is backward-compatible with the first class.

An agent, occupying a first place, is also capable of creating one or more clones of the agent and moving each clone to a respective place. A clone is an agent process which is the result of duplicating an existing agent process. An agent initiates and controls the creation of one or more clones, and the movement of each clone to a respective place process by performance of operation "send." The agent specifies the number of clones to be created and defines the corresponding trips by creating one or more tickets which are supplied as arguments to operation "send". Each ticket defines a trip to be taken by a respective clone of the agent. The number of tickets supplied by the agent defines the number of clones created.

Once a clone of the agent is moved to a second place, the clone initially has the execution state of the agent at the time the clone was created. Thus, when the clone arrives at a second place, the clone continues to execute so as to simulate the movement of the agent to the second place as described above with respect to operation "go."

In the prior art, a first process, i.e., a head process, created limb processes which had the same interface, i.e., could generally perform the same operations, as the head process. Limb processes did not act except as directed by the head process and could move to remote computer systems only at the direction of the head process.

In the present invention, however, a clone is autonomous and is not controlled by the agent which created the clone. For example, the clone can be configured to ignore all attempts by the agent to arrange a meeting, which is discussed below, whereby the agent and the clone can interact. The agent must attempt to interact with a clone of the agent in the same way the agent attempts to interact with any other agent, as discussed below. As the clone is autonomous, the clone occupying the second place can travel to a third place by performance of operation "go" without being so instructed by the agent and even without the consent of the agent.

As limb processes of the prior art were not active and acted only at the direction of a head process, the head process and a remote limb process necessarily interacted across network communications media. The paradigm of this prior art system is therefore more closely related to remote procedure calling. In contrast, clones of agents formed in accordance with the present invention are active and autonomous and embody all of the instructions which form the agent. Therefore, no interaction is required (in fact, no interaction is allowed) across network communications media. Therefore, the paradigm of the present invention is more closely related to remote programming. The present invention therefore represents a significant increase in generality over the prior art.

Increases in efficiency in one embodiment of the present invention are realized in performance of operation "send" by deferring cloning of an agent as long as possible. For example, a first clone and a second clone are to be sent to a first place and a second place, respectively. Suppose that the agent is executing within a first computer system, that the first place is executing within a second computer system, and that the second place is executing within a third computer system. Suppose further that in travelling to the first and second places, the first and second clones must travel through an engine executing on a fourth computer system. In such a case, a single clone is formed and transported to the engine executing within the fourth computer system. Thus, only a single clone is created within the engine interpreting the original agent thereby saving space within that engine and only a single clone is transported across network communications media to the fourth computer system thereby saving time in transporting clones to the fourth computer system. The engine executing within the fourth computer system forms from the single clone the first and second clones and transports the first and second clones to the first and second places, respectively.

As an agent can own objects which account for a substantial majority of the size of the agent, e.g., a rasterized graphical image such as a facsimile transmission or digitized sound, avoiding sending several copies of such large objects, each copy owned by a respective clone, to a single engine saves substantial time and expense.

A first agent, occupying a place, can initiate a meeting between the first agent and a second agent occupying the place. During such a meeting, the first agent can transfer to and receive from the second agent data in the form of objects, and the second agent process can transfer to and receive from the first agent data in the form of objects.

The present invention represents a significant improvement over a prior art system which teaches the posting of messages on a virtual bulletin board by a first process. The messages are then "read" by the intended recipient process. In the prior art system, a first process gives to a second process a reference to the first process by posting the reference on the virtual bulletin board. However, since there is no mechanism for simultaneous exchange of references, the second process has access to the first process before giving to the first process a reference to the second process. Thus, there is no mechanism to prevent "malicious" processes from gaining access to other processes without granting to the other processes access to themselves.

The present invention represents an improved method of establishing contact between two processes such that a first process cannot obtain access to a second process without simultaneously granting to the second process access to the first process.

In one embodiment of the present invention, two agents can interact only if both agents occupy the same place and the place is a meeting place. A meeting place is a place that is a member of a class of meeting places, which is a subclass of the class of places. A first agent directs that a meeting be arranged between the first agent and a second agent by issuing an instruction directing the meeting place to arrange the meeting. The issued instruction is called operation "meet", and the first agent's issuance of the instruction is called "requesting a meeting".

The first agent supplies, as an argument to the instruction, a petition defining the meeting. The petition defines the meeting by specifying the second agent as the petitioned agent. The second agent is specified by specifying the name and/or the class of the second agent. The petition further defines the meeting by specifying the amount of time in which the meeting must be arranged or abandoned.

In arranging the meeting, the meeting place supplies to the second agent the name and class of the first agent and indicates that the first agent has issued an instruction requesting a meeting with the second agent. The second agent examines the name and class of the first agent and responds to the meeting place either accepting or rejecting the meeting with the first agent.

If the meeting is rejected, the first agent is informed that the second agent is not available. If the meeting is accepted, the meeting place gives to the second agent a reference to the first agent and gives to the first agent a reference to the second agent. With a reference to the second agent, the first agent (i) can direct the second agent to perform operations; (ii) can supply to the second agent objects as arguments; and (iii) can receive from the second agent objects as results. As the second agent has a reference to the first agent, the second agent has similar capabilities with respect to the first agent.

Either the first or the second agent can terminate the meeting between the two by issuing an appropriate command. The meeting place, in performing an operation "part" in response to the issued command, voids any references to the second agent contained within the first agent and voids any references to the first agent contained within the second agent, thereby terminating interaction between the two agents.

The present invention represents a significant improvement over the prior art as a first agent cannot gain access to a second agent unless the second agent agrees or without granting to the second agent access to the first agent. Additionally, since two agents cannot interact unless both occupy the same meeting place, intermediate levels of security are available to agents. For example, an agent can protect itself from other agents by occupying a meeting place whose location is not widely known by other agents. Inversely, an agent, which is designed to be highly visible, may occupy a well-known meeting place. No such mechanism is available in the prior art.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows the structure of computer systems of the prior art.

FIG. 2A is a logic flow diagram of a prior art method using remote procedure calling.

FIG. 2B shows a prior art network implementing remote procedure calling.

FIG. 3A is a logic flow diagram of a prior art method using remote programming.

FIG. 3B shows a prior art network implementing remote programming.

FIGS. 4A and 4B show the movement of an agent process through a network constructed in accordance with the present invention.

FIGS. 5A and 5B show processes, formed in accordance with the principles of the present invention, executing within a computer system.

FIG. 5C shows a portion of a class hierarchy graph in accordance with one embodiment of the present invention.

FIGS. 6A-6C show the movement of an agent process through a network formed in accordance with the present invention.

FIGS. 7A-7E show the movement of clones of an agent process through a network formed in accordance with an aspect of the present invention.

FIGS. 8A-8F illustrate interaction between two agent processes by using operation "meet".

FIGS. 9A-9E illustrate the interrelations of place processes formed in accordance with one aspect of the present invention.

FIG. 10 shows the structure of a computer network formed in accordance with the principles of the present invention.

FIGS. 11A and 11B show alternative representations of the network shown in FIG. 10.

FIG. 12 is a diagram illustrating the class relationships of an agent process in one embodiment of the present invention.

FIGS. 13A and 13B illustrate the state of an agent process formed in accordance with the present invention immediately before and after, respectively, movement of the agent process within a computer network of the present invention by performance of operation "go".

FIGS. 14A-14G are logic flow diagrams which illustrate the steps taken to move an agent process through a network in accordance with the present invention by performance of operation "go".

FIGS. 15A-15E show the structure of a network formed in accordance with the present invention and illustrate the movement of an agent process through the network.

FIG. 16 shows the structure of an agent process including a permit.

FIG. 17 shows the structure of the permit of FIG. 16.

FIG. 18A shows the structure of the ticket of FIG. 13A including a teleaddress, a citation, a telename, and a way.

FIG. 18B shows the structure of the way of FIG. 18A.

FIG. 19 shows the structure of the telename of FIG. 18A.

FIG. 20A shows a dictionary formed according to one embodiment of the present invention.

FIG. 20B shows the structure of a finder constructed according to one embodiment of the present invention.

FIG. 21 shows the stricture of an encoded agent in accordance with one embodiment of the present invention.

FIGS. 22A and 22B show the state of an agent process immediately prior to and following, respectively, performance of operation "entering".

FIG. 22C is a logic flow diagram illustrating the steps taken in performance of operation "entering" in accordance with one embodiment of the present invention.

FIGS. 23A and 23B show a portion of the state of a process immediately preceding and following, respectively, performance of operation "exiting".

FIGS. 24A-24C are logic flow diagrams illustrating the steps taken in transporting an agent process through a network in accordance with an aspect of the present invention.

FIG. 24D shows the structure of a repository of interchanged objects which is used in the steps shown in FIGS. 24A-24C.

FIG. 25 shows a computer network formed in accordance with the principles of the present invention.

FIGS. 26A and 26B show a portion of the state of an agent process immediately prior to and following, respectively, performance of operation "send".

FIG. 26C shows the state of a clone of the agent process immediately following performance of operation "send".

FIGS. 27A and 27B show the state of a engine process before and after, respectively, formation of clones of an agent process in performance of operation "send".

FIG. 28 shows the computer network of FIG. 25 in which clones of the agent process have travelled to respective computer systems of the computer network in performance of operation "send".

FIGS. 29A-29E show a computer network through which clones of an agent process travel according to another aspect of the present invention referred to as "deferred cloning".

FIG. 30A shows the structure of a send frame including a nil and a list of tickets.

FIG. 30B shows the structure of an encoded clone of an agent process formed in accordance with an aspect of the present invention.

FIGS. 31A and 31B show the state of a process immediately preceding and following, respectively, performance of operation "meet".

FIG. 32 is a logic flow diagram of the steps taken in performance of operation "meet".

FIG. 33 shows a portion of the state of an agent process including a set of contacts.

FIGS. 34A and 34B show the state of a process immediately preceding and following, respectively, performance of operation "meeting".

FIG. 35 is a logic flow diagram illustrating the steps taken in performance of operation "meeting" in accordance with one embodiment of the present invention.

FIG. 36 shows the state of two agent processes which are interacting in accordance with an aspect of the present invention.

FIGS. 37A and 37B show a portion of the state of an agent process immediately preceding and following, respectively, performance of operation "part".

FIG. 38 shows the state of the agent processes shown in FIG. 36 immediately following performance of operation "part".

FIGS. 39A-39F show a portion of the state of a first agent process during interaction with a second agent process in accordance with the present invention.

FIG. 40 is a logic flow diagram illustrating steps taken by the second agent process during the interaction shown in FIGS. 39A-39F according to one embodiment of the present invention.

FIG. 41A shows the structure of a class definition in accordance with one aspect of the present invention.

FIG. 41B shows the structure of a class object formed in accordance with one embodiment of the present invention.

FIG. 41C shows the structure of a class object formed in accordance with a second embodiment of the present invention.

FIG. 42 shows the structure of an interface object formed in accordance with the present invention.

FIG. 43 shows the structure of a feature definition including a set, an identifier, and a boolean.

FIG. 44 shows the structure of an attribute definition including a constraint and a boolean.

FIG. 45 shows the structure of an operation definition including a constraint and a list, which in turn includes a constraint.

FIG. 46 shows the structure of a constraint.

FIG. 47 shows the structure of an implementation object which includes two lists and six lexicons.

FIG. 48 shows the structure of a method which includes a procedure and a list, which in turn includes an identifier.

FIG. 49 shows the structure of the procedure of FIG. 48.

FIG. 50 shows the structure of a citation which includes a telename, two integers, and an identifier.

FIG. 51 shows the structures of two cited objects, each of which includes a respective citation.

FIG. 52A is a logic flow diagram illustrating the steps taken in performance of operation "do".

FIG. 52B shows the structure of a predefined frame which includes an integer and a procedure.

FIG. 53 shows the execution state of a process which includes a stack, which in turn includes a user frame.

FIG. 54 shows the state of the user frame of FIG. 53.

FIGS. 55A and 55B combine as shown in FIG. 55C to form a single logic flow diagram illustrating the steps taken in performance of a user-defined operation.

FIG. 56A shows the execution state of a process which includes a stack, which in turn includes a frame.

FIG. 56B shows the execution state of the process of FIG. 56A and a second frame.

FIG. 56C shows the execution state of the process of FIGS. 56A and 56B, including the stack, which in turn includes the first-mentioned frame and the second frame.

FIG. 57 is a logic flow diagram illustrating the steps taken in selecting a feature definition and a method from the class hierarchy in accordance with the present invention.

FIG. 58A is a diagram showing the hierarchy of the classes of which a list is a member.

FIG. 58B is a diagram showing the hierarchy of the classes of which class "List" is a member.

FIG. 59 is a logic flow diagram illustrating the steps taken in the initialization of an object.

FIG. 60 is a logic flow diagram illustrating the steps taken in performance of operation "if".

FIG. 61 is a logic flow diagram illustrating the steps taken in performance of operation "either".

FIGS. 62A and 62B show a portion of the execution state of a process immediately preceding and following, respectively, performance of operation "select".

FIG. 63 is a logic flow diagram illustrating the steps taken in performance of operation "select".

FIG. 64 shows the state of a predefined frame which represents the dynamic state of a performance of operation "select".

FIG. 65 is a logic flow diagram illustrating the steps taken in performance of operation "while".

FIGS. 66A and 66B show a portion of the execution state of a process immediately prior to and immediately following, respectively, performance of operation "catch".

FIG. 67 is a logic flow diagram illustrating the steps taken in performance of operation "catch".

FIG. 68 is a logic flow diagram illustrating the steps taken in performance of operation "loop".

FIG. 69 shows the structure of a repeat frame which includes an executed object and two integers.

FIG. 70 is a logic flow diagram illustrating the steps taken in performance of operation "repeat".

FIG. 71 shows the execution state of a process which includes a stack which in turn contains, from top to bottom, a user-defined frame, a predefined frame, a repeat frame, and a second user-defined frame.

GLOSSARY OF TERMS

"Abstract Class": A class which is abstract has no instances. An abstract class can have subclasses, and an abstract class can define features, methods, and properties which are inherited by the subclasses of the abstract class.

"Agent": An agent is a process which occupies a place and which is mobile, i.e. can move from a first place to a second place.

"Arguments": An argument is an object "consumed" by performance of an operation as input data. In other words, an argument is an object transferred from the requester to the responder immediately prior to performance of the operation by the responder at the request of the requester.

"Attribute": An attribute is a feature which either retrieves or sets information regarding the internal state of an object. Usually the information pertains to the object itself, but sometimes the information pertains to the reference by which the object is identified in invoking the attribute. An attribute is a pair of operations in which one sets, and the other retrieves, information regarding the internal state of the responder.

"Authority": An authority is an entity which owns and controls various resources in the network. An example of an authority is a user of the network. Authorities are created administratively and cannot be created programmatically, i.e., cannot be created at the request of a process.

"Class": A class defines (i) zero or more properties, which define the internal states of the members of the class, (ii) zero or more methods, which define the internal behavior of the members of the class, and (iii) zero or more features, which define the external behavior of the members of the class.

"Concrete Class": A class which is concrete can have instances.

"Engine Place": Every engine contains exactly one engine place which represents the engine itself.

"Engine": An engine is a machine in a computer system which manages objects, primarily processes, and executes instructions. An engine is typically a computer process executing within a computer system in addition to an operating system and various user applications. One or more engines can be executing within each computer system of a network. Each engine processes at least one place.

"Exception": An exception is an object "thrown" by performance of a feature if the feature fails to be performed completely and successfully. An exception, as the term is used herein, is alternatively a condition which causes such an object to be thrown. The responder is said to "throw" an exception, rather than "produce" an exception, because an exception arises from the failure of an operation and is therefore distinct from a result which is produced by a successful operation. The distinction between producing a result and throwing an exception is described in more detail below and in Appendix A which is hereby incorporated herein in its entirety by reference.

"Feature": A feature is a task that an object can be directed to perform. The task is carried out by a method, which includes a set of computer instructions. Performance of a feature is accomplished by execution of the computer instructions of the feature's method. A feature is associated with a specific class of objects, and performance of a feature can vary with the specific internal state of the object performing the feature. Features are conceptually divided into the two categories: (i) attributes and (ii) operations.

"Frame": A frame is an object which records the dynamic state of a method implementing a feature during performance of the feature. A frame is used by an engine to maintain information regarding a method which the engine is executing, including information identifying the object performing the feature implemented by the method and the particular instruction that is currently executing.

"Identifier": An identifier is an object which can reference a second object. The "text" of an identifier is a string which distinguishes the identifier from other identifiers within a particular scope. The various scopes of identifiers are discussed in greater detail in Appendix A.

"Implementation": An implementation is a set of computer steps performed in performance of a particular feature. An "implementation object" is an object defining the various implementations of the various features of a class.

"Instance": An object is an instance of a class if the object is a member of that class and is not a member of any subclass of that class.

"Interface": An interface defines a particular attribute or the particular arguments consumed and the result produced by performance of a particular operation. An "interface object" is an object defining the various interfaces of the various features of a class.

"Member": An object is a member of the class of which the object is an instance and any superclasses of that class.

"Method": A method is a set of computer instructions whose execution constitutes performance of a particular feature. A "method object" is an object defining a method. A method has a dynamic state during performance of the method, i.e., execution of the instructions of the method. The dynamic state of a method is represented by a frame.

"Network": All engine places, the computer systems in which the engine places execute and communications apparatus connecting those computer systems collectively form a network.

"Object": An object is an element in a computing environment within a computer system. An object has an internal state defined by zero or more properties, an internal behavior defined by zero or more methods, and an external behavior defined by zero or more features.

"Operation": An operation is a feature for which an interface and implementation is defined.

"Place": A place is a process which is a locale for zero or more processes. A place can occupy a second place. The first-mentioned place is a subplace of the second place, and the second place is a superplace of the first place.

"Primitive": A primitive is an object that can be used in the formation of a procedure or a method, and that therefore can serve as an instruction.

"Process": A process is an object which constitutes an autonomous computation. A process is autonomous because a process performs a method without being requested to do so by another object. A process commences performance of a central method upon creation of the process, and the process is destroyed upon completion of the central method. Every object is owned by exactly one process. Every process is owned by itself. As used herein, the term "computer process" refers to a series of instructions carried out by a computer system, which is a more general and well-known definition.

"Property": A property is an object which represents a part of the internal state of a second object.

"Reference": A reference is a data structure which identifies a particular object. An object, in being directed to perform a feature, is identified by a reference to the object supplied by the requester of the feature. References are either protected or unprotected. An object cannot be altered or modified using a protected reference to identify the object.

"Region": A region is one or more engine places within a network which are controlled by a single authority. A region is generally distinguished by the close coordination and management of computer systems which support the engine places of the region. The transportation of agents within a region is therefore generally quicker and less expensive than transportation of agents between regions. A region can be, for example, a local area network which is connected to a wide area network.

"Requester": A requester is an object which directs another object, i.e. the responder, to perform a feature. The requester supplies zero or more objects as input data to the responder of the feature requested and receives zero or one object as output data from the responder of the feature. Directing an object to perform a feature is alternatively called "requesting" the object to perform the feature.

"Responder": A responder is an object performing a feature at the direction of another object, i.e. the requester. The responder receives zero or more objects as input data and supplies zero or one object as output data in performing the feature. A responder is alternatively called a "responding" object.

"Result": A result is an object "produced" by performance of an operation as output data. In other words, a result is an object transferred from the responder to the requester immediately following performance of an operation by the responder at the request of the requester.

"Subclass": A subclass inherits methods, properties, and/or feature definitions from one or more classes. A subclass can define one or more properties, methods, and/or features which are not inherited from any other class and can reimplement a feature which is inherited from another class by defining a new implementation of the feature.

"Superclass": The classes from which a subclass inherits properties, methods, and/or features are superclasses of the subclass.

"Virtual Place": Every place which is not an engine place is a virtual place.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

According to the principles of this invention, a novel set of computer processes are used to route a particular computer process to a selected computer system contained in a plurality of interconnected computer systems and to execute the particular computer process on the selected computer system. The computer processes of this invention are defined, in one embodiment, in terms of object-oriented computer processes. The computer processes of this invention include (i) an instruction set that defines the various operations in the process and (ii) an engine that interprets the instruction set and controls operation of a central processing unit (CPU) in performance of the computer processes.

As explained more completely below, the particular computer process directs its own movement, i.e., transportation, through the computer network by executing an instruction which identifies a destination computer system within the network and directs that the particular computer process be transported there. While executing within the destination computer system, the particular computer process may have access to information which is not available elsewhere in the network. The particular computer process can access that information and use that information to determine to which other computer systems to travel. As explained more completely below, the present invention provides computer processes with a level of mobility, extensibility and generality not found in the prior art.

In remote programming paradigms typically found in the prior art, a computer process does not direct its own movement, but is sent from a source computer system to execute within a destination computer system. If the computer process cannot direct its own movement throughout the network, the computer process cannot select further destination computer systems to which to travel on the basis of information obtained by the computer process at the destination computer system. Thus, such a computer process must return to the source computer system with the information obtained before being sent to a second destination computer system. As computer processes of the present invention can direct their own movement through the network, computer processes of the present invention represent a substantial extension of the traditional remote programming paradigm.

Existing remote programming systems, which provide processes which direct their own movement through a computer network, lack generality and extensibility. Such systems lack generality in that such systems (i) are limited to homogeneous computer networks or (ii) require that a travelling process in a heterogeneous network contain instructions which conform specifically to whichever computer system is executing the process, i.e. computer systems to which the travelling process travels. In the present invention, a process travels within a heterogeneous computer network and the execution of the instructions of the process is independent of which particular computer system within which the process executes, i.e., to which the process travels. As discussed below in greater detail, the computer instructions disclosed below are implemented uniformly by each of the computer systems of a heterogeneous network. Thus, a process formed in accordance with the present invention can travel to any computer system within a heterogeneous computer network and execute there without any specific information regarding the nature of the computer system.

Remote programming systems of the prior art typically lack extensibility in that a process cannot create a class of data objects and utilize data objects of that class within computer systems to which the process subsequently travels. Many computer processes formed today are "object-oriented". As defined above in the Glossary of Terms, an object has (i) an internal state defined by a number of properties, (ii) an internal behavior defined by a number of methods, and (iii) an external behavior defined by a number of features. The properties, methods, and features of a group of objects with like properties, methods, and features are defined by a class. In prior art systems, a process which defines a class cannot use objects of the class while executing in computer systems to which the process subsequently travels. Transportation of class definitions with travelling processes is not feasible or practical in prior art systems because class definitions are not standardized, class definitions are generally very large and complex; and a single process generally uses objects of many classes.

Class definitions are not "standardized" in that prior art systems are typically based on existing programming languages which are not designed with mobile processes in mind. Therefore, class definitions in a process formed using one of these existing programming languages typically rely on information specific to the computer system within which the process is created, such as the specific memory addresses of portions of the class definitions. Reliance on such information, which is specific to a particular computer system, makes class definitions of prior art systems very difficult to transport to remote computer systems.

In the present invention, classes are represented by class objects which are part of the disclosed computer instruction set. A process formed in accordance with the present invention includes class objects when travelling from one computer system to another. Thus, a process can define a class of object in a first computer system, travel to a second computer system, and utilize objects of the class within the second computer system. Unnecessary delay and expense in transporting all classes utilized by a travelling process are eliminated by transporting only those classes which are not defined within the computer system to which the process travels.

Additionally, the present invention provides efficiencies not found in the prior art in transporting several clones of a process to several destination computer systems simultaneously. As discussed more completely below, substantial efficiencies are realized by deferring creation of one or more clones of the process so long as the travel path of one clone coincides with the travel path of another clone. Clones, and this aspect of the present invention, are discussed further below.

In remote programming systems, two processes share information by a first process giving a second process access to the first process. The first process gives the second process access to the first process without simultaneously obtaining access to the second process. In such a situation, the second process is free to interfere with the execution of the first process without compromising the security of the second process. In the present invention, a first process obtains access to a second process and simultaneously gives to the second process access to the first process through the cooperation and coordination of a third process. Further security is provided as the second process either accepts or rejects such an exchange with the first process according to the configuration of the second process. The third process ensures that (i) the second process agrees to such an exchange and that (ii) each process gains access to the other process simultaneously such that neither process can interfere with the execution of the other process without affording a similar opportunity to the other process.

A novel computer process of this invention is an agent process. An agent process is a computer process formed of the computer instructions disclosed below in Appendix A, which is a part of this disclosure and which is incorporated herein by reference in its entirety. Agent processes are each interpreted by another novel computer process of this invention, i.e., an engine, and thereby effectuates the computer instructions disclosed below and in Appendix A. The term "interpreted" is used herein as it is understood in the art; a computer instruction in a series of computer instructions is read and executed by an engine before the next computer instruction in the series is read.

Interpreting, rather than compiling, instructions of the disclosed instruction set provides greater generality. A first agent can travel from a first computer system to a second computer system and meet with a second agent there which gives to the first agent a procedure. The first agent can then perform the procedure which the first agent was not originally designed to perform.

Yet another novel computer process of this invention is a place process. Place processes are dispersed throughout a computer network. Each agent process "occupies" a respective place process; i.e., a place process is part of the internal state of an agent process and therefore provides a context within which the agent process executes. Each agent process can initiate and control the agent process's transportation from a first place process to a second place process. "Agent" and "place" as used herein are shorthand terms for "agent process" and "place process" respectively.

FIG. 4A shows computer network 100 which includes computer systems 120A and 120B which are connected by communications link 102AB. Computer system 120A is executing place 220A and agent 150A. Agent 150A occupies place 220A as shown in FIG. 4A. Computer system 120B is executing place 220B. Hereinafter, the statement that an agent or place occupies a particular place should be interpreted as including a statement that the agent or place is executing within the computer system which contains the particular place.

Agent 150A issues an instruction to computer system 120A. In response to the instruction, agent 150A is transported to a place, e.g. place 220B, specified in the instruction. The instruction is called operation "go", and the issuance of the instruction by agent 150A is called herein performance of operation "go" by agent 150A.

Upon performance of operation "go" by agent 150A, (i) execution of agent 150A is suspended; (ii) agent 150A is encoded into a standardized form which preserves the execution state of agent 150A; (iii) the standardized form of agent 150A is transported to computer system 120B; (iv) agent 150A, including the preserved execution state, is decoded from the standardized form; and (v) execution of agent 150A is resumed within computer system 120B. After performance of operation "go" by agent 150A, agent 150A no longer occupies place 220A and is no longer executing within computer system 120A; instead, agent 150A occupies place 220B and is executing within computer system 120B (FIG. 4B). By enabling an agent to travel to a remote computer system in the midst of the agent's execution, the agent is free to travel to data which the agent is configured to access.

A standardized form is a form to which agents are encoded for the transportation of the agent from one computer system to another. The standardized form preserves the execution state of the encoded agent such that the agent can be decoded at the destination computer system and execution of the agent can resume by executing the instruction of the agent which sequentially follows operation "go". Each computer system of the network of the present invention can maintain an agent in whatever form is convenient for carrying out the computer instructions included in the agent. However, in transporting an agent from one computer system to another, each computer system of the network must use the standardized form of an agent during transportation much the same way that two people must agree to the vocabulary and syntax of a single language to communicate. The nature of the standardized form is discussed in greater detail in Appendices B, C, D, E and F, which are part of this disclosure and which are incorporated in their entirety herein by reference.

As an agent can direct its own movement, i.e., transportation, through the network, means must be provided for specifying a number of parameters of a trip from a first computer system to a second computer system. A first parameter of a trip is the place to which the agent is transported, i.e., the destination of the trip. In one embodiment, a trip destination can be specified by name, by class, or by address. An address can be, for example, a location within a local area network.

Frequently, two or more pathways exist between a first computer system and a second computer system. One pathway may be quick but expensive and another may be time consuming but inexpensive. In such a case, no single pathway is always preferred in the transportation of an agent. Therefore, a second parameter of a trip is the "way" and the "means" for travel of an agent.

In addition, errors in configuring an agent for a trip to a nearby computer system can cause the agent to be inadvertently transported to distant computer systems at considerable expense to the creator of the agent. Therefore, an important parameter of a trip is the amount of time or resources that can be expended in transporting the agent before the trip is aborted.

Yet another important consideration in controlling the transportation of agents throughout a network is security. For example, if all agents travelling to a particular computer system are granted ingress, the particular computer system may become overburdened with many processes requiring substantial processing, and throughput of the particular computer system can suffer. Therefore, another parameter of a trip is the amount of resources the agent requires at the destination place. Thus, the agent can be denied ingress to the place if the resources required by the agent are more than the place is able or willing to provide.

In one embodiment, a ticket 1306 (FIG. 4A) controls the transportation of agent 150A and specifies place 220B as the destination place. As shown in FIG. 4A, agent 150A contains ticket 1306. Ticket 1306 defines the trip taken by agent 150A from place 220A to place 220B. In one embodiment, ticket 1306 specifies (i) the destination place of the trip, (ii) the "way" or pathway and "means" agent 150A is to take to the destination place, (iii) the maximum amount of time within which the trip must be completed before the trip is aborted and (iv) the amount of resources agent 150A asks to use at the destination place. By specifying the amount of resources agent 150A is permitted to use at place 220B, place 220B can determine whether agent 150A requires more resources than place 220B is configured to provide. In such a situation, place 220B can deny ingress to agent 150A. Thus, using a ticket as described more completely below, an agent can completely define a pending trip between a first place and a second place.

As discussed above, the prior art process known to the inventors cannot manipulate objects of a class defined only in a previously occupied computer system. In other words, if a prior art process defines a class of objects and thereafter travels to a destination computer system, the process cannot manipulate objects of the class unless the destination computer system contains a definition of the identical class or the process defines the same class again within the destination computer system. As described in greater detail below, agents of the present invention, which travel from one place to another, transport definitions of classes which are not defined within the destination place. Thus, agents of the present invention can define a class within a first computer system, travel to a second computer system and manipulate objects of the class while executing within the second computer system. Agents of the present invention therefore represent a significant improvement over the known prior art processes.

What is also generally lacking in the prior art is a means to implement a complex, multi-level security system in a computer network in which computer processes are mobile. One type of security which is afforded by the present invention, and which is not suggested by the prior art, is the security afforded by places. As discussed in greater detail below, places, by granting or denying ingress to various agents, provide various levels of security and several places can be configured to provide multi-level, hierarchical security.

To assist in the understanding and visualization of the various aspects and embodiments of the present invention, various representational and relational conventions are used in the drawings. Representational and relational conventions used herein are represented in FIGS. 5A, 5B and 5C. Computer system 120A (FIG. 5A) is executing place 220A, place 220X, place 220Y, agent 150A, agent 150X and agent 150Y. Computer system 120A also contains objects 140A, 140B and 140X in a memory, e.g., mass memory or main memory (neither shown), of computer system 120A. Agent 150A and 150X occupy place 220A; place 220Y occupies place 220X; and agent 150Y occupies place 220Y. Agent 150A owns objects 140A and 140B, and agent 150X owns object 140X. The relationships of occupancy and ownership are discussed in greater detail below. Briefly, occupancy of places provides various levels and types of security, and ownership determines which objects travel with an agent which performs operation "go".

FIG. 5B is an alternative and equivalent representation of the various relationships represented in, and described above with respect to, FIG. 5A. While FIG. 5A accurately represents, e.g., that agent 150X occupies place 220A and contains object 140X, the form of FIG. 5A is less suitable for representing more complex relationships. Therefore, the tree structure of FIG. 5B is used in the drawings to represent more complex relationships in illustrating the various computer instructions of various embodiments of the present invention.

The tree structure of FIG. 5B should not be confused with the class hierarchy tree which is shown in part in FIG. 5C. FIG. 5C represents the class relationships of various items represented in FIGS. 5A and 5B. Objects 140A, 140B and 140X are members of class "Object" which is represented by class object 520. Membership in a class is discussed in greater detail in the Glossary of Terms above and is represented by a dashed line between the class and the object which is a member of the class. Class object 522 represents class "Process", which is a subclass of class "Object". Places 220X, 220Y and 220A are members of class "Place", which is a subclass of class "Process" and is represented by class object 524. Agents 150A, 150X and 150Y are members of class "Agent", which is a subclass of class "Process" and is represented by class object 526. Thus, places 220X, 220Y and 220A and agents 150A, 150X and 150Y are all members of class "Process" and are therefore computer processes. Objects 140A, 140B and 140X are not members of class "Process" and are therefore not computer processes.

When an agent is transported from place to place, objects owned by the agent are transported with the agent from place to place. However, transporting an object can consume considerable resources if the object is large. In general, time in transporting an agent containing objects from a first place executing within a first computer system to a second place executing within a second computer system is substantially reduced by eliminating transportation of objects already at the second place. This is easily demonstrated by considering a simple example. Agent 150A (FIG. 6A) is executing within computer system 120A and occupies place 220A which is also executing within computer system 120A. Agent 150A owns objects 140A, 140B and 140C. In this embodiment, object 140B has digest 622. Digest 622 indicates that object 140B is interchangeable and that any object having a digest equal to digest 622 can be substituted for object 140B.

Place 220B owns, and therefore contains, objects 624 and 626. Object 624 has digest 628. A process "contains" all the objects owned by the process and the classes of which the process and the objects owned by the process are members.

In performance of operation "go", as indicated above, agent 150A and all objects contained by agent 150A are represented in a standardized form. However, object 140B is not included in the standardized form of agent 150A. Instead, a copy of digest 622, i.e., digest 622-C (FIG. 6B), is included in the standardized form of agent 150A. Agent 150A, objects 140A and 140C, and digest 622-C are transported over communications link 102AB, in the direction of arrow A, to computer system 120B. Object 140B is held within computer system 120A at least until it is determined that an equivalent interchangeable object is found within computer system 120B.

At computer system 120B (FIG. 6C), agent 150A, objects 140A and 140C, and digest 622-C are decoded. In decoding agent 150A, computer system 120B recognizes digest 622-C and determines whether an object with an equivalent digest occupies place 220B. Object 624 occupying place 220B has digest 628 which is equal to digest 622, and is therefore equal to digest 622-C. Since digest 628 is equal to digest 622, objects 140B and 624 are interchangeable. Therefore, in decoding agent 150A, a copy, e.g., object 624-C, is made of object 624 and substituted within agent 150A for interchangeable object 140B. Agent 150A therefore owns object 624-C, which is a copy of object 624, in lieu of object 140B. Thus, transportation of object 140B to place 220B is obviated. Since an equivalent interchangeable object is found within computer system 120B, object 140B can be deleted from computer system 120A. Of course, there are situations in which an equivalent interchanged object is not found on computer system 120B. In such a situation, object 140B (FIG. 6B) is retrieved from computer 120A as described more completely below.

An agent, occupying a first place, is capable of creating one or more clone processes of the agent and transporting each clone process to a respective place. Thus, in effect, an agent is capable of traveling to and occupying several places simultaneously. Of course, it is not a single agent that travels simultaneously but rather the clones of the agent.

To travel to and occupy several places simultaneously, an agent issues an instruction which creates multiple clones of the agent and causes each clone to travel to a respective place. Each clone is an agent, and, at the time of a clone's creation, the clone is identical to the original agent, and therefore includes an execution state identical to that of the original agent.

For example, agent 150A, which occupies place 220A in computer 120A (FIG. 7A), issues an instruction to computer system 120A which creates clones of agent 150A and transports the clones to occupy one or more places, e.g., place 220B in computer system 120B and place 220C in computer system 120C, which are specified in the instruction issued. The instruction is called operation "send", and the issuance of the instruction by agent 150A is called herein performance of operation "send" by agent 150A. Performance of operation "send" by agent 150A as represented in FIGS. 7A, 7B, 7C and 7D is controlled, in this embodiment, by two tickets (not shown) within agent 150A. The two tickets control the transportation of respective clones and specify places 220B and 220C as the places to which respective clones of agent 150A are to be transported.

Agents 150A-1 and 150A-2 (FIG. 7B) are clones formed from agent 150A, and are identical to agent 150A except that agents 150A-1 and 150A-2 do not occupy place 220A. As described above, even the execution states of agents 150A-1 and 150A-2 are initially identical to the execution state of agent 150A. Agents 150A-1 and 150A-2 travel along intercomputer communications link 120ABC (FIG. 7C), as described in greater detail below, to respective places 220B and 220C.

After performance of operation "send" by agent 150A (FIG. 7D), agent 150A continues to occupy place 220A. Agent 150A-1 occupies place 220B, and agent 150A-2 occupies place 220C.

Space in computer system 120A and time in transporting clones of agent 150A are saved by deferring complete cloning of an agent 150A so long as the travel path of one clone coincides with the travel path of another clone, i.e., at least two clones have some initial portion of their journey that is coextensive. For example, in FIG. 7E, both clones of agent 150A must pass through computer system 120D to reach respective destination places 220B and 220C. Therefore, only a single clone of agent 150A, namely, agent 150A-1, is transported to computer system 120D. A second clone of agent 150A, namely, agent 150A-2, is formed in computer system 120D from agent 150A-1. Agents 150A-1 and 150A-2 are then transported to respective destination places 220B and 220C. Thus, only a single clone of agent 150A is formed in computer system 120A and only a single clone is transported to computer system 120D saving space in computer system 120A and time in transporting agents 150A-1 and 150A-2 to their respective destinations.

Two agents exchange information by participating in a meeting between the two agents. In such a meeting, each agent is provided with a reference to the other agent. As discussed below, a first agent, which possesses a reference to a second agent, (i) can direct the second agent to take specific actions in accordance with instructions contained with the second agent and (ii) can transfer data to and receive data from the second agent. In one aspect of the present invention, an agent is prevented from interfering with other agents by requiring that no agent be given a reference to a second agent unless the second agent is given a reference to the first-mentioned agent. In that way, no agent can gain access to a second agent without granting reciprocal access.

A first agent, occupying a place, can initiate a meeting with a second agent occupying that place. During such a meeting, the first agent can transfer objects to and receive objects from the second agent, and the second agent can transfer objects to and receive objects from the first agent.

A subclass of class "Place" (FIG. 5C) is class "Meeting Place" (not shown). In the illustrative example of FIGS. 8A-8F, place 220B is a member of class "Meeting Place" and is therefore a meeting place. Therefore, place 220B is sometimes referred to herein as "meeting place 220B". Meeting place 220B (FIG. 8A), which is executing in computer system 120B, provides a means for agents 150A and 150B, which occupy meeting place 220B, to communicate and share information in a meeting as indicated by arrows A and B. Petition 3106 within agent 150A defines and controls the meeting between agents 150A and 150B.

A meeting between agent 150A and 150B is arranged as illustrated by FIGS. 8B-8F. Agent 150A (FIG. 8B) issues a first computer instruction, represented by arrow 851, directing meeting place 220B to arrange a meeting between agents 150A and 150B. The first instruction includes petition 3106, which controls the meeting, and which specifies that agent 150A wants to meet with agent 150B. On behalf of meeting place 220B (FIG. 8C), the engine issues a second computer instruction, represented by arrow 852, which notifies agent 150B that agent 150A has issued the first computer instruction, and which causes execution of a number of computer instructions within agent 150B to determine whether a meeting between agents 150A and 150B is acceptable.

Upon determination that the meeting between agents 150A and 150B is acceptable (FIG. 8D), agent 150B issues a reply, represented by arrow 853, to the second computer instruction, directing the engine, on behalf of meeting place 220B, to proceed in arranging the meeting between agents 150A and 150B. On behalf of meeting place 220B (FIG. 8E), the engine conveys to agent 150A a reference to agent 150B, the conveyance being represented by arrow 854A, and conveys to agent 150B a reference to agent 150A, the conveyance being represented by arrow 854B. Agent 150A (FIG. 8F) interacts with agent 150B using the reference to agent 150B, the reference being represented by arrow 855A, and agent 150B interacts with agent 150A using the reference to agent 150A, the reference being represented by arrow 855B.

Two agents cannot participate in a meeting together unless the two agents occupy the same place. A hierarchy of places provides users of the present invention a mechanism to provide varying levels and types of access and security to various agents. The benefit of various levels and types of access and security is demonstrated by the illustrative example of FIGS. 9A-9E.

FIG. 9A shows a building 902 having floors 902-1, 902-2, 902-3, 902-4 and 902-5. Floor 902-3 is a place within the place of building 902 and is therefore a subplace of building 902. FIG. 9B shows floor 902-3 having rooms 902-3-1, 902-3-2, 902-3-3, and 902-3-4. Room 902-3-2 is a place within the place of floor 902-3 and is therefore a subplace of floor 902-3.

The organization of building 902 lends itself to hierarchical security. For example, building 902 can be restricted to allow only people of a first level of security, e.g., military personnel, to enter. Floor 902-3 can be further restricted to allow only people of a second (higher) level of security, e.g., naval personnel, to enter. Room 902-3-2 can be still further restricted to allow only people of a third (still higher) level of security, e.g., naval officers, to enter. Floor 902-4 can be restricted independently of floor 902-3, e.g., to allow only air force personnel to enter.

The engine in computer system 120X (FIG. 9C) is executing places 220X1 and 220X2. Place 220X1 can represent, for example, building 902. Places 220X1-1 and 220X1-2, which represent, for example, floors 902-4 and 902-3, occupy place 220X1 (FIG. 9D) and are therefore subplaces of place 220X1. Conversely, place 220X1 is a superplace of places 220X1-1 and 220X1-2. Place 220X1-2-1, which represents, for example, room 902-3-1, occupies place 220X1-2 (FIG. 9E). Place 220X1-2-1 is therefore a subplace of place 220X1-2, and place 220X1-2 is a superplace of place 220X1-2-1.

In one embodiment of the present invention, two agents can only meet "face-to-face", i.e., when both agents occupy the same place. As used herein, an agent "occupies" one place only and does not simultaneously occupy subplaces or superplaces of the place. For example, an agent occupying place 220X1-2 does not simultaneously occupy place 220X1 or place 220X1-2-1. Just as a first person in building 902 (FIG. 9A) cannot communicate face-to-face with a second person on floor 902-3 unless the first person is also on floor 902-3, an agent occupying place 220X1 (FIG. 9D) cannot communicate with an agent occupying place 22OX1-2. As a first person on floor 902-3 (FIG. 9B) cannot communicate face-to-face with a second person in room 902-3-2 unless the first person is also in room 902-3-2, an agent occupying place 220X1-2 (FIG. 9E) cannot communicate with an agent occupying place 220X1-2-1.

Such a place hierarchy enables a user of the present invention to restrict access to place 220X1, to further restrict access to place 22OX1-2 and to restrict access to place 220X1-2-1 further still. Additionally, the security hierarchy implemented is not necessarily directly related to the place hierarchy implemented. For example, access to place 220X1-2 can be more restrictive than access to a subplace of place 220X1-2, such as place 220X1-2-1. The restriction of access to a place is described in greater detail below. Thus, the place hierarchy enables a user of the present invention to construct sophisticated security hierarchies in which various agents are given various levels of access to other agents which occupy certain places, subplaces of those places, and subplaces of those subplaces.

To describe further details of the novel processes described above, a better understanding of the structure of the computer systems described above is required. In the embodiment shown in FIG. 10, three computer systems are connected to form a computer network 100. Computer system 120A includes CPU 110A, network communications hardware 104A, and memory 117A. Input and output modules corresponding to input module 12 and output module 14 of FIG. 1 are omitted for clarity. Additionally, mass memory 17A and main memory 17B of FIG. 1 are combined to form memory 117A. Network communications hardware 104A can be any device which enables CPU 110A to propagate signals across and to receive and interpret signals from the network.

Within memory 117A are a number of computer processes operating concurrently within CPU 110A. Network manager 130A is a computer process which coordinates data transmission between the various computer systems of the computer network. Operating system 131A is a computer process which coordinates the operation of the various components and resources of computer system 120A. For example, operating system 131A coordinates the use of components CPU 110A, memory 117A and I/O modules (not shown in FIG. 10, see FIG. 1). Engine 132A is a computer process which interprets computer instructions of an object-oriented computer instruction set of this invention and processes information in the form of objects defined in that object-oriented computer instruction set. For example, engine 132A effectuates concurrent execution of place 220A (FIG. 4A) and agent 150A, both of which are processes constructed of the object-oriented computer instruction set of the present invention. Engine 132A is not shown in FIG. 4A.

In addition to these processes operating within memory 117A (FIG. 10) of computer system 120A, there are typically one or more processes which are user applications, e.g. user application 133A. User application 133A can request of engine 132A the creation of and/or manipulation of objects defined within the object-oriented instruction set interpreted by engine 132A.

Computer systems 120B and 120C are configured similarly to computer system 120A. However, while the general structure of computer systems 120A, 120B and 120C are similar, computer systems 120A, 120B and 120C can be otherwise heterogeneous.

The computer systems of computer network 100 are connected such that an agent process can be transported from one computer system to another. Computer systems 120A, 120B and 120C are connected to form a computer network by coupling the respective network communications hardware 104A, 104B and 104C by means of communications links 102AB, 102BC and 102AC. Communications links 102AB, 102BC and 102AC can be any means by which data can be conveyed from one network communications hardware, e.g., network communications hardware 104A to another, e.g., network communications hardware 104B. For example, network communications link 102AB can be the public switched telephone network, in which case network communications hardware 104A and 104B are modems and network managers 130A and 130B are capable of issuing commands to network communications hardware 104A and 104B, respectively, to establish and utilize communications via communications link 102AB i.e., the public switched telephone network.

Objects constructed of the object-oriented computer instruction set are executed by an engine, e.g., engine 132A (FIG. 11A). Engine 132A has a communication infrastructure 132A-CI, a program portion 132A-P, and a data portion 132A-D. Data representing the state of the various objects executed by engine 132A, e.g., object 140A, are stored in data portion 132A-D of engine 132A. Data portion 132A-D of engine 132A is memory space within memory 117A (FIG. 10) reserved as work space for engine 132A and is generally inaccessible from the perspective of other processes on computer system 120A, e.g. operating system 131A and user application 133A.

As discussed above, an engine effectuates execution of processes and objects. Program portion 132A-P (FIG. 11A) of engine 132A includes computer instructions which effectuate execution of the objects represented in data portion 132A-D. The computer instructions which are combined to form program portion 132A-P can be of a known computer language. For example, the computer software attached as Microfiche Appendix G is a program portion of an engine constructed in accordance with the principles of the present invention and is constructed in accordance with the C++ programming language.

Communication infrastructure 132A-CI of engine 132A includes computer instructions which transport data between engines dispersed throughout network 100. The computer software attached as Microfiche Appendix H, which is a part of this disclosure and is herein incorporated by reference in its entirety, is a communication infrastructure of an engine constructed in accordance with the principles of this invention. Many aspects of the communication infrastructure of an engine are described in greater detail in Appendix D, which is a part of this disclosure and which is incorporated herein by reference in its entirety.

FIG. 11B is an alternative and equivalent representation of the computer network of FIG. 11A.

As indicated by FIG. 11A, engine 132B of computer system 120B is configured in a manner that is directly analogous to the configuration of engine 132A.

Objects within the Network

As explained more completely below, places 220A and 220B (FIG. 4A), agent 150A, ticket 1306, etc. are defined using "objects" according to the principles of this invention. As stated above, objects, which are formed according to the computer instruction set interpreted by engines 132A and 132B and which are interpreted by engine 132A, are stored in data portion 132A-D (FIG. 11A). For example, object 140A in data portion 132A-D is formed according to the computer instruction set interpreted by engines 132A and 132B and is interpreted by engine 132A.

Brief Overview of the Computer Instruction Set of the Present Invention

Each of the novel processes of this invention, and the features needed to define and support the processes, are defined by a set of computer instructions that are interpreted by an engine of this invention. The computer instructions of the present invention are object-oriented. Therefore, data in the present invention, e.g., data which represent agent 150A, are organized into objects, each of which has an internal state and an external behavior. An object's properties define the object's internal state and the object's features define the object's external behavior (see Glossary of Terms above). Each object is an instance of a respective one of a number of classes.

According to the principles of this invention, all classes defined in the computer instruction set, except for mix-in classes which are described below, are subclasses of a class "Object", which is described more completely in Appendix A. Thus, each class that is described herein and which is not a mix-in class inherits the features and properties of class "Object".

In one embodiment, limited multiple inheritance is implemented using mix-in classes. "Mix-ins" or "mix-in classes" are classes which are not subclasses of class "Object". Examples of mix-in classes, which are described below and in Appendix A, include mix-in classes "Executed", "Named" and "Referenced". A non-mix-in class, alternatively called a "flavor" or a "flavor class", can be the immediate subclass of at most one flavor, but can be the immediate subclass of zero or more mix-in classes. A mix-in class can be the immediate subclass of no class or of another mix-in class. Unless otherwise stated, a class is a flavor. No cycles in class hierarchy are permitted; i.e., no class is permitted to be both a subclass and a superclass of another class.

The use of mix-in classes allows features and properties to be defined once and used across a broad variety of classes. For example, mix-in class "Ordered" defines operations for determining the relative order of two objects. Flavor classes "Association", "Citation", "List", "Identifier", "Pattern", "Permit", "Bit", "Boolean", "Character", "Number", "Octet" and "Time" inherit from mix-in class "Ordered". Thus, associations, citations, lists, identifiers, patterns, permits, bits, booleans, characters, numbers, octets and times have an order relative to other members of the same class. For example, in the case of numbers, the number two is "after" the number one and is "before" the number three.

The principal class of objects in the present invention is the class of processes. As described above, processes are either (i) places which are occupied by other processes, or (ii) agents which can (a) transport themselves from a first place, terminating occupancy of the first place, to occupy a second place and (b) interact with other agents occupying the same place.

Agent 150A (FIG. 11A) is a process formed in accordance with the computer instruction set of the present invention whose execution is carried out by engine 132A. Agent 150A can (i) examine and modify itself, (ii) transport itself from a first place in network 100 (FIG. 10) to a second place, and (iii) interact with other agents which occupy the second place.

Herein, a process is described as performing an operation that consumes arguments and produces zero or one result. However, a process, in and of itself, is an object that includes a collection of instructions, which are selected from the instructions described more completely below, and which is interpreted by an engine, e.g., engine 132A which is executing in CPU 110A. The performance of an operation by a process, or any other object of the disclosed instruction set, is in actuality the selection of and interpreting of a particular group of the instructions included in the process or object. Interpreting the instructions of a process by an engine is herein alternatively called "interpreting the process". Thus, when agent 150A performs an operation, agent 150A provides instructions to engine 132A which in turn interprets the instructions and directs CPU 110A to carry out appropriate tasks effectuating performance of the operation by agent 150A. The interaction between a process and an engine is described more completely below.

An important aspect of the present invention is that the set of computer instructions described more completely below is implemented uniformly by the respective computer systems of network 100 (FIG. 10). Computer systems 120A, 120B and 120C can use completely different and incompatible data structures, memory configurations, CPUs and operating systems. But, since an agent is capable of transporting itself to and from any of computer systems 120A, 120B and 120C, it is important that each computer system implement the set of computer instructions of the present invention in a standardized fashion. As long as the computer instructions are uniformly implemented, computer systems 120A, 120B and 120C can be otherwise incompatible. Therefore, agents can travel freely among the computer systems of a heterogeneous, as well as a homogeneous, computer network.

Typically, prior art systems either required that processes travel only within homogeneous networks or that processes be specifically designed to execute computer instructions which were compatible with the computer system within which the process was executing. In the latter case, processes were configured for the particular system requirements of the computer system on which execution of the process began and for the particular system requirements of any computer systems to which the process was intended to travel. Thus, as the computer instructions of an agent of the present invention can execute on any computer system of a heterogeneous network, the present invention represents a substantial improvement over the prior art.

Agents

As discussed above, the behavior of an agent is dependent in part on the internal state of the agent. Therefore, prior to considering the external behavior of an agent in a network, several aspects of the internal state of an agent are briefly discussed. Each agent is a member of class "Agent".

It should be noted that no agents are instances of class "Agent," as class "Agent" is abstract. Class "Agent" is abstract as no implementation for operation "live" is defined or inherited by class "Agent". As discussed below and in Appendix A in greater detail, operation "live" defines the steps that are performed by a process, i.e., an agent or a place, upon creation of the process. These steps are collectively called the "central procedure" of the process. A central procedure for either agents or places is not provided as users of the present invention design and provide central procedures for agents and places to suit the particular needs of each user. Thus, users of the present invention create concrete subclasses of class "Agent" and therein provide implementations for operation "live".

Class "Agent" is a subclass of class "Process". (See FIG. 5.) Class "Process" is a subclass of class "Object" and also inherits from mix-in class "Named". Class "Object" inherits from mix-in class "Referenced". An agent possesses the following attributes: (i) attributes "class" and "size" inherited from superclass "object"; (ii) attribute "isProtected" inherited from mix-in class "Referenced"; (iii) attribute "name" inherited from mix-in class "Named"; and (iv) attributes "brand", "permit" and "privateclasses" inherited from superclass "Process". Class "Agent" defines no attributes. Each of the above-mentioned attributes and classes is discussed in more detail in Appendix A.

Diagram 1270 (FIG. 12) illustrates the class relations of the classes of which agent 150A is a member. Agent 150A is a member of class "Agent" as agent 150A is shown to be contained within domain 1272 which represents class "Agent". Since class "Agent" is abstract, agent 150A is also a member of one or more subclasses (not shown) of class "Agent".

Domain 1272 is completely contained within domain 1274 which represents class "Process". Agent 150A therefore inherits attributes "brand", "permit" and "privateClasses", which are defined by class "Process". Additionally, all members of class "Agent" are also members of class "Process". Thus, as described above, class "Agent" is a subclass of class "Process".

Domain 1274 is completely contained within domain 1276 which represents class "Object". Agent 150A therefore inherits attributes "class" and "size" which are defined by class "Object". Additionally, all members of class "Process", including members of class "Agent", are also members of class "Object". Thus, as described above, class "Process" is a subclass of class "Object".

Domain 1274 representing class "Process" is contained within domain 1278, which represents class "Named". Connection 1278A shows that domain 1274 is contained within domain 1278 while accurately representing that domain 1276, representing class "Object", is not contained within domain 1278 and that domain 1278 is not contained within domain 1276. Class "Named", represented by domain 1278, is a mix-in class. As domain 1274 is contained within domain 1278, agent 150A is contained within domain 1278 and is therefore a member of mix-in class "Named". Mix-in class "Named" defines attribute "name" which is included in agent 150A.

Domain 1280 which represents mix-in class "Referenced" contains domain 1276, which represents class "Object", as indicated by connection 1280A. As domain 1276 is contained within domain 1280, agent 150A is contained within domain 1280 and is therefore a member of mix-in class "Referenced". Mix-in class "Referenced" defines attribute "isprotected" which is included in agent 150A.

As every flavor of the disclosed embodiment of the present invention is a subclass of class "Object", every flavor is also a subclass of mix-in class "Referenced". Thus, it is not necessary to separate the features of class "Referenced" from the features of class "Object". However, the features of mix-in class "Referenced" are separated from the features of class "Object" to aid conceptualization and understanding of the present invention.

As discussed above in the Glossary of Terms, objects are identified within the disclosed computer instruction set by references. As discussed in greater detail below, in directing an object to perform an operation, the object is identified by a reference. Features defined by mix-in class "Referenced" operate on the reference which identifies the object. For example, attribute "isProtected" determines whether the reference to the object, and not the object itself, is protected. Features defined by class "Object" operate on the object identified by the reference. For example, attribute "class" determines of which class the object is an instance.

It should be noted that no attribute is defined which provides information regarding the place occupied by agent 150A (FIG. 12). However, the place occupied by agent 150A is maintained as a property of agent 150A. Agent 150A can determine which place agent 150A occupies by execution of the "here" selector. The execution of selectors, and in particular the "here" selector, is discussed in greater detail in Appendix A. The property which is the place occupied by agent 150A is defined by class "Process". Thus, any process, i.e., either a place or an agent, includes a property which is the place occupied by the process.

While the only class disclosed herein and in Appendix A which is an immediate subclass of mix-in class "Named" is class "Process", subclasses of mix-in class "Named", which are not subclasses of class "Process", are defined by users of the present invention using the instructions disclosed herein and in Appendix A. Therefore, class "Named" is a mix-in class.

Agents as Processes

Associated with every process, both agents and places, is a central procedure which defines the primary behavior of the process as discussed above. The central procedure of a process is the method which implements an operation "live" as performed by the process. An engine initiates processing of a process by causing the process to perform operation "live", thereby causing execution of the process's central procedure. The provision of a method for an operation is discussed in greater detail below. When a process completes performance of operation "live", either successfully or otherwise, the process is terminated. The termination of a process is discussed in section 2.4.11 of Appendix A and that discussion is incorporated herein by reference.

Mobility of Agents: Operation "Go"

As discussed above, an agent travels from one place to another by performance of operation "go". Operation "go" is discussed in the context of the illustrative example of FIGS. 15A-15E. To travel from place 220A to place 220B, agent 150A (FIG. 15A) performs operation "go". FIG. 15A shows the state of network 1500 prior to performance of operation "go" by agent 150A.

Agent 150A owns objects 140A and 140B and occupies place 220A in engine 132A. Thus, agent 150A and place 220A are processes which are simultaneously interpreted by engine 132A. In other words, place 220A and agent 150A are simultaneously performing operation "live". Engine 132B interprets place 220B and agent 150B. Agent 150B occupies place 220B.

Communication infrastructure 132A-CI of engine 132A is connected to communication infrastructure 132Z-CI of engine 132Z by communications link 102AZ. Engine 132Z interprets place 220Z. Communication infrastructure 132Z-CI is also connected to communication infrastructure 132B-CI of engine 132B by communications link 102ZB. While in this embodiment only three computer systems are illustrated in network 1500, the number of computer systems in network 1500 is an arbitrary number, Hence, the computer systems illustrated in FIG. 15A are illustrative of the principles of the invention and are not intended to limit the invention to the particular network illustrated.

Performance of operation "go" by agent 150A, in this embodiment, requires transportation of agent 150A from engine 132A through engine 132Z to engine 132B. Hence, operation "go" requires action on the part of engine 132A, i.e., the source engine, engine 132Z, i.e. the transit engine, and engine 132B, i.e., the destination engine.

Operation "Go" as Performed by the Engine Processing the Source Place

FIG. 13A shows a portion of the internal state, including a portion of the execution state, of agent 150A immediately prior to performance of operation "go" by agent 150A. The execution state of a process is described in greater detail below. Stack 1304 is a part of the execution state of agent 150A. Stack 1304 contains, at top "T", ticket 1306. Ticket 1306 is described more completely below. Arguments consumed by performance of operation "go" are popped from stack 1304 and stack 1304 is therefore the "current stack" in the context of operation "go". Place 220A is a property of agent 150A, indicating that agent 150A occupies place 220A.

FIG. 13B shows a portion of the internal state, including a portion of the execution state, of agent 150A immediately following performance of operation "go" by agent 150A. FIG. 13B is described in greater detail below.

Logic flow diagram 1400 (FIG. 14A) illustrates operation "go" as carried out by engine 132A (FIG. 15A). Engine 132A is the source engine as agent 150A is executing within engine 132A when performance of operation "go" is initiated. The steps of logic flow diagram 1400 (FIG. 14A) are discussed in the context of the trip from place 220A (FIG. 15A) to place 220B taken by agent 150A.

In performance of operation "go" by agent 150A, engine 132A (FIG. 15A) determines whether agent 150A is the agent requesting performance of operation "go" in an access test step 1402 (FIG. 14A). If operation "go" is requested by an object other than agent 150A (FIG. 15A), processing transfers from access test step 1402 (FIG. 14A) to terminal step 1404 in which an exception of class "Process Not Current" is thrown causing operation "go" to fail. If, however, operation "go" is requested by agent 150A (FIG. 15A), processing transfers from access test step 1402 (FIG. 14A) to a "canGo" test step 1406.

In "canGo" test step 1406, engine 132A (FIG. 15A) determines whether agent 150A is permitted to perform operation "go". In "canGo" test step 1406, engine 132A (FIG. 15A), queries attribute "permit" of agent 150A. Attribute "permit" as discussed above, is one of a plurality of attributes of agent 150A. The various attributes of agent 150A are described in greater detail in Appendix A in conjunction with class "Process". The query of attribute "permit" of agent 150A produces property "permit" of agent 150A. Specifically, permit 1612 (FIG. 16) is property "permit" of agent 150A and is therefore produced by querying attribute "permit" of agent 150A. In this embodiment, property "permit" is one of a number of properties of agent 150A.

Permit 1612 (FIG. 17) includes, among several properties which are described in greater detail in Appendix A, properties "charges", "canGo", and "age" which are integer 1702, boolean 1704, and integer 1706, respectively. A boolean is an object having one of only two possible values: "true" or "false". In "canGo" test step 1406 (FIG. 14A), engine 132A (FIG. 15A) queries attribute "canGo" of permit 1612 (FIG. 17), thereby producing boolean 1704 which is property "canGo" of permit 1612, and compares boolean 1704 to "true".

If boolean 1704 has a value of "false", processing transfers from "canGo" test step 1406 (FIG. 14A) to terminal st