Sucedió antes

En ciencias de la computación , la relación de pasado anterior (denotada:${\displaystyle \to \;}$La relación causal entre dos eventos es tal que, si un evento ocurre antes que otro, el resultado debe reflejarlo, incluso si en realidad se ejecutan en un orden diferente (generalmente para optimizar el flujo del programa). Esto implica ordenar eventos basándose en la posible relación causal entre pares de eventos en un sistema concurrente, especialmente en sistemas distribuidos asíncronos . Fue formulada por Leslie Lamport . ^{[ 1 ]}

La relación de precedencia se define formalmente como el orden parcial menos estricto sobre eventos tales que:

• Si los eventos${\displaystyle a\;}$y${\displaystyle b\;}$ocurren en el mismo proceso,${\displaystyle a\to b\;}$si ocurre el evento${\displaystyle a\;}$precedió a la ocurrencia del evento${\displaystyle b\;}$.
• Si ocurre${\displaystyle a\;}$es el envío de un mensaje y evento${\displaystyle b\;}$es la recepción del mensaje enviado en el evento${\displaystyle a\;}$,${\displaystyle a\to b\;}$.

Si dos eventos ocurren en procesos aislados diferentes (que no intercambian mensajes directa o indirectamente a través de procesos de terceros), entonces se dice que los dos procesos son concurrentes, es decir, ninguno de los dos procesos es concurrente.${\displaystyle a\to b}$ni${\displaystyle b\to a}$es cierto. ^{[ 2 ]}

Si existen otras relaciones causales entre los eventos de un sistema determinado, como por ejemplo entre la creación de un proceso y su primer evento, estas relaciones también se añaden a la definición.

Por ejemplo, en algunos lenguajes de programación como Java, ^{[ 3 ]} C, C++ o Rust, existe un borde de precedencia si la memoria escrita por la instrucción A es visible para la instrucción B, es decir, si la instrucción A completa su escritura antes de que la instrucción B comience su lectura.

Como todos los órdenes parciales estrictos, la relación de "sucedió antes" es transitiva , irreflexiva (y, trivialmente, asimétrica ), es decir:

• ${\displaystyle \forall a,b,c}$, si${\displaystyle a\to b\;}$y${\displaystyle b\to c\;}$, entonces${\displaystyle a\to c\;}$(transitividad). Esto significa que para cualesquiera tres eventos${\displaystyle a,b,c}$, si${\displaystyle a}$sucedió antes${\displaystyle b}$, y${\displaystyle b}$sucedió antes${\displaystyle c}$, entonces${\displaystyle a}$debió haber sucedido antes${\displaystyle c}$.
• ${\displaystyle \forall a,a\nrightarrow a}$(irreflexividad). Esto significa que ningún evento puede ocurrir antes que sí mismo.
• ${\displaystyle \forall a,b,}$si${\displaystyle a\to b}$entonces${\displaystyle b\nrightarrow a}$(asimetría). Esto significa que para cualesquiera dos eventos${\displaystyle a,b}$, si${\displaystyle a}$sucedió antes${\displaystyle b}$entonces${\displaystyle b}$no puede haber sucedido antes${\displaystyle a}$.

Observemos que la propiedad de asimetría se deduce directamente de las propiedades anteriores: por contradicción, supongamos que${\displaystyle \forall a,b,}$tenemos${\displaystyle a\to b\;}$y${\displaystyle b\to a}$. Entonces, por transitividad, tenemos${\displaystyle a\to a,}$lo cual contradice la irreflexividad.

Los procesos que componen un sistema distribuido desconocen la relación de precedencia a menos que utilicen un reloj lógico , como un reloj de Lamport o un reloj vectorial . Esto permite diseñar algoritmos de exclusión mutua y realizar tareas como la depuración o la optimización de sistemas distribuidos.

En sistemas distribuidos, la relación de precedencia se puede rastrear con precisión en caso de fallos catastróficos mediante relojes vectoriales, sus variantes y otros mecanismos de seguimiento de causalidad. Sin embargo, en caso de fallos bizantinos , donde los procesos pueden comportarse de forma arbitraria o maliciosa, es fundamentalmente imposible detectar la relación de precedencia. ^{[ 4 ]} El razonamiento intuitivo para esto es que los procesos bizantinos pueden falsificar o manipular metadatos, lo que imposibilita determinar las verdaderas dependencias causales.

• condición de carrera
• modelo de memoria de Java
• Marca de tiempo de Lamport
• Reloj lógico

• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Java Concurrency in Practice . Addison Wesley. ISBN 0-321-34960-1.