Most practical synchronous Byzantine fault-tolerant (BFT) protocols, such as Sync HotStuff (S&P 2020), follow the paradigm of partially synchronous BFT and adopt a deterministic design. While these protocols achieve$\mathbf{O}(\mathbf{n})$time complexity, they exhibit impressive performance in failure-free scenarios. This paper challenges this conventional wisdom, showing that a randomized paradigm terminating in expected$O(1)$time may well outperform prior ones even in the failure-free scenarios. Our framework reduces synchronous BFT to a new primitive called multi-valued Byzantine agreement with strong external validity (MBA-SEV). Inspired by the external validity property of multi-valued validated Byzantine agreement (MVBA), the additional validity properties allow us to build a BFT protocol where replicas agree on the hashes of the blocks. Our instantiation of the paradigm, Sonic, achieves$O(n)$amortized message complexity per block proposal, expected$O(1)$time, and enables a fast path of only two communication step. Our evaluation results using up to 91 instances on Amazon EC2 show that the peak throughput of Sonic and P-Sonic (a pipelining variant of Sonic) is$2.24 x-14.52 x$and$3.08 x-24.25 x$that of Sync HotStuff, respectively.