Fast byzantine paxos
First Claim
1. A method for selecting values in a distributed computing system having a maximum number of malicious devices, the method 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
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.
3 Assignments
0 Petitions
Accused Products
Abstract
A distributed computing system can operate in the face of malicious failures on the part of some of its constituent devices, and provide a minimum of message delays between receiving a client request and providing a response, when each device within the system verifies the sender of any message it receives, and the propriety of the message. The sender can be verified through message authentication schemes or digital signature schemes. The propriety of a message can be verified by receiving a sufficiently large number of equivalent, properly authenticated messages. If the number of malicious devices is represented by the variable “M”, a sufficient number of equivalent, properly authenticated messages to verify that the message is true can be any number of messages greater than M. Furthermore, to verify that a leader device is not maliciously submitting different proposals to different devices using the same proposal number, a quorum of devices can be required to select a proposal, where a quorum is a sufficiently large number of devices such that any other quorum has, as a majority of its devices, non-malicious devices from the first quorum. Therefore, the distributed computing system can operate properly with M number of malicious failures and F number of total failures, and with a minimum of message delays, if the number of constituent devices in the distributed computing system is greater than 3F+2M. Additionally, if the distributed computing system can revert to a more traditional algorithm if too many devices fail or become malicious, it can use a message-delay-reducing algorithm while having as few as 2Q+F+2M+1 constituent devices, where Q is the number of devices that can fail and still allow the system to use a message-delay-reducing algorithm.
84 Citations
15 Claims
-
1. A method for selecting values in a distributed computing system having a maximum number of malicious devices, the method 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 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. - View Dependent Claims (2, 3, 4)
-
-
5. A computer-readable storage medium having computer-executable instructions for selecting values in a distributed computing system having a maximum number of malicious devices, the computer-executable instructions performing steps 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 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. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12)
-
-
13. A distributed computing system, wherein at least a quorum of devices in the distributed computing system comprise computer-readable storage media having computer-executable instructions for performing steps 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 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;the distributed computing system comprising a minimum number of devices, wherein the minimum number of devices is greater than;
a sum of a maximum number of failed devices and the maximum number of malicious devices plus twice the maximum number of malicious devices plus twice a maximum number of failed and malicious devices that can be accommodated, wherein the sufficient number of operating devices is at least the minimum number of devices minus the maximum number of failed and malicious devices that can be accommodated. - View Dependent Claims (14, 15)
-
Specification