An introduction to lockless algorithms

Many people are giving you exact definitions of the word "total ordering" which is relevant to the article, obviously, but it is also worth pointing out that the word "total", when applied to some operation, be it mathematics or a computer program, means it is an operation that works and "makes sense" over every possible input you could feed it. This is an extremely common occurrence computer programmers encounter regularly, though it may not seem like it.

For example, many people define division as a function that takes two parameters, 'n' and 'd', and computes n / d. But most people would agree that d=0 is an invalid parameter your program will actually fault. It's nonsensical.[1] So division is not total, then: you can give it an input and it can fail. But multiplication is total: it doesn't matter what two integers you give it. You can always multiply them, and there is always a sensible result. Thus, being "total", or "totality", is a property of algorithms/functions/actions you can perform on some objects (those objects being the set of all possible parameters, commonly called "the input domain".)

There is another operator that you often use when programming, and it is called "is x less than y", or <. You use it to figure out how things are ordered. Is 1 less than 2? It turns out, this is very similar to the question "does a thing happen before another thing?" and it's a very important question. They are both a way of asking what order things occurred in, just for different kinds of "things". But, as an algorithm, ordering is not always total: sometimes you just can't tell if A happened before B, or if A is less than B, or not. It might not make sense for the objects in question.

I'll also say that partiality and totality, and especially partially ordered sets (sometimes called "posets"), are an extremely, extremely fundamental component of computer science and mathematics. They're very important, and very well worth understanding, even if it's only at a high level.

[1] It's only nonsensical to some people or computers. On some CPUs, such as RISC-V for example, division by zero is well defined, as n/0=0. This is fine, and not really problematic. At the end of the day, math is what human beings make of it. For rigorous mathematics, n/0=0 might be heresy. But for computers, for humans using them, it's maybe OK to let that slide.