It should always be a prerequisite to have a proof before one begins an implementation. If one cannot construct such a proof then they have no business trying to design new distributed algorithms. Fortunately there are a few algorithms for proofs of replicated state machines available as previously noted.<p>Proofs will typically show the limitations of an algorithm, for instance the original paxos paper notes that the contained algorithm does not provide liveliness.<p>A system based on an algorithm with a proof has some chance of being correct, while a system based on an algorithm with no proof while technically it may have a non-zero probability of being correct that probability approaches zero.<p>Having worked on such systems and having talked to some people who have worked on debugging issues with paxos implementations at extreme scale while it is virtually impossible to to ensure that the system will be able to make forward progress it is possible to ensure that the state of the state machine remains correct.<p>When I look at an implementation of such an algorithm to evaluate it I pay very careful attention to the test suites. The more bizarre the tests they contain the more likely the implementation is to handle very weird network edge cases.