Evolving Paxos for the Non-Malicious Arbitrary Model - Santos, Enrique S. dos; Barbieri, Rodrigo R.; Vieira, Gustavo M. D. (Anais do Workshop de Testes e Tolerância a Falhas (WTF); 2023: Anais do XXIV Workshop de Testes e Tolerância a FalhasDO - 10.5753/wtf.2023.720, 2023)
The non-malicious arbitrary fault model presents a compromise between the weak fault tolerance of the fail-stop fault model and the complexity of the Byzantine fault model. This model describes processes that are capable of using validation codes to detect and drop invalid messages. In this paper we propose a more robust non-malicious version of the distributed consensus algorithm Paxos that can withstand algorithm-level (distributed) faults, while ensuring the application will only see correct states. Our approach to extend the non-malicious model beyond local validations is to define global invariants that must be respected by the algorithm and track them as the algorithm executes. Experimental work shows our solution works for a representative subset of faults and that the performance cost is minimal compared to a local-only non-malicious implementation based on validation codes.