Reloj vectorial

Algoritmo para la ordenación parcial de eventos y detección de causalidad en sistemas distribuidos

Un reloj vectorial es una estructura de datos que se utiliza para determinar el orden parcial de los 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 que lo envía . 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 conserva una copia local de la matriz de relojes global con los "valores más grandes posibles".

Denotado como el reloj vectorial mantenido por el proceso , las actualizaciones del reloj proceden de la siguiente manera: ^[1] ${\displaystyle VC_{i}}$ ${\displaystyle i}$

Ejemplo de un sistema de relojes vectoriales. Los eventos en la región azul son las causas que conducen al evento B4, mientras que los de la región roja son los efectos del evento B4.

• Inicialmente todos los relojes están en cero.
• Cada vez que un proceso experimenta un evento interno, incrementa su propio reloj lógico en el vector en uno. Por ejemplo, cuando se produce un evento en el proceso , actualiza . ${\displaystyle i}$ ${\displaystyle VC_{i}[i]\leftarrow VC_{i}[i]+1}$
• Cada vez que un proceso envía un mensaje, incrementa su propio reloj lógico en el vector en uno (como en el punto anterior, pero no dos veces para el mismo evento), luego empareja el mensaje con una copia de su propio vector y finalmente envía el par.
• Cada vez que un proceso recibe un par de reloj de mensaje-vector, 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 de vector y el valor en el vector en el par recibido (para cada elemento). Por ejemplo, si el proceso recibe un mensaje de , primero incrementa su propio reloj lógico en el vector en uno y luego actualiza todo su vector estableciendo . ${\displaystyle P_{i}}$ ${\displaystyle (m,VC_{j})}$ ${\displaystyle P_{j}}$ ${\displaystyle VC_{i}[i]\leftarrow VC_{i}[i]+1}$ ${\displaystyle VC_{i}[k]\leftarrow \max(VC_{i}[k],VC_{j}[k]),\forall k}$

Historia

Lamport originó la idea de los relojes lógicos de Lamport en 1978. ^[2] Sin embargo, los relojes lógicos en ese artículo eran escalares, no vectores. La generalización al tiempo vectorial fue desarrollada varias veces, aparentemente de forma independiente, por diferentes autores a principios de la década de 1980. ^[3] Al menos 6 artículos contienen el concepto. ^[4] Los artículos citados canónicamente en referencia a los relojes vectoriales son los trabajos de Colin Fidge y Friedemann Mattern de 1988, ^{[5] [6]} ya que establecieron (de forma independiente) el nombre de "reloj vectorial" y las propiedades matemáticas de los relojes vectoriales. ^[3]

Propiedad de ordenación parcial

Los relojes vectoriales permiten la ordenación causal parcial de los eventos. Definiendo lo siguiente:

• ${\displaystyle VC(x)}$denota el reloj vectorial del evento , y denota el componente de ese reloj para el proceso . ${\displaystyle x}$ ${\displaystyle VC(x)_{z}}$ ${\displaystyle z}$
• ${\displaystyle VC(x)<VC(y)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}<VC(y)_{z'}]}$
  • En inglés: es menor 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 menor (es decir, ). ${\displaystyle VC(x)}$ ${\displaystyle VC(y)}$ ${\displaystyle VC(x)_{z}}$ ${\displaystyle VC(y)_{z}}$ ${\displaystyle z}$ ${\displaystyle VC(x)_{z'}<VC(y)_{z'}}$
• ${\displaystyle x\to y\;}$denota que el evento ocurrió antes del evento . Se define como: si , entonces ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\to y\;}$ ${\displaystyle VC(x)<VC(y)}$

Propiedades:

• Antisimetría : si , entonces ¬ ${\displaystyle VC(a)<VC(b)}$ ${\displaystyle (VC(b)<VC(a))}$
• Transitividad : si y , entonces ; o, si y , entonces ${\displaystyle VC(a)<VC(b)}$ ${\displaystyle VC(b)<VC(c)}$ ${\displaystyle VC(a)<VC(c)}$ ${\displaystyle a\to b\;}$ ${\displaystyle b\to c\;}$ ${\displaystyle a\to c\;}$

