Method of achieving optimistic multiple processor agreement in potentially asynchronous networks
AssigneeInternational Business Machines Corporation
InventorsKlaus Kursawe, Victor Shoup
Life of this patent
Estimating the term…
Abstract
A method for achieving agreement among n participating network devices to an agree-value in a network is disclosed. The method proposes an optimistic approach to the consensus problem, whereby the number t of faulty devices is less than n/3. It is distinguished between an optimistic and pessimistic case. In the pessimistic case, a fallback agreement protocol is performed that reaches the same agree-value as the method in the optimistic case outputs.
Claims27
A method for achieving agreement among n participating network devices to an agree-value in a network, the agreement arising out of a series of messages being sent and received by each participating network device, whereby the number t of faulty devices is less than n/3, each participating network device performing the following steps:
- a) broadcasting to the participating network devices an init-vote message comprising an init-vote value;
- b) once having received one of n valid of the init-vote messages with init-vote values from the participating network devices and a signal from a failure detector,
- evaluating the received init-vote values to obtain a verification-vote value whereby the verification-vote value is an evaluating function of the received init-vote values;
- c) broadcasting to the participating network devices a verification-vote message comprising the obtained verification-vote value;
- and
- d) once having received n of the verification-vote messages comprising the same verification-vote value,
- deciding the agree-value to be equal to the same verification-vote value, or having received a signal from any failure detector;
- e) broadcasting to the participating network devices a signed verification-vote message comprising the obtained verification-vote value and a signature;
- and
- f) once having received n-t signed verification-vote messages, performing a fallback agreement protocol with an initial value that has the simple majority of the received obtained verification-vote values.
A method for achieving agreement among n participating network devices to an agree-value in a network, the agreement arising out of a series of messages being sent and received by each participating network device, whereby the number t of faulty devices is less than n/3, each participating network device performing the following steps:
- i) performing for a number of honest participating network devices that exceeds 2n/3 an agreement protocol that comprises failure detection;
- ii) performing a validation protocol, using detector means that validates whether agreement is reached;
- and
- iii) deciding for the agree-value in the case that at least x of the participating network devices agree, where x is a number larger than t, or
- performing a fallback agreement protocol if at least one participating network device suspects that the agreement is not reached, the fallback agreement protocol producing the same agree-value value if at least one of the honest participating network devices has already decided for the agree-value.
A computer program comprising program code means for performing the method for achieving agreement among n participating network devices to an agree-value in a network, the agreement arising out of a series of messages being sent and received by each participating network device, whereby the number t of faulty devices is less than n/3, each participating network device, said method comprising the steps of:
- (a) broadcasting to the participating network devices an init-vote message comprising an init-vote value;
- (b) once having received one of n valid of the init-vote messages with init-vote values from the participating network devices and a signal from a failure detector, evaluating the received init-vote values to obtain a verification-vote value whereby the verification-vote value is an evaluating function of the received init-vote values;
- (c) broadcasting to the participating network devices a verification-vote message comprising the obtained verification-vote value;
- and
- (d) once having received n of the verification-vote messages comprising the same verification-vote value, deciding the agree-value to be equal to the same verification-vote value, or having received a signal from any failure detector;
- (e) broadcasting to the participating network devices a signed verification-vote message comprising the obtained verification-vote value and a signature;
- and
- (f) once having received n-t signed verification-vote messages, performing a fallback agreement protocol with an initial value that has the simple majority of the received obtained verification-vote.
A computer program device readable by machine tangibly embodying a program of instructions executable by the machine for performing the method for achieving agreement among n participating network devices to an agree-value in a network, the agreement arising out of a series of messages being sent and received by each participating network device, whereby the number t of faulty devices is less than n/3, each participating network device, said method comprising the steps of:
- (a) broadcasting to the participating network devices an init-vote message comprising an init-vote value;
- (b) once having received one of n valid of the init-vote messages with init-vote values from the participating network devices and a signal from a failure detector, evaluating the received init-vote values to obtain a verification-vote value whereby the verification-vote value is an evaluating function of the received init-vote values;
- (c) broadcasting to the participating network devices a verification-vote message comprising the obtained verification-vote value;
- and
- (d) once having received n of the verification-vote messages comprising the same verification-vote value, deciding the agree-value to be equal to the same verification-vote value, or having received a signal from any failure detector;
- (e) broadcasting to the participating network devices a signed verification-vote message comprising the obtained verification-vote value and a signature;
- and
- (f) once having received n-t signed verification-vote messages, performing a fallback agreement protocol with an initial value that has the simple majority of the received obtained verification-vote.
A computer program comprising program code means for performing the method for achieving agreement among n participating network devices to an agree-value in a network, the agreement arising out of a series of messages being sent and received by each participating network device, whereby the number t of faulty devices is less than n/3, each participating network device performing the following steps:
- i) performing for a number of honest participating network devices that exceeds 2n/3 an agreement protocol that comprises failure detection;
- ii) performing a validation protocol, using detector means that validates whether agreement is reached;
- and
- iii) deciding for the agree-value in the case that at least x of the participating network devices agree, where x is a number larger than t, or performing a fallback agreement protocol if at least one participating network device suspects that the agreement is not reached, the fallback agreement protocol producing the same agree-value value if at least one of the honest participating network devices has already decided for the agree-value.
A computer program product readable by machine tangibly embodying a program of instructions executable by the machine for performing the method for achieving agreement among n participating network devices to an agree-value in a network, the agreement arising out of a series of messages being sent and received by each participating network device, whereby the number t of faulty devices is less than n/3, each participating network device performing the following steps:
- i) performing for a number of honest participating network devices that exceeds 2n/3 an agreement protocol that comprises failure detection;
- ii) performing a validation protocol, using detector means that validates whether agreement is reached;
- and
- iii) deciding for the agree-value in the case that at least x of the participating network devices agree, where x is a number larger than t, or performing a fallback agreement protocol if at least one participating network device suspects that the agreement is not reached, the fallback agreement protocol producing the same agree-value value if at least one of the honest participating network devices has already decided for the agree-value.
Dependencies are inferred from the claim text.