State Machine Replication

In an SMR protocol, there are two types of nodes: \emph{servers} and \emph{clients}.
The servers run the SMR protocol and the clients (can be servers) submit \emph{requests} to the state machine using the interface provided by the SMR protocol.
The state output by the servers in an SMR protocol must be consistent across all servers, i.e.,\ no two honest servers output different states at any point.
Here, consistency means that the clients should obtain views as though a single state machine executed all requests.
We realize the state machine using a distributed linearizable append-only log consisting of a block of client requests.
As long as the honest servers agree on the log, they will derive a deterministic and thus, consistent state.

\begin{definition}[SMR --- State Machine Replication~\cite{schneiderImplementingFaulttolerantServices1990}]%
\label{def:smr}
  A State Machine replication protocol generates a linearizable log of client requests akin to a single non-faulty server among the servers with the following guarantees:
  \begin{asparaenum}[(1)]
    \item \textbf{Safety.} Honest servers do not output different requests at the same log position.
    \item \textbf{Liveness.} Each client request is eventually output by all honest servers.
  \end{asparaenum}
\end{definition}