Un reloj vectorial es una estructura de datos que se utiliza para determinar el orden parcial de eventos en un sistema distribuido y detectar violaciones de causalidad . Al igual que en las marcas de tiempo de Lamport , los mensajes entre procesos contienen el estado del reloj lógico del proceso de envío . Un reloj vectorial de un sistema de N procesos es una matriz / vector de N relojes lógicos, un reloj por proceso; En cada proceso se guarda una copia local de los "valores posibles más grandes" de la matriz de reloj global.
Denotar como el reloj vectorial mantenido por el proceso i, las actualizaciones del reloj proceden de la siguiente manera: [1]
- Inicialmente, todos los relojes son cero.
- Cada vez que un proceso experimenta un evento interno, incrementa su propio reloj lógico en el vector en uno. Por ejemplo, ante un evento en el proceso i, actualiza.
- Cada vez que un proceso envía un mensaje, incrementa su propio reloj lógico en el vector en uno (como en la viñeta anterior, pero no dos veces para el mismo evento) y luego el mensaje lleva una copia de su propio vector.
- Cada vez que un proceso recibe un mensaje, incrementa su propio reloj lógico en el vector en uno y actualiza cada elemento en su vector tomando el máximo del valor en su propio reloj vectorial y el valor en el vector en el mensaje recibido (por cada elemento). Por ejemplo, si el proceso Pj recibe un mensaje m de Pi, se actualiza configurando.
Historia
Sin usar el nombre específico "reloj vectorial", el concepto de reloj vectorial se mencionó por primera vez [2] en un artículo de 1986 de Rivka Ladin y Barbara Liskov, donde usan el término "marca de tiempo de varias partes". [3] Para citar la página 31 del artículo de Liskov / Ladin:
Resolvemos este problema mediante el uso de marcas de tiempo de varias partes , donde hay una parte para cada réplica. Por lo tanto, si hay n réplicas, una marca de tiempo t es
t =
,> donde cada parte es un número entero positivo. Dado que normalmente habrá una pequeña cantidad de réplicas (p. Ej., De 3 a 7), es práctico utilizar dicha marca de tiempo.
El término "reloj vectorial" fue utilizado por primera vez de forma independiente por Colin Fidge y Friedemann Mattern en 1988. [4] [5]
Propiedad de pedido parcial
Los relojes vectoriales permiten el ordenamiento causal parcial de los eventos. Definiendo lo siguiente:
- denota el vector de reloj de evento , y denota el componente de ese reloj para el proceso .
- En Inglés: es menos que , si y solo si es menor o igual que para todos los índices de proceso , y al menos una de esas relaciones es estrictamente más pequeña (es decir, ).
- denota ese evento sucedió antes del evento . Se define como: si, luego
Propiedades:
- Antisimetría : si, entonces ¬
- Transitividad : si y , luego ; o si y , luego
Relación con otros pedidos:
Otros mecanismos
- En 1999, Torres-Rojas y Ahamad desarrollaron Plausible Clocks , [6] un mecanismo que ocupa menos espacio que los relojes vectoriales pero que, en algunos casos, ordenará totalmente los eventos que son causalmente concurrentes.
- En 2005, Agargwal y Garg crearon Chain Clocks , [7] un sistema que rastrea las dependencias usando vectores con un tamaño menor que el número de procesos y que se adapta automáticamente a sistemas con un número dinámico de procesos.
- En 2008, Almeida et al. introdujo Interval Tree Clocks . [8] [9] [10] Este mecanismo generaliza los relojes vectoriales y permite la operación en entornos dinámicos cuando las identidades y el número de procesos en el cálculo no se conocen de antemano.
- En 2019, Lum Ramabaja desarrolló Bloom Clocks , [11] una estructura de datos probabilística cuya complejidad espacial no depende de la cantidad de nodos en un sistema. Si dos relojes no son comparables, el reloj de floración siempre puede deducirlo, es decir, no son posibles falsos negativos. Si dos relojes son comparables, el reloj de floración puede calcular la confianza de esa declaración, es decir, puede calcular la tasa de falsos positivos entre pares de relojes comparables.
Ver también
Referencias
- ^ "3ª edición de sistemas distribuidos (2017)" . DISTRIBUTED-SYSTEMS.NET . Consultado el 21 de marzo de 2021 .
- ^ La referencia a este artículo fue descubierta por la profesora Lindsey Kuper y descrita en la conferencia 23 de su serie de conferencias en video de YouTube sobre sistemas distribuidos.
- ^ Barbara Liskov, Rivka Ladin (1986). "Servicios distribuidos de alta disponibilidad y recolección de basura distribuida tolerante a fallas" . ACM. págs. 29–39 . Consultado el 22 de septiembre de 2020 . Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Colin J. Fidge (febrero de 1988). "Marcas de tiempo en sistemas de transmisión de mensajes que conservan el orden parcial" (PDF) . En K. Raymond (ed.). Proc. de la XI Conferencia Australiana de Ciencias de la Computación (ACSC'88) . págs. 56–66 . Consultado el 13 de febrero de 2009 .
- ^ Mattern, F. (octubre de 1988), "Tiempo virtual y estados globales de sistemas distribuidos", en Cosnard, M. (ed.), Proc. Taller sobre algoritmos paralelos y distribuidos , Chateau de Bonas, Francia: Elsevier, págs. 215–226
- ^ Francisco Torres-Rojas; Mustaque Ahamad (1999), "Relojes plausibles: relojes lógicos de tamaño constante para sistemas distribuidos" , Computación distribuida , 12 (4): 179-195, doi : 10.1007 / s004460050065
- ^ Agarwal, Anurag; Garg, Vijay K. (17 de julio de 2005). "Seguimiento eficiente de dependencias para eventos relevantes en sistemas de memoria compartida" (PDF) . Actas del vigésimo cuarto simposio anual de ACM sobre principios de computación distribuida . Asociación de Maquinaria de Computación: 19-28. doi : 10.1145 / 1073814.1073818 . Consultado el 21 de abril de 2021 .
- ^ Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Interval Tree Clocks: A Logical Clock for Dynamic Systems", en Baker, Theodore P .; Bui, Alain; Tixeuil, Sébastien (eds.), Principios de sistemas distribuidos (PDF) , Lecture Notes in Computer Science, 5401 , Springer-Verlag, Lecture Notes in Computer Science, págs. 259–274, Bibcode : 2008LNCS.5401 ..... B , doi : 10.1007 / 978-3-540-92221-6 , ISBN 978-3-540-92220-9
- ^ Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Relojes de árbol de intervalos: un reloj lógico para sistemas dinámicos", Relojes de árbol de intervalos: un reloj lógico para sistemas dinámicos , Lecture Notes in Computer Science, 5401 , p. 259, doi : 10.1007 / 978-3-540-92221-6_18 , hdl : 1822/37748 , ISBN 978-3-540-92220-9
- ^ Zhang, Yi (2014), "Preliminares de antecedentes: Resultados del reloj del árbol de intervalos", Preliminares de antecedentes: Resultados del reloj del árbol de intervalos (PDF)
- ^ Lum Ramabaja (2019), The Bloom Clock , arXiv : 1905.13064 , Bibcode : 2019arXiv190513064R
enlaces externos
- Por qué los relojes lógicos son fáciles (compara historias causales, relojes vectoriales y vectores de versión)
- Explicación de los relojes vectoriales
- Implementación de reloj vectorial basado en marcas de tiempo en Erlang
- Implementación de reloj vectorial en Objective-C
- Implementación de reloj vectorial en Erlang
- Por qué los relojes vectoriales son difíciles
- Por qué Cassandra no necesita relojes vectoriales