The B-Consensus Algorithm Sample Clauses

The B-Consensus Algorithm. We initially provide an overview of the algorithm and then its description in detail (see Algo- rithm 1). Similarly to Ben-Or’s algorithm, our algorithm requires f < n/2 (i.e., a majority of correct processes). Overview of the algorithm. The algorithm executes in a sequence of rounds, where each round has three stages (see Figure 2 — for clarity, messages from a process to itself have been omitted). In the first stage of the round, processes query the 1-WAB oracle, which propagates 4From here on, “consensus” implicitly means “uniform consensus.” their estimates to the other processes and wait for the first message output by the oracle in the current round. The second and third stages are used to determine whether a majority of processes output the same estimate in the first stage. 1st stage 2nd stage 3rd stage propose(v) . . . p1 p2 pn Figure 2: One round of the B-Consensus algorithm decide(v) In the second stage, a process sends its current estimate (updated in the first stage) to the other processes and waits for the first n − f messages of the same kind. If the n − f messages received contain the same estimate value v, the process takes v as its estimate; otherwise it takes a void value as its estimate. Notice that the majority constraint guarantees that the only possible outcomes of the second stage for all processes is either v or void. In the third stage, each process sends its estimate to the other processes and again waits for n− f responses. If the same non-void value is received from f + 1 processes, the process decides if it has not yet decided in a previous round, and proceeds to the next round. The algorithm, as it is, requires processes to keep executing even after they have already decided on some value. We address this issue in Section 4. B-Consensus in detail. Algorithm 1 (page 8) is the B-Consensus algorithm. In each round (lines 6–24), every process p first queries the oracle (line 6), waits for the first answer tagged with the current round number rp (line 7) and updates its estimatep value (line 8). Then p sends estimatep to all in a message of type first (line 9) and waits for n − f such messages (line 10). After updating estimatep, process p sends again estimatep to all in a message of type second (line 15) and waits for n − f such messages. If f + 1 messages received contain a value v different from ⊥ then p decides v (line 18). Even after deciding, p continues the algorithm. Compared to Ben-Or’s algorithm (Appendix A, Algorithm 5), lines 6...

The B-Consensus Algorithm. We initially provide an overview of the algorithm and then its description in detail (see Algorithm 1). Similarly to Ben-Or’s algorithm, our algorithm requires f < n/2 (i.e., a majority of correct processes).