Patent ID: 7856502

Claim:
A method for selecting a value in a distributed computing system implementing a system state machine that selects the value and a quorum selection state machine separate from the system state machine, the distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the method comprising the steps of: proposing, to a first set of computing devices in the distributed computing system, a first proposal comprising: a first quorum, a first leader computing device for the first quorum, and a first proposal number associated with the first quorum and the first leader computing device, wherein: the first quorum implements the system state machine and comprises all operational main computing devices of the distributed computing system, and wherein the first set of computing devices implements the quorum selection state machine and comprises at least a majority of computing devices of the distributed computing system; receiving a first set of vote responses from the first set of computing devices; and if the first set of vote responses indicate that, from the first set of computing devices, at least a majority of computing devices of the distributed computing system has voted for the first proposal, transmitting a notification of a selection of the first proposal, wherein: proposing the first proposal number comprises proposing the first proposal number to a second set of computing devices; and the second set of computing devices is selected such that, for a series of proposal numbers from an overall largest proposal number, among the largest proposal numbers to which one or more responding computing devices have previously responded, until the first proposal number, at least one of the one or more responding computing devices has been in quorums corresponding to the series of proposal numbers.