Amending my own parent comment, since it won't let me edit: I was wrong about this being standard in Paxos/Raft etc. They actually require "f failures with 2f+1 replicas" (meaning that at a minimum a strict majority of replicas need to be available). I blame my morning brain.