There are many deterministic BFT protocols. PBFT is probably the most well-known. [1] The SCP paper points to several BFT protocols with message complexity of

There are many deterministic BFT protocols. PBFT is probably the most well-known. [1] The SCP paper points to several BFT protocols with message complexity of O(N polylog(N)), e.g. [2] [1] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, pages 173–186. USENIX Association, 1999. [2] Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. Load balanced scalable byzantine agreement through quorum building, with full information. In MarcosK. Aguilera, Haifeng Yu, Nitin H. Vaidya, Vikram Srinivasan, and RomitRoy Choudhury, editors, Distributed Computing and Networking, volume 6522 of Lecture Notes in Computer Science, pages 203–214. Springer Berlin Heidelberg, 2011.