Many algorithms have been designed to solve distributed systems problems—for example, we will examine solutions for the consensus problem in the related discussion. In order to be useful, these algorithms need to tolerate the various faults of distributed systems that we discussed in this topic.
Algorithms must be written in a way that does not depend too heavily on the details of the hardware and software configuration on which they are run. This in turn requires that we somehow formalize the kinds of faults that we expect to happen in a system. We do this by defining a system model, which is an abstraction that describes an algorithm’s assumptions.
With regard to timing assumptions, three system models are in common use:
Synchronous model
The synchronous model assumes bounded network delay, bounded process pauses, and bounded clock error. This does not imply exactly synchronized clocks or zero network delay; it just means you know that network delay, pauses, and clock drift will never exceed a fixed upper bound. The synchronous model is not a realistic model of most practical systems because (as discussed in this topic) unbounded delays and pauses do occur.
Partially synchronous model
Partial synchrony means that a system behaves like a synchronous system most of the time, but it sometimes exceeds the bounds for network delay, process pauses, and clock drift. This is a realistic model of many systems. Most of the time, networks and processes are quite well behaved—otherwise, we would never be able to get anything done—but we have to reckon with the fact that any timing assumptions may be shattered occasionally. When this happens, network delay, pauses, and clock error may become arbitrarily large.
Asynchronous model
In this model, an algorithm is not allowed to make any timing assumptions—in fact, it does not even have a clock (so it cannot use timeouts). Some algorithms can be designed for the asynchronous model, but it is very restrictive.
Besides timing issues, we also have to consider node failures. Some common system models for nodes are as follows:
Crash-stop faults
In the crash-stop (or fail-stop) model, an algorithm may assume that a node can fail in only one way—namely, by crashing. The node may suddenly stop responding at any moment, and thereafter that node is gone forever—it never comes back.
Crash-recovery faults
In the crash-recovery model, we assume that nodes may crash at any moment, and perhaps start responding again after an unknown time. Nodes are assumed to have stable storage (i.e., nonvolatile disk storage) that is preserved across crashes, while the in-memory state is assumed to be lost.
Degraded performance and partial functionality
In addition to crashing and restarting, nodes may slow down. They may still be able to respond to health check requests, while being too slow to get any real work done. For example, a Gigabit network interface could suddenly drop to 1 Kb/s throughput because of a driver bug; a process that is under memory pressure may spend most of its time performing garbage collection; worn-out SSDs can have erratic performance; and hardware can be affected by high temperature, loose connectors, mechanical vibration, power supply problems, firmware bugs, and more. Such a situation is called a limping node, gray failure, or fail-slow, and it can be even more difficult to deal with than a cleanly failed node. A related problem occurs when a process stops doing some of the things it is supposed to do while other aspects continue working—for example, because a background thread is crashed or deadlocked.
Byzantine (arbitrary) faults
Nodes may do absolutely anything, including trying to trick and deceive other nodes, as described in the previous section.
For modeling real systems, the partially synchronous model with crash-recovery faults is generally the most useful. It allows for unbounded network delay, process pauses, and slow nodes. But how do distributed algorithms cope with that model?
Defining the correctness of an algorithm
To define what it means for an algorithm to be correct, we can describe its properties. For example, the output of a sorting algorithm has the property that for any two distinct elements of the output list, the element further to the left is smaller than the element further to the right. That is simply a formal way of defining what it means for a list to be sorted—an invariant of a sorted list.
Similarly, we can write down the properties we want of a distributed algorithm to define what it means to be correct. For example, if we are generating fencing tokens for a lock (see “Fencing off zombies and delayed requests”), we may require the algorithm to have the following properties:
Uniqueness
No two requests for a fencing token return the same value.
Monotonic sequence
If request x returned token tx, and request y returned token ty, and x completed before y began, then tx < ty.
Availability
A node that requests a fencing token and does not crash eventually receives a response.
An algorithm is correct in a system model if it always satisfies its properties in all situations that we assume may occur in that system model. However, if all nodes crash, or all network delays suddenly become infinitely long, then no algorithm will be able to get anything done. How can we still make useful guarantees even in a system model that allows complete failures?
Distinguishing between safety and liveness
To clarify the situation, it is worth distinguishing between two kinds of properties: safety and liveness. In the example just given, uniqueness and monotonic sequence are safety properties, but availability is a liveness property.
What distinguishes the two kinds of properties? A giveaway is that liveness properties often include the word “eventually” in their definition. (And yes, you guessed it—eventual consistency is a liveness property.)
Safety is often informally defined as nothing bad happens, and liveness as something good eventually happens. However, it’s best to not read too much into those informal definitions, because “good” and “bad” are value judgments that don’t apply well to algorithms. The actual definitions of safety and liveness are more precise:
-
If a safety property is violated, we can point to the particular point in time that it was broken (e.g., if the uniqueness property was violated, we can identify the particular operation in which a duplicate fencing token was returned). After a safety property has been violated, the violation cannot be undone—the damage is already done.
-
A liveness property works the other way around. It may not hold at a certain point in time (e.g., a node may have sent a request but not yet received a response), but there is always hope that it may be satisfied in the future (namely, by receiving a response).
An advantage of distinguishing between safety and liveness properties is that it helps us deal with difficult system models. For distributed algorithms, it is common to require that safety properties always hold, in all possible situations of a system model. Even if all nodes crash, or the entire network fails, the algorithm must nevertheless ensure that it does not return a wrong result (i.e., that the safety properties remain satisfied).
However, with liveness properties we are allowed to make caveats—for example, we could say that a request needs to receive a response only if a majority of nodes have not crashed, and only if the network eventually recovers from an outage. The definition of the partially synchronous model requires that eventually the system returns to a synchronous state—that is, any period of network interruption lasts only for a finite duration and is then repaired.
Mapping system models to the real world
Safety and liveness properties and system models are very useful for reasoning about the correctness of a distributed algorithm. However, when implementing an algorithm in practice, the messy facts of reality come back to bite you again, and it becomes clear that the system model is a simplified abstraction of reality.
For example, algorithms in the crash-recovery model generally assume that data in stable storage survives crashes. However, what happens if the data on disk is corrupted or wiped out by hardware error or misconfiguration? What happens if a server has a firmware bug and fails to recognize its hard drives on reboot even though the drives are correctly attached to the server?
Quorum algorithms (see “Using quorums for reading and writing”) rely on a node remembering the data that it claims to have stored. If a node may suffer from amnesia and forget previously stored data, that breaks the quorum condition and thus breaks the correctness of the algorithm. Perhaps a new system model is needed, in which we assume that stable storage mostly survives crashes but may sometimes be lost. But that model then becomes harder to reason about.
The theoretical description of an algorithm can declare that certain things are simply assumed not to happen—and in non-Byzantine systems, we do have to make assumptions about faults that can and cannot happen. However, a real implementation may still have to include code to handle the case of something happening that was assumed to be impossible, even if that handling boils down to printf("Sucks to be you") and exit(666)—that is, letting a human operator clean up the mess. (This is one difference between computer science and software engineering.)
That is not to say that theoretical, abstract system models are worthless—quite the opposite. They are incredibly helpful for distilling down the complexity of real systems to a manageable set of faults that we can reason about so that we can understand the problem and try to solve it systematically.