		Search-engine friendly clone of the ACL2 documentation.

Committees

Committee-quorum

Quorum of validators in a committee.

Signature
(committee-quorum commtt) → quorum
Arguments: commtt — Guard (committeep commtt).
Returns: quorum — Type (posp quorum).

As in the BFT literature, the quorum number in AleoBFT is n - f, where n and f are the numbers explained in max-faulty-for-total. As n and f are functions of the committee, the quorum number is a function of the committee too.

Some recent BFT literature uses 2f + 1 as the quorum number, which is correct only if n = 3f + 1, but not if n = 3f + 2 and n = 3f + 3, which are the other two possibilities, as discussed in max-faulty-for-total. Unfortunately that literature uses 2f + 1 without explicating the n = 3f + 1 assumption. There is indeed no reason for making this assumption, which is unnecessarily restrictive, given that the more general quorum n - f works for any value of n.

Definitions and Theorems

Function: committee-quorum

(defun committee-quorum (commtt)
  (declare (xargs :guard (committeep commtt)))
  (let ((__function__ 'committee-quorum))
    (declare (ignorable __function__))
    (- (committee-total commtt)
       (committee-max-faulty commtt))))

Theorem: posp-of-committee-quorum

(defthm posp-of-committee-quorum
  (b* ((quorum (committee-quorum commtt)))
    (posp quorum))
  :rule-classes (:rewrite :type-prescription))

Theorem: committee-quorum-of-committee-fix-commtt

(defthm committee-quorum-of-committee-fix-commtt
  (equal (committee-quorum (committee-fix commtt))
         (committee-quorum commtt)))

Theorem: committee-quorum-committee-equiv-congruence-on-commtt

(defthm committee-quorum-committee-equiv-congruence-on-commtt
  (implies (committee-equiv commtt commtt-equiv)
           (equal (committee-quorum commtt)
                  (committee-quorum commtt-equiv)))
  :rule-classes :congruence)