Agreement and atomic broadcast in asynchronous networks
First Claim
Patent Images
1. A method comprising:
- achieving agreement among n participating network devices in an asynchronous network for deciding on a common value (v) being validated by a justification (p) together satisfying a predetermined predicate (Q), a agreement arising out of a series of messages being sent and received by each participating network device with up to a number t of faulty devices, each participating network device performing the following steps;
i) broadcasting to the participating network devices an echo message comprising a proposed value (w) and a proposed justification (π
) by using verifiable and consistent broadcast;
ii) receiving n−
t echo messages comprising candidate values (w1, w2, w3) and candidate justifications (π
1, π
2, π
3) satisfying the predicate (Q), and repeating the following steps
1) to
3) for each participating network device as a candidate device represented by a candidate device identifier (a) according to an order;
1) broadcasting to all participating network devices a vote message comprising the candidate device identifier (a), and either a first agree-value (Y) together with the candidate value (wa) and the candidate justification (π
a), or a second agree-value (N), 2) receiving vote messages and counting up to n−
t vote messages including the second agree-value (N) or the first agree-value (Y), the candidate value (wa), and the candidate justifications (π
a) satisfying the predicate (Q), 3) performing a Byzantine agreement to determine whether the candidate device has sent the candidate value (wa) and the candidate justification (π
a) satisfying the predicate (Q), iii) in response to the result of the Byzantine agreement, deciding the common value (v) proposed as the candidate value (w) and the justification (p) proposed as the candidate justification (π
) of an agreed candidate device.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods and apparatus for achieving agreement among participating network devices in an asynchronous network for deciding on a common value is disclosed, whereby the common value is validated by a justification and both together satisfy a predetermined predicate. Moreover, a method for reliably broadcasting messages in an order within the asynchronous network is described. Up to one third or more of the participating network devices might be faulty in arbitrary ways.
-
Citations
21 Claims
-
1. A method comprising:
achieving agreement among n participating network devices in an asynchronous network for deciding on a common value (v) being validated by a justification (p) together satisfying a predetermined predicate (Q), a agreement arising out of a series of messages being sent and received by each participating network device with up to a number t of faulty devices, each participating network device performing the following steps;
i) broadcasting to the participating network devices an echo message comprising a proposed value (w) and a proposed justification (π
) by using verifiable and consistent broadcast;
ii) receiving n−
t echo messages comprising candidate values (w1, w2, w3) and candidate justifications (π
1, π
2, π
3) satisfying the predicate (Q), and repeating the following steps
1) to
3) for each participating network device as a candidate device represented by a candidate device identifier (a) according to an order;
1) broadcasting to all participating network devices a vote message comprising the candidate device identifier (a), and either a first agree-value (Y) together with the candidate value (wa) and the candidate justification (π
a), or a second agree-value (N),2) receiving vote messages and counting up to n−
t vote messages including the second agree-value (N) or the first agree-value (Y), the candidate value (wa), and the candidate justifications (π
a) satisfying the predicate (Q),3) performing a Byzantine agreement to determine whether the candidate device has sent the candidate value (wa) and the candidate justification (π
a) satisfying the predicate (Q),iii) in response to the result of the Byzantine agreement, deciding the common value (v) proposed as the candidate value (w) and the justification (p) proposed as the candidate justification (π
) of an agreed candidate device.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
13. A method for reliably broadcasting messages in an order within an asynchronous network comprising n participating network devices and tolerating a number t of less than n/3 faulty participating network devices, each participating network device storing a queue (q) and a log (d), the method operating in rounds, each round comprising the following steps:
-
i) responsive to a message broadcast request comprising a message value (m) performing the step of;
appending the message value (m) to the queue (q) unless the log (d) or the queue (q) comprises the message value (m),ii) deriving a signature (σ
) on the queue (q),iii) broadcasting to all participating network devices a queue message comprising the queue (q) and the signature (σ
),iv) receiving a number c of at least t+1 queue messages comprising c proposed queues and proposed signatures, v) storing the proposed queues in a queue vector (QV) and the proposed signatures in a signature vector (SV), vi) proposing the queue vector (QV) for Byzantine agreement validated by the signature vector (SV) and performing a method for achieving agreement on a common value being validated by a justification (p) together satisfying a predetermined predicate (Q) by validating the queue vector (QV) and the signature vector (SV) through a determined predicate (Q) asserting that the signature vector (SV) comprises c valid signature entries of distinct participating network devices (A, B, C) on entries of the queue vector (QV), vii) preparing in response to the result of the Byzantine agreement an ordered list (L) of unique message values out of the entries of the decided queue vector (DQV) viii) accepting the unique message values in the ordered list (L) in the sequence of the ordered list (L), ix) appending the accepted unique message values to the log (d). - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
20. A system comprising:
means for achieving agreement among n participating network devices in an asynchronous network for deciding on a common value (v) being validated by a justification (p) together satisfying a predetermined predicate (Q), the agreement arising out of a series of messages being sent and received by each participating network device with up to a number t of faulty devices, each participating network device including;
i) means for broadcasting to the participating network devices an echo message comprising a proposed value (w) and a proposed justification (π
) by using verifiable and consistent broadcast;
ii) means for receiving n−
t echo messages comprising candidate values (w1, w2, w3) and candidate justifications (π
1, π
2, π
3) satisfying the predicate (Q), and repeating the following steps
1) to
3) for each participating network device as a candidate device represented by a candidate device identifier (a) according to an order;
3) means for broadcasting to all participating network devices a vote message comprising the candidate device identifier (a), and either a first agree-value (Y) together with the candidate value (wa) and the candidate justification (π
a), or a second agree-value (N),2) means for receiving vote messages and counting up to n−
t vote messages including the second agree-value (N) or the first agree-value (Y), the candidate value (wa), and the candidate justifications (π
a) satisfying the predicate (Q),3) means for performing a Byzantine agreement to determine whether the candidate device has sent the candidate value (wa) and the candidate justification (π
a) satisfying the predicate (Q),iii) means for deciding in response to the result of the Byzantine agreement, the common value (v) proposed as the candidate value (w) and the justification (p) proposed as the candidate justification (π
) of an agreed candidate device.- View Dependent Claims (21)
Specification