US 8,135,987 B2 · Collection ordering for replicated state machines

Abstract

A replicated state machine with N replica servers may be configured to tolerate a count of F faults. A first operation (of a first ordering type) executes when a first quorum of correctly functioning replicas is available. A second operation (also of the first operation type) executes when a second quorum of correctly functioning replicas is available. A third operation (of a second ordering type) executes when a third quorum of correctly functioning replicas are available. The operations are executed by the replicated state machine such that: (1) the replicated state machine does not guarantee operational ordering between the first operation and the second operation; (2) the replicated state machine guarantees ordering between the first operation and the third operation; and (3) the replicated state machine guarantees ordering between the second operation and the third operation.

Claims20

Dependent claims

A replicated state machine comprising:

N replica servers, the replicated state machine configured to tolerate a count of F faults, wherein a first operation executes when a first quorum of correctly functioning replicas are available, a second operation executes when a second quorum of correctly functioning replicas are available, and a third operation executes when a third quorum of correctly functioning replicas are available, where the operations are executed by the replicated state machine such that:
the replicated state machine does not guarantee operational ordering between the first operation and the second operation;
the replicated state machine guarantees ordering between the first operation and the third operation;
and
the replicated state machine guarantees ordering between the second operation and the third operation.

2 more elements

A method performed by a replicated state machine comprised of a plurality of replica server computers, wherein each replica server maintains its own copy of the state of the replicated state machine, and where operations submitted to the replicated state machine are replicated on varying quorums of the replica servers, the method comprising:

receiving a first plurality of operations, and guaranteeing that the first plurality of operations will all be applied to the replicated state machine despite faults that prevent the replicated state machine from applying the first plurality of operations to each replica server, wherein the first plurality of operations are all of a first ordering type, the first ordering type such that operations of the first ordering type are not guaranteed to be applied to the replicated state machine in a consistent order;
receiving a second plurality of operations, and guaranteeing that the second plurality of operations will all be applied to the replicated state machine despite faults that prevent the replicated state machine from applying the second plurality of operations to each replica server, wherein the second plurality of operations are all of a second ordering type, the second ordering type such that operations of the second ordering type are guaranteed to be applied to the replicated state machine in a consistent order, and each operation of the first type is guaranteed to be applied in a consistent order with respect to operations of the second type.

Dependencies are inferred from the claim text.

Collection ordering for replicated state machines

Life of this patent

Collection ordering for replicated state machines

Life of this patent

Abstract

Claims20