Selecting values in a distributed computing system

1. A method for selecting a value in a distributed computing system having a maximum number of malicious devices, the method comprising:

transmitting, to a first quorum of devices in the distributed computing system, a request with a client authenticator and a group of forwarded prior vote messages with authenticators, the group of forwarded prior vote messages with authenticators comprising more copies of prior vote messages than three times the maximum number of malicious devices in the distributed computing system, wherein the group of forwarded prior vote messages with authenticators indicate a set of safe values for a proposal number for current and future steps, and further wherein the request with the client authenticator comprises an indication of the proposal number and a requested value from the set of safe values;

receiving, from a second quorum of devices in the distributed computing system, a quorum of properly authenticated vote messages indicating an acceptance of the request; and

transmitting, to a subset of the devices in the distributed computing system, a selection message with authenticator and the quorum of properly authenticated vote messages, the selection message with authenticator indicating that the requested value was selected.

2. The method of claim 1 , wherein the set of safe values is a majority previously voted for request indicated by at least a majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators if the majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators indicated the majority previously voted for request.

3. The method of claim 1 , further comprising:

transmitting, to a third quorum of devices in the distributed computing system, a suggested next proposal number message, comprising a suggested next proposal number;

receiving, from a fourth quorum of devices in the distributed computing system the group of forwarded prior vote messages with authenticators, wherein each prior vote message in the group of forwarded prior vote messages with authenticators comprises an indication of a request previously voted for by an original sending device of a prior vote message and a previously voted proposal number corresponding to the request previously voted for by the original sending device.

4. The method of claim 3 , wherein the proposal number and the suggested next proposal number are larger than a largest previously voted for proposal number in the group of forwarded prior vote messages with authenticators and the requested value is a majority previously voted for request indicated by at least a majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators if the majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators indicated the majority previously voted for request; the method further comprising: receiving a leader invocation request to determine if a client request was voted for by a quorum of devices in the distributed computing system.

5. A method for selecting values in a distributed computing system, the method comprising:

receiving a properly authenticated request;

receiving a group of forwarded prior vote with authenticators messages comprising more copies of prior vote messages than three times the maximum number of malicious devices in the distributed computing system, of which more copies than twice the maximum number of malicious devices in the distributed computing system are properly authenticated, wherein the group of forwarded prior vote messages with authenticators indicate a set of safe values for a proposal number for current and future steps; and

if a sufficient number of devices operate:

transmitting a vote message if the properly authenticated request is contained in the set of safe values and no other request with the proposal number for a current step was previously accepted;

otherwise:

transmitting, to a first quorum of devices in the distributed computing system, an exclusivity message, wherein the exclusivity message indicates a unique proposed value for the proposal number for which a vote can be cast, and wherein the exclusivity message is authenticated for the first quorum of devices;

receiving, from a second quorum of devices in the distributed computing system, a quorum of exclusivity messages authenticated from the second quorum of devices; and

transmitting a vote message if the received quorum of exclusivity messages indicated the properly authenticated request as the unique proposed value and no suggested next proposal number message was responded to.

6. A method for selecting values in a distributed computing system having a maximum number of failed devices, wherein a quorum of devices is a sufficiently large number of devices such that any other quorum of devices shares a majority of its devices with any other quorum, and wherein further a selected value is a proposed value for which at least one quorum of devices votes, the method comprising:

receiving a request to select the proposed value;

transmitting, in response to the received request, a message indicating that the proposed value is safe;

receiving a group of messages from a number of devices greater than three times the maximum number of failed devices, the group of messages indicating that the proposed value is safe; and

voting for the proposed value in response to the received group of messages.

7. The method of claim 6 , wherein transmitting the message indicating that the proposed value is safe comprises transmitting a prior vote message to a leader device, and further wherein the received group of messages is received as a group of forwarded messages with authenticators from the leader device.

8. The method of claim 6 , wherein transmitting the message indicating that the proposed value is safe comprises multicasting the message directly to devices in the distributed computing system, and further wherein the received group of messages is received directly from devices in the distributed computing system.

9. A computer storage medium having computer-executable instructions stored thereon for selecting a value in a distributed computing system having a maximum number of malicious devices, wherein the computer storage medium is not a signal, the computer-executable instructions, when executed on one or more processors, performing operations comprising:

transmitting, to a first quorum of devices in the distributed computing system, a request with a client authenticator and a group of forwarded prior vote messages with authenticators, the group of forwarded prior vote messages with authenticators comprising more copies of prior vote messages than three times the maximum number of malicious devices in the distributed computing system, wherein the group of forwarded prior vote messages with authenticators indicate a set of safe values for a proposal number for current and future steps, and further wherein the request with the client authenticator comprises an indication of the proposal number and a requested value from the set of safe values;

