Degradable agreement in the presence of Byzantine faults

Consider a system consisting of a sender that wants to send a value to certain receivers. Byzantine agreement protocols have previously been proposed to achieve this in the presence of arbitrary failures. The imposed requirement typically is that the fault-free receivers must all agree on the same value. We propose an agreement protocol that achieves Lamport's Byzantine agreement up to a certain number of faults and a degraded form of agreement with a higher number of faults. The degraded form of agreement allows the fault-free receivers to agree on at most two different values one of which is necessarily the default value. The proposed approach is named `degradable agreement'. An algorithm for degradable agreement is presented along with bounds on the number of nodes and network connectivity necessary to achieve degradable agreement.