State Machine Replication. Producing a unique and everlasting sequence of decisions is at the cornerstone of the State machine approach [50] which aims at creating a sequence of commands. In this problem, the external clients are the processes that are issuing commands. The servers are the processes in charge of executing those commands according to the unique total order defined by the core. Each client participates to some consensus instances (but not all). The Propose primitive accepts a single parameter, namely the proposed value. If a Proposer provides a value vx then this proposed value will eventually appear in a future decision <c , vx> but the client ignores (and has no control on) the value of c when it submits vx. In this approach, data is replicated at n servers. This technique relies upon the client- server interaction: each process (client/server) has an estimate of who the current leader is. Clients issue operations that need to be performed in the same order at all correct servers. A client sends a request to the current leader that launches the Paxos consensus algorithm to agree upon the order of the requests. Once the consensus is completed, the leader sends the response back to the client. To implement the state machine approach, Xxxxxxx suggests to tag each command with the round number (also called ballot number) that is used in the protocol. Yet, this strat- egy may lead to have holes in the sequence and, consequently, nop commands may have to correspond to some sequence numbers. In [38] and [41], a single everlasting instance of the protocol manages both a round number (like in Paxos) and a consensus number that are initialized once.
State Machine Replication. In this subsection, we examine the inner workings of State Machine Replication and its relevance for recent advances in distributed systems. Using a central server is the simplest way to implement a client-server communication service. Yet the service can only be as fault-tolerant as the processor executing the server. This means that multiple servers (replicas) must be used for the service to continue to work. An approach for implementing a fault-tolerant service is State Machine Replication (SMR) [22]. It replicates servers and coordinates the client’s interactions among these replicas, with each replica sim- ulating a state machine. A state machine is composed of a group of variables and commands. While variables encode the service state at any instant, commands transform the machine’s state using deterministic programs that run atomically (regarding other commands). A client makes requests to execute these commands (e.g. read, write), providing input if necessary, and receiving output either directly or to a peripheral output device. Be that as it may, the system still needs to account for failures. The ones considered in the state machine model are either Byzantine – where the component exhibits arbitrary, inconsistent behavior – or fail-stop – where the other components can detect that a failure has occurred and then stop. A variant of the fail-stop is a crash failure, in which the components halt without the ability to detect a failure. In this context, a system component is said to be faulty when its behavior ceases to be consistent with its specification. Moreover, the system itself is said to be t fault-tolerant if it satisfies its specification under the requirement that no more than t components become faulty during a certain interval. To implement a t fault-tolerant state machine system, the state machine must be replicated with each replica running individually. Additionally, it is required that the state machine is deterministic: starting in the same initial state and executing the same requests in the same order, each state machine must produce the same output. Since each replica will obtain an individual output – and each replica can be faulty – a voter device is necessary to combine the outputs of the replicas so they can agree on the final output for the system, decided by a majority. Considering that the system is designed under a synchronous model, t + 1 replicas are enough for fail-stop failures (in case t fail, one still works) and...