receiving, from a second quorum of devices in the distributed computing system, a quorum of properly authenticated vote messages indicating an acceptance of the request; and

transmitting, to a subset of the devices in the distributed computing system, a selection message with authenticator and the quorum of properly authenticated vote messages, the selection message with authenticator indicating that the requested value was selected.

10. The computer storage medium of claim 9 , wherein the set of safe values is a majority previously voted for request indicated by at least a majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators if the majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators indicated the majority previously voted for request.

11. The computer storage medium of claim 9 , having further computer-executable instructions for performing operations comprising:

transmitting, to a third quorum of devices in the distributed computing system, a suggested next proposal number message, comprising a suggested next proposal number;

receiving, from a fourth quorum of devices in the distributed computing system the group of forwarded prior vote messages with authenticators, wherein each prior vote message in the group of forwarded prior vote messages with authenticators comprises an indication of a request previously voted for by an original sending device of a prior vote message and a previously voted proposal number corresponding to the request previously voted for by the original sending device.

12. The computer storage medium of claim 10 , wherein the proposal number and the suggested next proposal number are larger than a largest previously voted for proposal number in the group of forwarded prior vote messages with authenticators and the requested value is a majority previously voted for request indicated by at least a majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators if the majority of prior vote messages with authenticators in the group of forwarded prior vote messages with authenticators indicated the majority previously voted for request;

the computer storage medium having further computer-executable instructions performing operations comprising: receiving a leader invocation request to determine if a client request was voted for by a quorum of devices in the distributed computing system.

13. A computer storage medium for selecting values in a distributed computing system having a maximum number of malicious devices, wherein the computer storage medium is not a signal, the computer storage medium having computer-executable instructions for performing operations comprising:

receiving a properly authenticated request;

receiving a group of forwarded prior vote messages with authenticators comprising more copies of prior vote messages than three times the maximum number of malicious devices in the distributed computing system, of which more copies than twice the maximum number of malicious devices in the distributed computing system are properly authenticated, wherein the group of forwarded prior vote messages with authenticators indicate a set of safe values for a proposal number for current and future steps; and

if a sufficient number of devices operate:

transmitting a vote message if the properly authenticated request is contained in the set of safe values and no other request with the proposal number for a current step was previously accepted;

otherwise:

transmitting, to a first quorum of devices in the distributed computing system, an exclusivity message, wherein the exclusivity message indicates a unique proposed value for the proposal number for which a vote can be cast, and wherein the exclusivity message is authenticated for the first quorum of devices;

receiving, from a second quorum of devices in the distributed computing system, a quorum of exclusivity messages authenticated from the second quorum of devices; and

transmitting a vote message if the received quorum of exclusivity messages indicated the properly authenticated request as the unique proposed value and no suggested next proposal number message was responded to.

14. A computer storage medium for selecting values in a distributed computing system having a maximum number of malicious devices, wherein the computer storage medium is not a signal, wherein a quorum of devices is a sufficiently large number of devices such that any other quorum of devices shares a majority of its devices with any other quorum, and wherein further a selected value is a proposed value for which at least one quorum of devices votes, the computer storage medium having computer-executable instructions stored thereon and executable on one or more processors for performing operations comprising:

receiving a request to select the proposed value;

transmitting, in response to the received request, a message indicating that the proposed value is safe;

receiving a group of messages from a number of devices greater than three times the maximum number of failed devices, the group of messages indicating that the proposed value is safe; and

voting for the proposed value in response to the received group of messages.

15. The computer storage medium of claim 14 , wherein:

transmitting the message indicating that the proposed value is safe comprises transmitting a prior vote message to a leader device, and

the received group of messages is received as a group of forwarded messages with authenticators from the leader device.

16. The computer storage medium of claim 14 , wherein:

transmitting the message indicating that the proposed value is safe comprises multicasting the message directly to devices in the distributed computing system, and

the received group of messages is received directly from devices in the distributed computing system.

17. A distributed computing system, wherein at least a quorum of devices in the distributed computing system comprise:

one or more processors; and

computer-readable media, in operative communication with the one or more processors, having computer-executable instructions executable by the one or more processors to perform operations comprising:

receiving a properly authenticated request;

receiving a group of forwarded prior vote messages with authenticators comprising more copies of prior vote messages than three times a maximum number of malicious devices in the distributed computing system, of which more copies than twice the maximum number of malicious devices in the distributed computing system are properly authenticated, wherein the group of forwarded prior vote messages with authenticators indicate a set of safe values for a proposal number for current and future steps; and

transmitting a vote message if the properly authenticated request is contained in the set of safe values and no other request with the proposal number for a current step was previously accepted; the distributed computing system comprising a minimum number of devices, wherein the minimum number of devices is greater than three times a sum of the maximum number of malicious devices and a maximum number of failed devices plus twice the maximum number of malicious devices.