To meet the throughput demands of blockchain systems, protocols for State Machine Replication increasingly have many processors disseminate transaction blocks in parallel. Certified designs require availability certificates before blocks enter the ordering process, which is robust but adds latency. BlueBottle, the leading uncertified design under $n\geq 5f+1$ ($n$ processors, at most $f$ Byzantine), reduces latency in favourable conditions but can put fetching missing data on the critical path. Raptr, the state of the art under $n\geq 3f+1$, avoids fetching on the voting path, but transactions wait for a leader's proposal and two voting rounds, and the leader controls the proposed sequence. We prove that strengthening the resilience assumption alone cannot remove Raptr's second voting round. We present Multimmit, a protocol for $n\geq 5f+1$ that builds on Raptr's approach and finalises leader blocks after a single round of voting, improving latency by at least one message delay. Extension votes let voters endorse fresh transaction blocks omitted from the leader's proposal: once a leader block finalises, every fresh, well-circulated block of an honest chain enters the total ordering by the next finalised leader block, even if that block's leader is Byzantine. Producer chains are interleaved by a prescribed rule, not in a leader-chosen sequence. Payments are final within a single round trip, once the producer assembles $n-f$ acknowledgments into a transferable receipt. With fifty validators across thirteen regions, Multimmit's median latency to placement in the total ordering moves from 383 to 411 ms as the offered rate rises from 100k to 1M transactions per second. At 100k, it is essentially unchanged under 0.1% message loss and rises by a factor of 1.4 with nine validators crashed; these conditions slow BlueBottle and Raptr, respectively, by more than an order of magnitude.
The optimal fault-tolerance achievable by any protocol has been characterized in a wide range of settings. For example, for state machine replication (SMR) protocols operating in the partially synchronous setting, it is possible to simultaneously guarantee consistency against $α$-bounded adversaries (i.e., adversaries that control less than an $α$ fraction of the participants) and liveness against $β$-bounded adversaries if and only if $α+ 2β\leq 1$. This paper characterizes to what extent "better-than-optimal" fault-tolerance guarantees are possible for SMR protocols when the standard consistency requirement is relaxed to allow a bounded number $r$ of consistency violations. We prove that bounding rollback is impossible without additional timing assumptions and investigate protocols that tolerate and recover from consistency violations whenever message delays around the time of an attack are bounded by a parameter $Δ^*$ (which may be arbitrarily larger than the parameter $Δ$ that bounds post-GST message delays in the partially synchronous model). Here, a protocol's fault-tolerance can be a non-constant function of $r$, and we prove, for each $r$, matching upper and lower bounds on the optimal "recoverable fault-tolerance" achievable by any SMR protocol. For example, for protocols that guarantee liveness against 1/3-bounded adversaries in the partially synchronous setting, a 5/9-bounded adversary can always cause one consistency violation but not two, and a 2/3-bounded adversary can always cause two consistency violations but not three. Our positive results are achieved through a generic "recovery procedure" that can be grafted on to any accountable SMR protocol and restores consistency following a violation while rolling back only transactions that were finalized in the previous $2Δ^*$ timesteps.