Relación con otras órdenes:

• Sea el tiempo real en el que se produce el evento. Si , entonces ${\displaystyle RT(x)}$ ${\displaystyle x}$ ${\displaystyle VC(a)<VC(b)}$ ${\displaystyle RT(a)<RT(b)}$
• Sea la marca de tiempo de Lamport del evento . Si , entonces ${\displaystyle C(x)}$ ${\displaystyle x}$ ${\displaystyle VC(a)<VC(b)}$ ${\displaystyle C(a)<C(b)}$

Otros mecanismos

• En 1999, Torres-Rojas y Ahamad desarrollaron Plausible Clocks , ^[7] un mecanismo que ocupa menos espacio que los relojes vectoriales pero que, en algunos casos, ordenará totalmente eventos que son causalmente concurrentes.

• En 2005, Agarwal y Garg crearon Chain Clocks , ^[8] un sistema que rastrea dependencias utilizando 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. introdujeron los relojes de árbol de intervalos . ^{[9] [10] [11]} 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 propuso Bloom Clocks , una estructura de datos probabilística basada en filtros Bloom . ^{[12] [13] [14]} En comparación con un reloj vectorial, el espacio utilizado por nodo es fijo y no depende de la cantidad de nodos en un sistema. La comparación de dos relojes produce un verdadero negativo (los relojes no son comparables) o una sugerencia de que un reloj precede al otro, con la posibilidad de un falso positivo donde los dos relojes no están relacionados. La tasa de falsos positivos disminuye a medida que se permite más almacenamiento.

Véase también

• Marcas de tiempo de Lamport
• Relojes matriciales
• Versión vectorial

Referencias

