  Service replication distributes an application over many processes for
tolerating faults, attacks, and misbehavior among a subset of the processes.
The established state-machine replication paradigm inherently requires the
application to be deterministic. This paper distinguishes three models for
dealing with non-determinism in replicated services, where some processes are
subject to faults and arbitrary behavior (so-called Byzantine faults): first, a
modular approach that does not require any changes to the potentially
non-deterministic application (and neither access to its internal data);
second, a master-slave approach, in which ties are broken by a leader and the
other processes validate the choices of the leader; and finally, a treatment of
applications that use cryptography and secret keys. Cryptographic operations
and secrets must be treated specially because they require strong randomness to
satisfy their goals.
  The paper also introduces two new protocols. The first uses the modular
approach for filtering out non-de\-ter\-min\-istic operations in an
application. It ensures that all correct processes produce the same outputs and
that their internal states do not diverge. The second protocol implements
cryptographically secure randomness generation with a verifiable random
function and is appropriate for certain security models. All protocols are
described in a generic way and do not assume a particular implementation of the
underlying consensus primitive.
