Poster: Byzantine Fault Tolerant State Machine Replication for Non-deterministic Applications 1st Pedro Camponˆes Department of Informatics NOVA University Lisbon Lisbon, Portugal p.campones@campus.fct.unl.pt 2nd Diogo Tavares Department of Informatics NOVA University Lisbon Lisbon, Portugal dc.tavares@campus.fct.unl.pt 3rd Jo˜ao Magalh˜aes Department of Informatics NOVA University Lisbon Lisbon, Portugal jmag@fct.unl.pt 4th Henrique Domingos Department of Informatics NOVA University Lisbon Lisbon, Portugal hj@fct.unl.pt Abstract—Byzantine Fault Tolerant State Machine Replication (BFT-SMR) is a widely used approach to provide availability and fault tolerance to applications by enabling the system to continue its correct execution even when some nodes present arbitrary faults. This is done by replicating for all nodes the execution and response to client requests. When the client receives enough identical responses, that response is delivered. In BFT- SMR all correct processes must produce equal responses to the client requests. This requisite hinders the use of Large Language Models (LLMs) given that these models inherently produce non- deterministic outputs. We introduce Model Answer Replication (MARS), an algorithm that allows the use of SMR in non- deterministic applications, particularly when employing LLMs. MARS’ key innovation is comparing responses to client requests by measuring their semantic similarity rather than bit by bit equality and allowing client side code to remain unaltered from what is found in SMR algorithms for deterministic applications. Index Terms—State Machine Replication, Byzantine Fault Tol- erance, Large Language Models, Non-deterministic Algorithms I. INTRODUCTION Instruction-tuned Large Language Models (LLMs) are deep- learning models designed to generate natural language textual responses to comply with user requests. Their success has enabled their integration into diverse applications, showcasing their utility across multiple domains [1], including critical applications such as medical diagnostics [2]. In critical applications, the safety and availability of the sys- tem is crucial. One common method to achieve this is through the Byzantine Fault Tolerant [3] State Machine Replication [4] (BFT-SMR) abstraction, where the components of the system are replicated. When a client issues a request, all nodes will execute it and send their response to the client, ensuring the system can execute correctly even when some nodes fail. With BFT-SMR, when a client makes a request, they receive multiple responses. If enough responses match, the system considers the request successful. This method clashes with LLMs, as their responses vary due to the non-determinism commonly introduced during language decoding. Existing solutions to abstract non-determinism in applications and allow This work was supported by the FCT/MCTES grants PRT/BD/152803/2021 and PRT/BD/154428/2022, as well as by NOVA LINCS UIDB/04516/2020 and UIDP/04516/2020 with the financial support of FCT.IP their use in the SMR approach [5], [6] fail to extend to the challenges posed by LLMs. We introduce Model Answer Replication (MARS), an algo- rithm designed to make LLMs compatible with SMR. To the best of our knowledge, this work represents the first attempt to address this issue. A key innovation of MARS is to compare server responses based on their semantic/conceptual similarity rather than by exact match. Furthermore, MARS and BFT- SMR protocols for deterministic operations differ in that in the latter the response the client delivers is the output of correct nodes, while in MARS, the response delivered can result from a byzantine node, as long as it is be deemed innocuous by correct nodes. This abstract outlines our ongoing work. We will: • Using fundamental concepts in BFT-SMR and unsuper- vised learning as basis (§ II) and under a realistic system model (§ III), we will specify (§ IV) and implement the MARS algorithm. • Validate and eval