State Machines

Implementing a fault-tolerant service using state machine replication requires us to be able to view our service in terms of state machines. Let's understand the characteristics of a state machine.

Core components of a state machine

A state machine consists of two main components: state variables and commands.

State variables

State variables of a state machine specify its state. These variables are any instances of data structures that provide details about the configuration of a server or information stored by them. They are like normal variables because they contain values.

Commands

Commands of a state machine are programs, functions, or code that alter the state of the state machine. These commands can perform the following operations:

1. Update values of state variables

2. Give an output

A vital characteristic of these commands is that they are deterministic. We can assume that the program or code that implements these commands is deterministic. Another important characteristic of these commands is that their execution is atomic with other commands. These assumptions are necessary so that we can compare the result or output of the state machines with each other.

Note: We will deliberately refrain from discussing how a command will be implemented or invoked to ensure that our model gives a general understanding. We will only talk about the steps involved in a command using pseudocode or plain English. We will describe state machines by only listing their state variables, commands, and the steps in those commands.

Complementary components

Now that we know what makes up a state machine, we'll discuss components of the state machine approach that will help us understand the interaction to and from a state machine.

Clients and requests

State machines have clients. A state machine's client can request to execute its commands. The client specifies the state machine, the command's name, and the information needed by the command in a request.

Output

A request produces an output when the command specified in the request produces an output. The output of a request (or command) can be to storage or memory hardware, a controlling device that controls hardware, or other clients. We can also refer to this output as the output of the state machine that processes the request.

In the illustration above, the state machine has two state variables:

• arr: An array that stores integers.

• L: Represents the length of arr.

It has three commands:

• arr(val): Places val at the smallest available index in arr that is not in use. It returns -1 if no index is available.

• update(val, ind): Updates the value at index ind in arr to val. It returns 1 when done.

• read(val): Returns the value stored at index ind of arr.

The diagram shows that its clients send requests in the order insert(3), update(5, 2), and read(2). The “Output(s)” box shows outputs that the state machine returns after processing these requests. We can see that the first output is -1, so the insert(3) command could not find an index to place 3. The next output is 1, which indicates that update(5, 2) is executed successfully. And lastly, the output 5 is for the read(2) command.

We will briefly discuss how state machine process ...