Ya pasó antes

En informática , la relación de "ocurrido antes" (denotada como ) es una relación entre el resultado de dos eventos, de modo que si un evento debe ocurrir antes de otro evento, el resultado debe reflejar eso, incluso si esos eventos en realidad se ejecutan fuera de orden (generalmente para optimizar el flujo del programa). Esto implica ordenar eventos en función de la relación causal potencial de pares de eventos en un sistema concurrente, especialmente sistemas distribuidos asincrónicos . Fue formulada por Leslie Lamport . ^[1] ${\displaystyle \to \;}$

La relación "sucedió antes" se define formalmente como el orden parcial menos estricto de eventos tales que:

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

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

Si existen otras relaciones causales entre eventos en un sistema determinado, como entre la creación de un proceso y su primer evento, estas relaciones también se agregan a la definición. Por ejemplo, en algunos lenguajes de programación como Java, ^[3] C, C++ o Rust, existe una arista de ocurrencia previa 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 vacuamente, asimétrica ), es decir:

• ${\displaystyle \forall a,b,c}$, si y , entonces (transitividad). Esto significa que para tres eventos cualesquiera , si ocurrió antes de , y ocurrió antes de , entonces debe haber ocurrido antes de . ${\displaystyle a\to b\;}$ ${\displaystyle b\to c\;}$ ${\displaystyle a\to c\;}$ ${\displaystyle a,b,c}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle c}$
• ${\displaystyle \forall a,a\nrightarrow a}$(irreflexividad). Esto significa que ningún acontecimiento puede suceder antes de sí mismo.
• ${\displaystyle \forall a,b,}$si entonces (asimetría). Esto significa que para dos eventos cualesquiera , si ocurrió antes entonces no puede haber ocurrido antes . ${\displaystyle a\to b}$ ${\displaystyle b\nrightarrow a}$ ${\displaystyle a,b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$

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

Los procesos que componen un sistema distribuido no tienen conocimiento de la relación entre lo que sucedió antes, 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 tareas como la depuración u optimización de sistemas distribuidos.

Véase también

• Condición de carrera
• Modelo de memoria de Java
• Marcas de tiempo de Lamport
• Reloj lógico

Citas

1. Lamport, Leslie (1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido", Communications of the ACM , 21(7), 558-565.
2. "Sistemas distribuidos 3.ª edición (2017)". DISTRIBUTED-SYSTEMS.NET . Consultado el 20 de marzo de 2021 .
3. Goetz et al. 2006, págs. 339–342, §16.1.3 El modelo de memoria de Java en 500 palabras o menos.

Referencias

• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Concurrencia en Java en la práctica. Addison Wesley. ISBN 0-321-34960-1.