` 24 D. Mazieres that “a ∨ accept(a)” is what each node must assert for a quorum to accept a under condition 1 of the definition of accept. For convenience, when comparing state across nodes, we will identify fields belong- ¨ ing to particular nodes with subscripts. If v is a node, then we write b ,p ,p ,… to v v v denote the values of b,p,p¨,… in node v’s state as described in Figure 16. Similarly, we ¨ let v denote message m’s sender, and b ,p ,p ,… denote the corresponding values of m m m m b,p,p¨,… in v ’s state as implied by m. m Each node initializes its ballot state for a slot by setting ' ← PREPARE, z ← ⊥, ¨ b ← ⟨0,z⟩, M ← ç, and all other fields (p,p ,c,ℎ) to the invalid ballot 0. While z = ⊥, a node can receive but not send ballot messages. Once z ≠ ⊥, if b.n = 0, a node reinitializes b ← ⟨1,z⟩ to start sending messages. Nodes then repeatedly exchange messageswithpeers,sendingwhicheverballotmessageisindicatedby'.Uponadding anewlyreceived message m to M , a node v updates its state as follows: v ¨ (1) If ' = PREPARE and m lets v accept new ballots as prepared, update p and p . Afterwards, if either p ⋧ ℎ or p¨ ⋧ ℎ, then set c ← 0. (2) If ' = PREPARE and m lets v confirm new higher ballots prepared, then raise ℎ to the highest such ballot and set z ← ℎ.x. ¨ (3) If ' = PREPARE, c = 0, b ≤ ℎ, and neither p ⋧ ℎ nor p ⋧ ℎ, then set c to the lowest ballot satisfying b ≤ c ≲ ℎ. (4) If ' = PREPARE and v accepts commit for one or more ballots, set c to the lowest such ballot, then set ℎ to the highest ballot such that v accepts all {commit b¨ ∣ ¨ c ≲ b ≲ ℎ}, and set ' ← CONFIRM. Also set z ← ℎ.x after updating ℎ, and unless ℎ≲b,setb←ℎ. (5) If ' = CONFIRM and the received message lets v accept new ballots prepared, raise p to the highest accepted prepared ballot such that p ∼ c. (6) If ' = CONFIRM and v accepts more commit messages or raises b, then let ℎ¨ be the highest ballot such that v accepts all {commit b¨ ∣ b ≲ b¨ ≲ ℎ¨} (if any). If there exists such an ℎ¨ and ℎ¨ > ℎ, then set ℎ ← ℎ¨, and, if necessary, raise c to ¨ ¨ the lowest ballot such that v accepts all {commit b ∣ c ≲ b ≲ ℎ}. (7) If ' = CONFIRM and v confirms commit c¨ for any c¨, set c and ℎ to the lowest and highest such ballots, set ' ← EXTERNALIZE, externalize c.x, and terminate. (8) If ' ∈ {PREPARE,CONFIRM} and b < ℎ, then set b ← ℎ. (9) If ' ∈ {PREPARE,CONFIRM} and ∃S ⊆ M such that the set of senders {v ¨ ∣ ¨ ¨ v m m ∈ S} is v-blocking and ∀m ∈ S, b ¨.n > b .n, then set b ← ⟨n,z⟩, where n is m v the lowest counter for which no such S exists. Repeat the previous steps after updating b. Whilec = 0,theaboveprotocolimplementsfederatedvotingtoconfirmbisprepared. Oncec ≠0,theprotocol implements federated voting on commit c¨ for every c ≲ c¨ ≲ ℎ. For the CONFIRM phase, once a well-behaved node accepts commit c, the node never accepts, and hence never attempts to confirm, commit c¨ for any c¨ ≁ c. Once a commit is confirmed,thevalueofitsballotissafetoexternalizeassumingquorumintersection. ¨ All messages sent by a particular node are totally ordered by ⟨',b,p,p ,ℎ⟩, with ' the most significant and ℎ the least significant field. The values of these fields can be determined from messages, as described in Figure 17. All PREPARE messages precede all CONFIRM messages, which in turn precede the single EXTERNALIZE message for a given slot. The ordering makes it possible to ensure M contains only the latest ballot