Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-03-31
2001-11-27
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06324590
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a system for controlling and coordinating distributed applications and for maintaining a relativistic view of state which can be used, for example, to insure a consistent view of resources in a distributed computing function.
BACKGROUND OF THE INVENTION
Distributed processing has many different forms and embodies many different techniques depending on the nature of the data and the objectives of a given application. Typical objectives include: transaction performance, locality of data, minimization of network traffic, high availability, minimization of storage requirements, extensibility, cost to produce, etc. Many applications have certain objectives of overriding significance which dictate the distributed processing technique employed.
There is one type of application for which the overriding concern is high availability (resiliency). This type includes switching systems used in a communications network, as well as control systems in the areas of avionics, industrial control, and stock trading. In these systems, it is assumed that any component may fail and the system must continue to run in the event of such failure. These systems are designed to be “fault-tolerant” usually by sacrificing many other objectives (e.g. cost, performance, flexibility and storage) in order to achieve high availability.
Traditionally, fault-tolerant systems have been built as tightly coupled systems with specialized hardware and software components all directed toward achieving high availability. It would thus be desirable to provide a more generally applicable technique for achieving high availability without reliance on specialized components.
Another important factor for a distributed application is the need to know the relative state of a plurality of peer processes before certain actions occur. Such coordination of effort requires that each process know not only what it thinks about the state of the other processes, but also what the other processes think about its state. This is called a “relativistic” view of process state.
For example, assume a system has been developed that uses four cooperating processes to perform a task. Also assume that all four processes must be active before the coordinated task can begin; an active process is defined as a process that has successfully contacted its peers. On system start-up, each process must contact all other processes. After contacting its peers, each process must wait until all other processes have contacted their peers. Thus, only after all processes have contacted their peers, and all the peers know of this contact status, can the task begin.
This is actually a very common situation when attempting to coordinate a task among several processes. It would be desirable to provide a mechanism for gathering a relativistic view of state among various processes.
SUMMARY OF THE INVENTION
In one aspect, the present invention is a method for constructing high-availability distributed applications. This method, referred to herein as “Replicated Resource Management” (RRM), provides a core set of services which enable the replication of data (e.g., state) information in a plurality of processes and optionally the sharing of workload by those processes. This core set of service enables synchronization of each new RRM process with existing RRM processes, recovery in the event of a process level or other failure, and an application level interface (to the RRM) that enables easy and effective use of RRM services in a distributed application.
RRM utilizes a distributed memory space, which an RRM process may examine at will. An RRM process may join and leave a distributed computing function, also at will. The shared memory space persists across process boundaries so long as at least one RRM process remains (or a persistent store is employed).
An analogy may be drawn between RRM and a long-running meeting or plurality of meetings in different rooms. People may come and go from a given meeting, and the meeting may continue indefinitely. As people enter a meeting, they are given information that allows them to participate in the meeting. As they leave, the meeting continues, using information they may have supplied. As long as at least one person remains in the room, the meeting can be said to be continuing (in session). If the last person leaves the room, all information gathered and distributed in the meeting may be recorded, so that an interested party may retrieve this information at a later date.
In the above analogy, the meeting room is analogous to a shared memory space or resource pool. The people participating in the meeting are analogous to RRM processes, and the information exchanged is analogous to RRM resources. This is illustrated in
FIG. 1
, where each RRM process has an associated resource manager (RM) which identifies several resource pools of interest, i.e., several meetings which are of interest to the person. In this way, a resource manager (process) participates in just its areas (pools) of interest, maintains a registry of resources in these associated pools, and includes mechanisms for communicating with other resource managers (processes) in order to maintain a consistent view of the state of the resources in the associated pools.
In another aspect, the invention provides a mechanism which allows a distributed application to develop a “relativistic view” of the state of its processes. More generally, the mechanism may be used to provide a relativistic view of any process or object. In the following discussion, we refer to objects instead of processes. The invention provides three procedures for defining a relativistic view of state, which may be used separately or together.
First, a state vector is provided. This is a one-dimensional associative array of logical object name to logical object state. The name is an “index” into the vector, and the state is stored in a “slot” associated with the index. A state vector is generated by an object and describes what that object thinks is the state of all objects in the vector. It is the object's view of itself and “relative” view of all other objects. A state vector is illustrated in FIG.
4
.
Second, a state matrix (see
FIG. 5
) is a two-dimensional associative array composed of state vectors. Rows and columns of the matrix are indexed by logical object name; the intersection of a row and column defines a “slot”. A row describes what an object thinks is the state of all objects in the row (this is the same as the state vector described above), while a column describes what all objects think is the state of a single object. General rules are provided for determining whether each of the state vectors and/or state matrices is determinant. For example, a determinant contact status may be achieved when every active resource manager agrees on the present state of all other active resource managers.
Third, application specific logic (ASL—i.e., a set of rules specific to an application) may be applied to the general rules associated with state vectors and state matrices for providing application specific state vectors (ASSVs) and application specific state matrices (ASSMs), respectively. Because state vectors and state matrices are objects, ASL may be added to them by derivation. As illustrated in
FIG. 6
, a zero, cardinality relationship (o, m) indicates that a state matrix is composed of zero or many state vectors. This relationship is inherited by the application specific state vectors and application specific state matrices. Again, by way of example, the ASSVs and ASSMs may be used to determine the contact status of processes in a distributed application.
These and other features of the present invention will be more fully understood by the following detailed description and drawings.
REFERENCES:
patent: 5179554 (1993-01-01), Lomicka et al.
patent: 5261044 (1993-11-01), Dey et al.
patent: 5263165 (1993-11-01), Janis
patent: 5485455 (1996-01-01), Dobbins et al.
patent: 6003037 (1999-12-01), Kassabgi et al.
patent: 0447339 A2 (1991-09-01)
Dev Roger
Jeffords Jason
Cabletron Systems Inc.
Courtenay III St. John
Wolf Greenfield & Sacks P.C.
LandOfFree
Replicated resource management system for managing resources... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Replicated resource management system for managing resources..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Replicated resource management system for managing resources... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572017