This paper presents an implementation of a replicated state machine in asynchronous distributed environments prone to node failures and network partitions. This implementation has two appealing properties: It allows minority partitions to continue providing service for idempotent requests, and it guarantees that progress will be made whenever a majority of replicas can communicate with each other.