System Models

We cannot reasonably talk about an algorithm or protocol without talking about the assumptions we are making about the underlying system. This set of assumptions is known as the system model.

A system model is a set of assumptions governing the behavior and interactions of a system’s components.

You can think of a system model as a board game: The game sets the stage and sets the rules while the players have to devise a strategy to achieve the objective of the game within the constraints of the rules. Even a slight change to the rules may render the players’ strategy completely ineffective. Your carefully devised strategy, executed over many rounds, may unravel in that instant.

For example, the FLP Impossibility states that consensus is trivial to achieve under a synchronous system model but impossible under an asynchronous system where even one component may fail.

System Model Super Powers

System models have a clever use. We can define the correctness of a system based on system models. The idea is straight forward: A system is correct, if the behavior under ideal execution semantics (ideal system model) is equivalent to the behavior under real execution semantics (real system model).

Failure Transparent Processes

Let’s look at an example, failure-transparent processes. The execution of a process is failure-transparent if a failure-free execution is equivalent to a failed execution that was subsequently recovered. In other words, an execution under a system model that allows failure is correct if there exists an equivalent execution under a system model that does not allow failure.

The real execution needs equivalence to an ideal execution.

References

I first encountered correctness via system models in [1] and finally understood correctness via system models in [2]

1. Fault Tolerance via Idempotence, G. Ramalingam and Kapil Vaswani
2. Durable functions: semantics for stateful serverless, S. Burckhardt et al