TheStellar Consensus Protocol 13 3/4 Slice is 3 nodes, including self v v v v 1 2 3 4 vote a vote a vote a vote ā accept accept accept Fig. 9. v voted for ā, which contradicts ratified statement a. 4 tier nodes v ,v ,v crash, the leaf tier will be blocked while the top tier and node v 6 7 8 5 will continue to enjoy liveness. An FBA protocol can guarantee liveness to a node v only if Q(v) contains at least onequorumslicecomprisingonlycorrectnodes.AsetB offailednodescanviolatethis property if B contains at least one member of each of v’s slices. We term such a set B v-blocking, because it has the power to block progress by v. Definition (v-blocking). Let v ∈ V be a node in FBAS ⟨V,Q⟩. A set B ⊆ V is v-blocking iff it overlaps every one of v’s slices—i.e., ∀q ∈ Q(v),q ∩ B ≠ ç. THEOREM7. Let B ⊆ V be a set of nodes in FBAS ⟨V,Q⟩. ⟨V,Q⟩ enjoys quorum availability despite B iff B is not v-blocking for any v ∈ V ⧵ B. PROOF. “∀v ∈ V⧵B,B is not v-blocking” is equivalent to “∀v ∈ V⧵B,∃q ∈ Q(v) such that q ⊆ V ⧵ B.” By the definition of quorum, the latter holds iff V ⧵ B is a quorum or B=V,theexactdefinitionofquorumavailability despite B. Asacorollary, the DSet of befouled nodes is not v-blocking for any intact v. 5.3. Accepting statements Whenanintact node v learns that it has ratified a statement, Theorem 6 tells v that other intact nodes will not ratify contradictory statements. This condition is sufficient for v to accept a, but we cannot make it necessary. Ratifying a statement requires vot- ingforit,andsomenodesmayhavevotedforcontradictorystatements.InFigure9,for example, v votes for ā before learning that the other three nodes ratified the contra- 4 dictory statement a. Though v4 cannot now vote for a, we would still like it to accept a to be consistent with the other nodes. Akeyinsightisthatifanodevisintact,thennov-blockingsetB canconsistentirely of befouled nodes. Now suppose B is a v-blocking set and every member of B claims to accept statement a. If v is intact, at least one member of B must be, too. The intact member will not lie about accepting a; hence, a is true and v can accept it. Of course, if v is befouled, then a might not be true. But a befouled node can accept anything and vacuously not affect the correctness of intact nodes. Definition (accept). An FBAS node v accepts a statement a iff it has never accepted astatement contradicting a and it determines that either (1) There exists a quorum U such that v ∈ U and each member of U either voted for a or claims to accept a, or (2) Each member of a v-blocking set claims to accept a. Though a well-behaved node cannot vote for contradictory statements, condition 2 above allows a node to vote for one statement and later accept a contradictory one.