Patent ID: 6957331

Claim:
A method for achieving agreement among n participating network devices to a first agree-value (Y) or a second agree-value (N) in an asynchronous 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) broadcasting to the participating network devices a pre-vote message comprising a pre-vote variable with a first pre-vote value or a second pre-vote value, and comprising a first signature proving the pre-vote and a second signature justifying the pre-vote variable; ii) once having received n−t valid of the pre-vote messages with pre-vote variables from the participating network devices, performing a main-vote to obtain a main-vote variable with either a first main-vote value, a second main-vote value, or a third main-vote value, whereby if all n−t pre-vote variables have the first pre-vote value then the first main-vote value is obtained, or if all n−t pre-vote variables have the second pre-vote value then the second main-vote value is obtained, or if the n−t pre-vote variables are different then the third main-vote value is obtained; iii) broadcasting to the participating network devices a main-vote message comprising the obtained main-vote variable, the first signature and the second signature; and iv) once having received n−t valid of the main-vote messages, performing a decision, if all n−t main-vote variables have the first main-vote value then deciding for the first agree-value or if all n−t main-vote variables have the second main-vote value then deciding for the second agree-value, thereby having achieved the agreement, and helping the other participating network devices to decide; otherwise i) broadcasting to the participating network devices a share-value(g x A,B,C,D ) to generate an unpredictable bit ∈{Y, N}; ii) receiving at least k share-values (g x A , g x B , g x C , g x D ) from the participating network devices, where k is a number larger than t, assembling out of those a common value and deriving one bit thereof; and iii) repeating the steps starting from a), whereby if all n−t main-vote variables have the third main-vote value then the binary value is used as the pre-vote variable, or if at least one of all n−t main-vote variables has the first main-vote value then the first pre-vote value is used as the pre-vote variable, or if at least one of all n−t main-vote variables has the second main-vote value then the second pre-vote value is used as the pre-vote variable.