# 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.

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 tokens” on page 303), 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 *t _{x},* and request

*y*returned token

*t*and

_{y},*x*completed before

*y*began, then

*t*<

_{x}*t*

_{y}.*Availability*

A node that requests a fencing token and does not crash eventually receives a response.

An algorithm is correct in some system model if it always satisfies its properties in all situations that we assume may occur in that system model. But how does this make sense? If all nodes crash, or all network delays suddenly become infinitely long, then no algorithm will be able to get anything done.