Consensus algorithm. A partially synchronous algorithm for Byzantine agreement when n > 3t and ℓ > t is shown in Figure 7. It uses the authenticated broadcast primitive described in the previous subsection and follows the same general pattern as the algo- rithm of Dwork, Xxxxx and Xxxxxxxxxx [9]. Each iteration of the main loop is called a phase, which takes four super- rounds. Each process has a proper variable, which stores a set of val- ues that can be output without violating validity. Initially, only the process’s own value is in this set. In each round, each process updates its proper variable as follows. Each process appends its proper set to each message it sends. If a process receives proper sets containing v in t + 1 messages in the same round, it adds v to its own proper set. Also, if a process has received proper sets in 2t + 1 messages during the round and no value appears in t + 1 of them, the process adds all possible input values to its own proper set. Consider a process p executing the algorithm. There are sev- eral times when p needs to have an estimate of the number of processes that performed a broadcast of a particular mes- sage m in an earlier superround r ≤ r′. During superround r′, p performs a number of Accept(i, α , m, r). For each identifier i, αi is p’s estimate of the number of processes with identifier i that performed Broadcast(i, m, r). We say that the number of witnesses that p has in superround ′ ond round of the superround). Process p must have re- ceived at least n − t messages containing tuples of the form r for (m, r) is the sum, over all i, of the αi’s that appear in all Accept(i, αi, m, r) actions that p performs during su- ′ ′ perround r . It follows from the properties of authenticated (echo, i, α , m, r) with α ≥ α in this round. Among the n− t senders of these messages, at least n − 2t are correct. Since the value stored in each sender’s a[i, m, r] variable can only increase, each of these n − 2t correct senders also sends a broadcast that this estimate will eventually be at least as large as the actual number of correct processes that per- formed Broadcast(∗, m, r) and exceed that number by at most t. ′ ′ tuple of the form (echo, i, α , m, r) with α ′ ≥ α in round xxx(r , T ). All of these messages are delivered. Thus, for each correct process, the value of a[i, m, r] is at least α af- ′ ter the process executes line 18 in superround max(r , T ). For the remainder of this section, we consider an execution in which fi processes with ...
