Arbitration of state changes

Details Arbitration of state changes Arbitration of state changes

1999-06-29

2003-01-28

Follansbee, John A. (Department: 2156)

Electrical computers and digital data processing systems: input/

Access arbitrating

Decentralized arbitrating

Reexamination Certificate

active

06513084

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to distributed computer systems, and more particularly to arbitrating changes in state for entities shared among such distributed computer systems.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent 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 file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright © 1998, Microsoft® Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
In a network in which multiple computers each process changes against the state of a shared entity, there must be a mechanism through which the computers cooperate when making the changes in such a way that all the computers come to the same decision about how the state should be changed. Locking and other synchronization primitives provide a way for multiple threads to coordinate changes to the same entity on the same computer. Across networked computers, however, some other synchronization mechanism is needed so that simultaneous changes to the same entity can be reconciled consistently by all the computers that share that object.
One previous solution to the problem designates a single computer in the network as a lock manager. The lock manager acts as a lock server to which the client computers in the network send their changes. The lock manager serializes the changes to ensure an orderly state change for shared entities. This solution is not entirely satisfactory. Not only is the lock manager a bottleneck in the processing of transactions through the network, but the computer acting as the lock manager must incorporate complex failsafe technology to prevent total shutdown of the network due to the failure of the lock server.
Other solutions focus on distributed locking protocols. A distributed locking protocol requires the implementation of a messaging protocol to handle the locking of the shared entity and to coordinate the changes among the computers so that the changes are applied in the proper order. While a distributed locking protocol does not rely on a designated computer to provide locking, only one computer in the network at a time manages the messaging protocol and so is subject to the same limitations as the lock manager solution.
Therefore, there is a need in the art for a mechanism that allows the distribution of the state change decision process among the interested computers, and which does not depend upon locking to ensure the proper ordering of the changes.
SUMMARY OF THE INVENTION
The above-mentioned shortcomings, disadvantages and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
When multiple nodes in a computer network perform work on a shared entity, such as a database record, an arbitration process is used to ensure changes made by more than one node to the same data is propagated to each of the nodes holding the shared entity and that the changes are applied in the same order on each of the nodes. An arbitration cycle for a particular entity is begun on a node (“instigator”) when the node broadcasts a proposal message for a change to the entity to the other nodes or when the node (“observer”) receives such a proposal message. Multiple nodes can be instigators during a single arbitration cycle. Each node that receives a proposal message sends a response message to the corresponding instigator. The arbitration cycle is closed to additional proposal messages after one instigator has received responses from all the nodes that share the entity. After each instigator node receives all the proposals in the arbitration cycle, it determines whether it is the winner of the arbitration cycle and broadcasts a closure message if it is. Each node determines an order in which to apply the changes proposed in the arbitration cycle when it knows it has received all the proposals in the arbitration cycle as determined by the sending or receiving of the closure message. Because each arbitration cycle is associated with a particular entity, multiple arbitration cycles associated with different items can be running concurrently in the network but multiple arbitration cycles for the same item must be executed serially. The arbitration process is executed even if there is only one proposal made in an arbitration cycle since the arbitration process enables the orderly propagation of changes across all the nodes.
A particular implementation of the arbitration logic in conjunction with an in memory database that provides coherent caching among networked database client computers is disclosed.
The arbitration process of the present invention sends the changes as part of the messages required for synchronization and also provides for a much richer solution to the problem of asynchronous changes, e.g., rejecting certain changes, ordering changes, etc. depending on the type of entity being changed. Furthermore, a centralized lock service is not required as each computer in the network individually makes the determination of how to change the entity within its own cache.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.


REFERENCES:
patent: 4914569 (1990-04-01), Levine et al.
patent: 5167022 (1992-11-01), Bahr et al.
patent: 5418967 (1995-05-01), Simcoe et al.
patent: 5794034 (1998-08-01), Harinarayan et al.
patent: 5832508 (1998-11-01), Sherman et al.
patent: 5835766 (1998-11-01), Iga
patent: 5878410 (1999-03-01), Zbikowski et al.
patent: 6029177 (2000-02-01), Sadiq et al.
patent: 6240479 (2001-05-01), Snyder et al.
patent: 6249846 (2001-06-01), Van Doren et al.
“TimesTen 3.7—In-Memory Database for 32-bit and 64-bit Operating Systems”, TimesTen Performance Software, http://timesten.com/products/ttdatasheet.html, 11 p., (Jun., 1999).
“TimesTen In-Memory Data Management—Technical White Paper”, Technical White Paper, TimesTen Performance Software, http://www.timesten.com/products/wp.html, 15 p., (2000).

Affiliated with

Also associated with

Rating

Arbitration of state changes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arbitration of state changes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration of state changes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3009268