Consistent message ordering for semi-active and passive replication
First Claim
1. A method for replicating application program objects using semi-active or passive replication, wherein replicas of said objects are distributed across a plurality of networked computers for fault tolerance, said method comprising:
- creating a primary replica of an object and one or more backup replicas of said object; and
the step of communicating message ordering information from said primary replica to said backup replicas for achieving consistent message ordering among said primary and backup replicas.
3 Assignments
0 Petitions
Accused Products
Abstract
Mechanisms for achieving consistent message ordering within a fault-tolerant distributed computer system based on semi-active or passive replication are described. The mechanisms communicate message ordering information from the primary replica to its backup replicas in such a way as to minimize the end-to-end request/response time, to minimize the number of additional messages that are multicast, and to ensure that, in the event of a fault, a backup replica has, or can obtain, the messages and the message ordering information that it needs to reproduce the actions of the primary replica.
-
Citations
69 Claims
-
1. A method for replicating application program objects using semi-active or passive replication, wherein replicas of said objects are distributed across a plurality of networked computers for fault tolerance, said method comprising:
-
creating a primary replica of an object and one or more backup replicas of said object; and
the step of communicating message ordering information from said primary replica to said backup replicas for achieving consistent message ordering among said primary and backup replicas. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for replicating application program objects using semi-active or passive replication, wherein replicas of said objects are distributed across a plurality of networked computers for fault tolerance, said method comprising:
-
communicating message ordering information from said primary replica to said backup replicas for achieving consistent message ordering among said primary and backup replicas;
wherein said communication of message ordering information to said backup replicas can occur after said primary replica has started processing said messages, and either before or concurrently with the transmission by said primary replica of its next message; and
wherein said communication of message ordering information may be achieved without the transmission of additional messages beyond those required for operation of the networked computers without fault tolerance. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A fault-tolerant computer system, wherein application program objects are replicated using semi-active or passive replication and distributed across a plurality of networked computers, said system comprising:
-
application program object replication software executable on one or more networked computers in said system; and
means associated with said replication software for communication of message ordering information from a primary replica to one or more backup replicas and for achieving consistent message ordering among said primary and backup replicas. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
-
21. A fault-tolerant computer system, wherein application program objects are replicated using semi-active or passive replication and distributed across a plurality of networked computers, said system comprising:
-
application program object replication software executable on one or more networked computers in said system; and
means associated with said replication software for communication of message ordering information from a primary replica to one or more backup replicas and for achieving consistent message ordering among said primary and backup replicas;
wherein said communication of message ordering information to said backup replicas, either directly or indirectly, can occur after said primary replica has started processing said messages, and either before or concurrently with the transmission by said primary replica of its next message; and
wherein said communication of message ordering information may be achieved without the transmission of additional messages beyond those required for operation of said application program objects without fault tolerance. - View Dependent Claims (22, 23, 24, 25, 26)
-
-
27. A computer program executable on one or more computers in a system of networked computers wherein application program objects are replicated using semi-active or passive replication and distributed across a plurality of said networked computers for fault tolerance, said program comprising:
-
instructions for communication of message ordering information from a primary replica of an object to backup replicas of said object for achieving consistent message ordering among said primary and backup replicas wherein said communication of message ordering information to said backup replicas, either directly or indirectly, can occur after said primary replica has started processing said messages, and either before or concurrently with the transmission by said primary replica of its next message; and
wherein said communication of message ordering information may be achieved without the transmission of additional messages beyond those required for operation of said application program objects without fault tolerance. - View Dependent Claims (28, 29, 30, 31, 32)
-
-
33. A computer program executable on one or more computers in a system of networked computers wherein application program objects are replicated using semi-active or passive replication and distributed across a plurality of said networked computers for fault tolerance, said program comprising:
a plurality of executable procedures configured to exploit multicast communication to achieve fault tolerance using semi-active or passive replication of objects with a primary replica and one or more backup replicas, and to maintain a consistent message delivery order across the replicas of an object to achieve strong replica consistency, despite asynchronous message reception, message loss and failure of the replicas, without requiring additional messages in fault-free conditions beyond those required in a system without replication. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69)
Specification