On the Validity of Consensus

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement, preventing them from deciding different values, and (3) validity, precluding "unreasonable" decisions. But, what is a reasonable decision? Strong validity, a classical property, stipulates that, if all correct processes propose the same value, only that value can be decided. Weak validity, another established property, stipulates that, if all processes are correct and they propose the same value, that value must be decided. The space of possible validity properties is vast. Yet, their impact on consensus algorithms remains unclear.|This paper addresses the question of which validity properties allow Byzantine consensus to be solvable in a general partially synchronous model, and at what cost. First, we determine the necessary and sufficient conditions for a validity property to make the consensus problem solvable; we say that such validity properties are solvable. Notably, we prove that, if n