US 7,249,280 B2 · Cheap paxos

Abstract

A distributed computing system can be operated in a fault tolerant manner using a collection of auxiliary computing devices and more main computing devices than the number of faults the system can tolerate. A quorum of all of the main computing devices can be used. In the event of a failure, an alternative quorum from a selected set of quorums, comprising at least one main computing device and some or all of the auxiliary computing devices, can be used to complete pending operations and to select a new set of quorums. Alternatively, another state machine, comprising at least one main computing device and some or all of the auxiliary computing devices, can select a new quorum comprising the currently operating main computing devices, and the new quorum can then complete pending operations and can continue to select proposals using the proposal number assigned by the other state machine.

Claims39

Dependent claims

A method for selecting a value in a distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the method comprising the steps of:

proposing a first set of quorums comprising a first preferred quorum comprising all of the operational main computing devices and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed first set of quorums share at least one computing device;
receiving a first set of vote responses from a first quorum, wherein the first quorum comprises at least one operational main computing device;
and
if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums:
proposing the value to a second quorum from the first set of quorums;
receiving a second set of vote responses from the second quorum;
and
determining that the value was selected if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value.

5 more elements

A computer-readable storage medium having computer-executable instructions for selecting a value in a distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the computer-executable instructions performing steps comprising:

proposing a first set of quorums comprising a first preferred quorum comprising all of the operational main computing devices and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed first set of quorums share at least one computing device;
receiving a first set of vote responses from a first quorum, wherein the first quorum comprises at least one operational main computing device;
and if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums:
proposing the value to a second quorum from the first set of quorums;
receiving a second set of vote responses from the second quorum;
and determining that the value was selected if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value.

3 more elements

A main computing device operating as part of a distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the main computing device comprising:

a processing unit performing steps comprising:
proposing a first set of quorums comprising a first preferred quorum comprising all of the operational main computing devices and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed first set of quorums share at least one computing device;
if a first set of vote responses indicate that every computing device in a first quorum has voted for the proposed set of quorums, proposing the value to a second quorum from the first set of quorums;
and
if a second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value, determining that the value was selected;
and
a network interface performing steps comprising:
receiving the first set of vote responses from the first quorum, wherein the first quorum comprises at least one operational main computing device;
and
receiving a second set of vote responses from the second quorum.

7 more elements

Dependencies are inferred from the claim text.

Cheap paxos

Life of this patent

Cheap paxos

Life of this patent

Abstract

Claims39