An introduction to lockless algorithms

"All accesses to the data structure form a total ordering" means that you can always say which access came first and which came second. This is what you'd expect from a mutex, because:

1) you can always say which critical section came first and which came second (lock waits for the other critical section to complete, if there's one), and

2) accesses within a critical section come from a single thread, and there is always a total order (defined in the article) within a thread.