This paper presents a replication algorithm that implements a highly-available, non-deterministic state machine. Our algorithm generalizes the Paxos parliament algorithm of Lamport to cope with non-deterministic computations, while preserving its nice resilience and efficiency properties. The algorithm is surprisingly simple, thanks to the use of two powerful underlying abstractions: weak consensus and weak leader election, together with a generic data structure: consensus bag. As a side-effect of our work, we discuss some similarities and differences between replicating deterministic and non-deterministic state machines. Indirectly, we revisit the traditional classification between state-machine replication and primary-backup.