Se considera instrucciones atómicas aquellas que están garantizados en cumplir correctamente independiente de otras instrucciones posiblemente ejecutado simultaneamente en el programa. A veces también se refiere a instrucciones atómicas cuando el procesador es capaz de re-instalar el estado justamente antes de haber empezado la ejecución de la instrucción cuando se haya producido una interrupción, es decir, el efecto de la instrucción es nulo.
Apuntamos la secuencia de instrucciones atómicas del programa como (a0, a1,..., an).
Un algoritmo secuencial impone un orden total en el conjunto de las instrucciones que establece mientras un algoritmo concurrente solamente especifica un orden parcial. Eso se puede visualizar con grafos: los nodos representan las instrucciones atómicas, las aristas indican si una instrucción debe seguir la otra.
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.