A measure of complexity (lower is better) for distributed consensus mechanisms in partially synchronous system model.

Definition: The sum, over all replicas , of the number of authenticators received by replica in the protocol to reach a consensus decision after GST.

An authenticator is either a partial signature or a signature.

Figure 2: Our Network Protocol (from The Saddest Moment)