Se considera instrucciones atómicas aquellas que está garantizado su correcto cumplimento independientemento de otras instrucciones posiblemente ejecutadas simultaneamente en el programa. A veces también nos referimos a instrucciones atómicas cuando el procesador es capaz de volver al estado producido justamente antes de haber empezado la ejecución de la instrucción en el caso de que se produzca una interrupción, es decir, el efecto de la instrucción es nulo.
Un algoritmo secuencial impone un orden total en el conjunto de las instrucciones que establece mientras un algoritmo concurrente solamente especifica un orden parcial.
Aunque eso no es totalmente cierto en el caso de microprocesadores modernos que son capaces de reordenar las instrucciones para conseguir un mejor rendimiento del procesador. Estas reordenaciones y ejecuciones especulativos suelen mantener la semántica de la secuencia de operaciones, sin embargo, incluso en orden del acceso a la memoria principal puede ser cambiada.
El orden establecido se puede visualizar con grafos: los nodos representan las instrucciones atómicas, las aristas indican si una instrucción debe seguir la otra.
Dicho orden se puede determinar con las condiciones de Bernstein. Sea L(Sk) el conjunto de variables que se leen durante la ejecución de las instrucciones en Sk. Sea E(Sk) el conjunto de variables que se escriben durante la ejecución de las instrucciones en Sk.
Entonces, se pueden ejecutar los dos conjuntos de instrucciones Si y
Sj concurrentemente, siempre cuando se cumpla:
L(Si) 
E(Sj) = E(Si) L(Sj) = E(Si) E(Sj) = 
.
Dado que en un programa concurrente varios procesos actuan simultaneamente sobre las instrucciones, no se puede establecer un orden total.
Eso implica que la ejecución del programa es indeterminística. Ejecutar el mismo programa varias veces, aún con los mismos datos de entrada, puede resultar en secuencias de instrucciones diferentes, incluso puede ocurrir que es imposible detectar en que orden se ejecutan las instrucciones en un caso real.