1. "Sistemas distribuidos 3.ª edición (2017)". DISTRIBUTED-SYSTEMS.NET . Consultado el 21 de marzo de 2021 .
2. Lamport, L. (1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" (PDF) . Comunicaciones de la ACM . 21 (7): 558–565. doi :10.1145/359545.359563. S2CID  215822405.
3. Schwarz, Reinhard; Mattern, Friedemann (marzo de 1994). "Detección de relaciones causales en cálculos distribuidos: En busca del santo grial". Computación distribuida . 7 (3): 149–174. doi :10.1007/BF02277859. S2CID  3065996.
4. Kuper, Lindsey (8 de abril de 2023). "¿Quién inventó los relojes vectoriales?". descomposición ∘ al .Los artículos son (en orden cronológico):
   • Fischer, Michael J.; Michael, Alan (1982). "Sacrificar la serialización para lograr una alta disponibilidad de datos en una red no confiable". Actas del 1er simposio ACM SIGACT-SIGMOD sobre Principios de sistemas de bases de datos - PODS '82 . p. 70. doi :10.1145/588111.588124. ISBN 0897910702.S2CID8774876  .​
   • Parker, DS; Popek, GJ; Rudisin, G.; Stoughton, A.; Walker, BJ; Walton, E.; Chow, JM; Edwards, D.; Kiser, S.; Kline, C. (mayo de 1983). "Detección de inconsistencia mutua en sistemas distribuidos". IEEE Transactions on Software Engineering . SE-9 (3): 240–247. doi :10.1109/TSE.1983.236733. S2CID  2483222.
   • Wuu, Gene TJ; Bernstein, Arthur J. (1984). "Soluciones eficientes para los problemas de registro y diccionario replicados". Actas del tercer simposio anual de la ACM sobre Principios de computación distribuida - PODC '84 . págs. 233–242. doi :10.1145/800222.806750. ISBN 0897911431. Número de identificación del sujeto  2384672.
   • Strom, Rob; Yemini, Shaula (agosto de 1985). "Recuperación optimista en sistemas distribuidos". ACM Transactions on Computer Systems . 3 (3): 204–226. doi : 10.1145/3959.3962 . S2CID  1941122.
   • Schmuck, Frank B. (noviembre de 1985). Relojes de software y orden de eventos en un sistema distribuido (inédito).
   • Liskov, Barbara; Ladin, Rivka (1986). "Servicios distribuidos de alta disponibilidad y recolección de basura distribuida con tolerancia a fallos". Actas del quinto simposio anual de la ACM sobre Principios de computación distribuida - PODC '86 . págs. 29–39. doi :10.1145/10590.10593. ISBN 0897911989.S2CID16148617  .​
   • Raynal, Michel (febrero de 1987). "Un algoritmo distribuido para evitar la deriva mutua entre n relojes lógicos". Information Processing Letters . 24 (3): 199–202. doi :10.1016/0020-0190(87)90186-4.
5. Fidge, Colin J. (febrero de 1988). "Marcas de tiempo en sistemas de paso de mensajes que preservan el ordenamiento parcial" (PDF) . En K. Raymond (ed.). Actas de la 11.ª Conferencia Australiana de Ciencias de la Computación (ACSC'88) . Vol. 10. págs. 56–66 . Consultado el 13 de febrero de 2009 .
6. Mattern, Friedemann (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. pp. 215–226.
7. Francisco Torres-Rojas; Mustaque Ahamad (1999), "Relojes plausibles: relojes lógicos de tamaño constante para sistemas distribuidos", Distributed Computing , 12 (4): 179–195, doi :10.1007/s004460050065, S2CID  2936350
8. 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 la ACM sobre Principios de computación distribuida . Association for Computing Machinery. págs. 19–28. doi :10.1145/1073814.1073818. ISBN . 1-58113-994-2. S2CID  11779779 . Consultado el 21 de abril de 2021 .
9. Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008), "Relojes de árbol de intervalos: un reloj lógico para sistemas dinámicos", en Baker, Theodore P.; Bui, Alain; Tixeuil, Sébastien (eds.), Principles of Distributed Systems (PDF) , Apuntes de clase en informática, vol. 5401, Springer-Verlag, Apuntes de clase en informática, pp. 259–274, Bibcode :2008LNCS.5401.....B, doi :10.1007/978-3-540-92221-6, ISBN 978-3-540-92220-9
10. 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, vol. 5401, p. 259, doi :10.1007/978-3-540-92221-6_18, hdl : 1822/37748 , ISBN 978-3-540-92220-9
11. Zhang, Yi (2014), "Antecedentes preliminares: resultados del reloj de árbol de intervalos", Antecedentes preliminares: resultados del reloj de árbol de intervalos (PDF)
12. Pozzetti, Tommaso; Kshemkalyani, Ajay D. (1 de abril de 2021). "Reloj vectorial codificado reiniciable para análisis de causalidad con una aplicación a la detección dinámica de carreras". IEEE Transactions on Parallel and Distributed Systems . 32 (4): 772–785. doi : 10.1109/TPDS.2020.3032293 . S2CID  220362525.
13. Lum Ramabaja (2019), El reloj Bloom , arXiv : 1905.13064 , Bibcode :2019arXiv190513064R
14. Kulkarni, Sandeep S; Appleton, Gabe; Nguyen, Duong (4 de enero de 2022). "Lograr la causalidad con relojes físicos". Actas de la 23.ª Conferencia internacional sobre computación distribuida y redes . págs. 97–106. arXiv : 2104.15099 . doi :10.1145/3491003.3491009. ISBN . 9781450395601.S2CID233476293  .​

Enlaces externos

• Por qué los relojes lógicos son fáciles de usar (comparación de historias causales, relojes vectoriales y vectores de versión)
• Explicación de los relojes vectoriales
• Implementación de un reloj vectorial basado en marcas de tiempo en Erlang
• Implementación de un reloj vectorial en Objective-C
• Implementación de reloj vectorial en Erlang
• ¿Por qué son difíciles los relojes vectoriales?
• Por qué Cassandra no necesita relojes vectoriales