Deterministic or probabilistic? - A survey on Byzantine fault tolerant state machine replication

Abraham, 2019, Asymptotically optimal validated asynchronous byzantine agreement, 337 Avarikioti, Z., Heimbach, L., Schmid, R., Vanbever, L., Wattenhofer, R., Wintermeyer, P., 2020. FNF-BFT: exploring performance limits of BFT protocols. arXiv preprint arXiv:2009.02235. Avizienis, 1985, The n-version approach to fault-tolerant software, IEEE Trans. Softw. Eng., 1491, 10.1109/TSE.1985.231893 Bachmann, 1894, Vol. 2 Baek, 2003, Simple and efficient threshold cryptosystem from the Gap Diffie-Hellman group, Vol. 3, 1491 Behl, 2015, Consensus-oriented parallelization: how to earn your first million, 173 Behl, J., Distler, T., Kapitza, R., 2017a. A highly parallelizable protocol for hybrid fault-tolerant service replication. Behl, 2017, Hybrids on steroids: SGX-based high performance BFT, 222 Ben-Or, 1994, Asynchronous secure computations with optimal resilience (extended abstract), 183 Bessani, 2014, State machine replication for the masses with BFT-SMART, 355 Bessani, 2008, The critical way of critical infrastructure protection, IEEE Secur. Privacy, 6, 44, 10.1109/MSP.2008.158 Boldyreva, 2003, Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-Group signature scheme, 31 Bracha, 1984, An asynchronous [(n - 1)/3]-resilient consensus protocol, 154 Bracha, 1985, Asynchronous consensus and broadcast protocols, J. ACM, 32, 824, 10.1145/4221.214134 Cachin, 2001, Secure and efficient asynchronous broadcast protocols, 524 Cachin, 2000, Random oracles in constantipole: Practical asynchronous byzantine agreement using cryptography (extended abstract), 123 Cachin, 2002, Secure intrusion-tolerant replication on the internet, 167 Cachin, 2005, Asynchronous verifiable information dispersal, 191 Canetti, 1993, Fast asynchronous byzantine agreement with optimal resilience, 42 Castro, 1999, Practical byzantine fault tolerance, 173 Castro, 2002, Practical byzantine fault tolerance and proactive recovery, ACM Trans. Comput. Syst., 20, 398, 10.1145/571637.571640 Chivers, 2015, An introduction to algorithms and the big O notation, 359 Corbett, 2012, Spanner: Google’s globally-distributed database, 251 Correia, 2004, How to tolerate half less one byzantine nodes in practical distributed systems, 174 Correia, 2007, Worm-it–a wormhole-based intrusion-tolerant group communication system, J. Syst. Softw., 80, 178, 10.1016/j.jss.2006.03.034 Correia, 2005, From consensus to atomic broadcast: time-free byzantine-resistant protocols without signatures, Comput. J., 49, 82, 10.1093/comjnl/bxh145 Correia, 2002, The design of a cots real-time distributed security kernel, 234 Cristian, 1995, Atomic broadcast: from simple message diffusion to byzantine agreement, 431 Danezis, 2022, Narwhal and tusk: a DAG-based mempool and efficient BFT consensus, 34 Desmedt, 1994, Threshold cryptography, Eur. Trans. Telecommun., 5, 449, 10.1002/ett.4460050407 Distler, 2015, Resource-efficient byzantine fault tolerance, IEEE Trans. Comput., 65, 2807, 10.1109/TC.2015.2495213 Duan, 2018, BEAT: asynchronous BFT made practical, 2028 Dwork, 1988, Consensus in the presence of partial synchrony, J. ACM, 35, 288, 10.1145/42282.42283 Fischer, 1983, The consensus problem in unreliable distributed systems (a brief survey), 127 Fischer, 1985, Impossibility of distributed consensus with one faulty process, J. ACM, 32, 374, 10.1145/3149.214121 Gao, 2022, Dumbo-NG: fast asynchronous BFT consensus with throughput-oblivious latency, 1187 Garay, 2020, SoK: a consensus taxonomy in the blockchain era, 284 Ga̧gol, 2019, Aleph: efficient atomic broadcast in asynchronous networks with byzantine nodes, 214 Golan Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M. K., Seredinschi, D.-A., Tamir, O., Tomescu, A., 2018. SBFT: a scalable and decentralized trust infrastructure. arXiv e-prints, arXiv–1804. Gunn, L. J., Liu, J., Vavala, B., Asokan, N., 2019. Making speculative BFT resilient with trusted monotonic counters. https://arxiv.org/abs/1905.10255. 10.48550/ARXIV.1905.10255 Guo, 2020, 803 Hao, 2018, Dynamic practical byzantine fault tolerance, 1 Hao, 2018, Dynamic practical byzantine fault tolerance, 1 Hunt, 2010, ZooKeeper: wait-free coordination for internet-scale systems, 11 Jin, 2022, An improved practical byzantine fault-tolerant consensus algorithm combined with aggregating signature, Vol. 12294, 1175 Kapitza, 2012, CheapBFT: resource-efficient byzantine fault tolerance, 295 Kihlstrom, 1998, The SecureRing protocols for securing group communication, Vol. 3, 317 Kotla, 2010, Zyzzyva: speculative byzantine fault tolerance, ACM Trans. Comput. Syst., 27, 10.1145/1658357.1658358 Kursawe, 2005, Optimistic asynchronous atomic broadcast, 204 Kwon, J., 2014. TenderMint: consensus without mining. Draft v. 0.6, fall 1 (11). Lamport, 1978, Time, clocks, and the ordering of events in a distributed system, Commun. ACM, 21, 558, 10.1145/359545.359563 Lamport, 2001, Paxos made simple, 51 Levin, D., Douceur, J. R., Lorch, J. R., Moscibroda, T., 2009. TrInc: small trusted hardware for large distributed systems Li, 2016, SAREK: optimistic parallel ordering in byzantine fault tolerance, 77 Liu, 2020, EPIC: efficient asynchronous BFT with adaptive security, 437 Liu, C., Duan, S., Zhang, H., 2021. MiB: asynchronous BFT with more replicas. arXiv preprint arXiv:2108.04488. Liu, 2016, XFT: practical fault tolerance beyond crashes, 485 Malkhi, 1997, Probabilistic quorum systems, 267 Maneas, 2021, On achieving interactive consistency in real-world distributed systems, J. Parallel Distrib. Comput., 147, 220, 10.1016/j.jpdc.2020.09.010 Martin, 2006, Fast byzantine consensus, IEEE Trans. Dependable Secure Comput., 3, 202, 10.1109/TDSC.2006.35 McKeen, 2013, Innovative instructions and software model for isolated execution, 1 Miller, 2016, The honey badger of BFT protocols, 31 Milosevic, 2013, Bounded delay in byzantine-tolerant state machine replication, 61 Moniz, 2011, RITAS: services for randomized intrusion tolerance, IEEE Trans. Dependable Secur. Comput., 8, 122, 10.1109/TDSC.2008.76 Mostefaoui, 2014, Signature-free asynchronous byzantine consensus with t<n/3 and O(n2) messages, 2 Özsu, 1999, Vol. 2 Plank, 2006, Optimizing cauchy reed-solomon codes for fault-tolerant network storage applications, 173 Rabin, 1983, Randomized byzantine generals, 403 Ramasamy, 2005, Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast, 88 Reiter, 1996, Distributing trust with the rampart toolkit, Commun. ACM, 39, 71, 10.1145/227210.227228 Reiter, 1994, The rampart toolkit for building high-integrity services, 99 Reiter, 1994, Secure agreement protocols: reliable and atomic group multicast in rampart, 68 Reiter, 1994, How to securely replicate services, ACM Trans. Program. Lang. Syst., 16, 986, 10.1145/177492.177745 Rivest, 1978, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 120, 10.1145/359340.359342 Schneider, 1990, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Comput. Surv., 22, 299, 10.1145/98163.98167 Shoup, 2000, Practical threshold signatures, 207 Shoup, 1998, Securing threshold cryptosystems against chosen ciphertext attack, 1 Sousa, 2012, From byzantine consensus to BFT state machine replication: a latency-optimal transformation, 37 Sousa, 2008, The forever service for fault/intrusion removal, 5:1 Toueg, 1984, Randomized byzantine agreements, 163 Tsudik, 1992, Message authentication with one-way hash functions, SIGCOMM Comput. Commun. Rev., 22, 29, 10.1145/141809.141812 Veronese, 2013, Efficient byzantine fault-tolerance, IEEE Trans. Comput., 62, 16, 10.1109/TC.2011.221 Wang, 2022, Byzantine fault tolerance for distributed ledgers revisited, Distrib. Ledger Technol. Res.Pract., 1, 1, 10.1145/3538227 Wood, 2009 Xiao, 2020, A survey of distributed consensus protocols for blockchain networks, IEEE Commun. Surv. Tutor., 22, 1432, 10.1109/COMST.2020.2969706 Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., Abraham, I., 2018. HotStuff: BFT consensus in the lens of blockchain. arXiv preprint arXiv:1803.05069. Yin, 2019, HotStuff: BFT consensus with linearity and responsiveness, 347 Zieliński, 2004, Paxos at War