En ciencias de la computación , la sucedió, antes de relación (indicada:) es una relación entre el resultado de dos eventos, de modo que si un evento debe ocurrir antes que 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 basados en la relación causal potencial de pares de eventos en un sistema concurrente, especialmente sistemas distribuidos asincrónicos . Fue formulado por Leslie Lamport . [1]
La relación sucedido antes se define formalmente como el orden parcial menos estricto de eventos tales que:
- Si eventos y ocurren en el mismo proceso, si la ocurrencia del evento precedió a la ocurrencia del evento .
- Si evento es el envío de un mensaje y un evento es la recepción del mensaje enviado en caso de , .
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, es decir, ninguno de los dos. ni es verdad. [2]
Si existen otras relaciones causales entre eventos en un sistema dado, 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, C ++ o Rust, existe un borde de ocurre antes 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 sucedido antes es transitiva , irreflexiva y antisimétrica , es decir:
- , Si y , luego (transitividad). Esto significa que para tres eventos cualesquiera, Si sucedió antes , y sucedió antes , luego debe haber sucedido antes .
- (irreflexividad). Esto significa que ningún evento puede suceder antes que él mismo.
- dónde , Si luego (antisimetría). Esto significa que para dos eventos distintos, Si sucedió antes luego no puede haber sucedido antes .
Los procesos que componen un sistema distribuido no tienen conocimiento de la relación sucedido antes a menos que utilicen un reloj lógico , como un reloj de Lamport o un reloj vectorial . Esto permite diseñar algoritmos para la exclusión mutua y tareas como depurar u optimizar sistemas distribuidos.
Ver también
Referencias
- ^ Lamport, Leslie (1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" , Comunicaciones del ACM , 21 (7), 558-565.
- ^ "3ª edición de sistemas distribuidos (2017)" . DISTRIBUTED-SYSTEMS.NET . Consultado el 20 de marzo de 2021 .