Entrevista de sistemas distribuidos: ¿Cuándo fallan los relojes de Lamport y cuándo se necesitan relojes vectoriales?

Prompt y casos de uso

Las réplicas se comunican mediante mensajes retrasados y no pueden depender del orden de reloj físico (wall-clock). Explica cómo razonar sobre la causalidad de eventos, por qué una marca de tiempo escalar de Lamport ofrece un ordenamiento consistente pero no una prueba de causalidad completa, y cuándo un reloj vectorial vale su costo en metadatos. La categoría central es general: razonamiento de sistemas distribuidos y trade-offs explícitos, no una base de datos o lenguaje de programación en particular.

Qué evalúa el entrevistador

• Si defines happened-before en lugar de tratar las marcas de tiempo como tiempo físico.
• Si actualizas un reloj de Lamport correctamente en eventos locales, envíos y recepciones.
• Si estableces la garantía unidireccional: a -> b implica L(a) < L(b), pero el inverso no está garantizado.
• Si comparas vectores componente por componente e identificas eventos concurrentes.
• Si analizas la pertenencia de procesos, el tamaño del vector, la sobrecarga de mensajes y la rotación de réplicas (churn).
• Si conectas la elección del reloj con una necesidad concreta, como la resolución de conflictos o el análisis de trazas.

Aclaraciones antes de responder

• ¿El objetivo es un orden total determinista, detección causal o una instantánea consistente (consistent snapshot)?
• ¿Las identidades de los procesos son fijas, o las réplicas pueden unirse, salir o reiniciarse?
• ¿Los mensajes pueden duplicarse, retrasarse o entregarse fuera de orden?
• ¿Las marcas de tiempo deben sobrevivir al almacenamiento y a la replicación entre regiones?
• ¿Son los metadatos acotados más importantes que la detección exacta de concurrencia?
• ¿Qué debe suceder cuando dos escrituras son concurrentes: fusionar, preguntar al usuario o elegir una ganadora?

Estructura de respuesta en 30 segundos

“Define happened-before como el orden del programa local más el envío antes de la recepción, cerrado transitivamente. Un reloj de Lamport se incrementa antes de cada evento local o de envío; al recibir establece max(local, received) + 1. Esto preserva la causalidad, por lo que a -> b implica L(a) < L(b), pero un escalar menor también puede provenir de eventos concurrentes no relacionados. Un reloj vectorial almacena un contador por proceso, incrementa su propia entrada y se fusiona mediante el máximo componente a componente al recibir. V(a) < V(b) componente a componente significa causalidad; los vectores incomparables significan concurrencia. Usa relojes de Lamport para un orden determinista compacto y vectores cuando se requiera distinguir actualizaciones concurrentes”.

Respuesta detallada paso a paso

Paso 1: Definir la relación.

Escribe a -> b cuando a precede a b en un proceso, a es un envío y b su recepción, o una cadena transitiva los conecta. Las lecturas de reloj físico no forman parte de esta definición.

Paso 2: Implementar un reloj de Lamport.

onLocalOrSend:
  clock = clock + 1
  attach clock to an outgoing message when sending

onReceive(messageClock):
  clock = max(clock, messageClock) + 1
  process the message

Para un orden total determinista, compara (clock, processId). El ID del proceso sirve para desempatar; no agrega información causal.

Paso 3: Establecer la garantía y el contraejemplo.

Si a -> b, las reglas de Lamport obligan a que L(a) < L(b). Lo contrario falla: dos procesos independientes pueden producir eventos con valores 4 y 7 aunque ninguno de los dos eventos haya influido en el otro. Un escalar no puede determinar si la diferencia representa causalidad o trabajo local no relacionado.

Paso 4: Implementar un reloj vectorial.

onLocalOrSend:
  vector[me] = vector[me] + 1
  attach a copy of vector to the message

onReceive(remote):
  for each process p:
    vector[p] = max(vector[p], remote[p])
  vector[me] = vector[me] + 1

Para los vectores A y B, A <= B significa que cada componente de A no es mayor que B; A < B requiere adicionalmente un componente estrictamente menor. A < B indica A -> B. Si ningún vector es menor que el otro, los eventos son concurrentes bajo el conjunto de procesos representado.

Paso 5: Comparar costo y membresía.

Los metadatos de Lamport consisten en un escalar más un desempate opcional. Los metadatos de vectores son proporcionales al conjunto de procesos rastreados y crecen en cada mensaje. La membresía dinámica necesita una época (epoch), representación dispersa, dotted version vectors u otra política explícita; reutilizar silenciosamente un ID de proceso puede fusionar historias no relacionadas.

Paso 6: Elegir un caso de uso.

Para un visor de registros que solo necesita un orden repetible, las marcas de tiempo de Lamport más un desempate estable suelen ser suficientes. Para la replicación con múltiples escritores (multi-writer), usa vectores cuando las escrituras concurrentes necesiten una presentación separada o una fusión a nivel de dominio. Un reloj vectorial no resuelve el conflicto por sí mismo; proporciona evidencia que el mecanismo de resolución debe manejar.

Paso 7: Definir el comportamiento ante fallos y recuperación.

Persiste el reloj junto con el evento o estado que describe, restáuralo de forma monótona tras un reinicio y decide cómo tratar los mensajes de una época anterior. Prueba mensajes retrasados, duplicados, reordenados y concurrentes; la sincronización de relojes físicos no reemplaza estas reglas.

Respuesta de muestra de alta calidad

“Happened-before es el orden parcial derivado del orden local, el envío antes de la recepción y la transitividad. Los relojes de Lamport se incrementan en eventos locales/de envío y usan max(local, received)+1 en la recepción. Garantizan que a -> b implica L(a) < L(b), pero valores escalares iguales u ordenados no pueden probar que dos eventos estén causalmente relacionados. Un reloj vectorial incrementa el componente del emisor y fusiona los vectores mediante el máximo componente a componente antes de incrementar el componente del receptor. Si un vector es estrictamente menor componente a componente, ese evento ocurrió antes que el otro; los vectores incomparables son concurrentes. Elijo relojes de Lamport para un ordenamiento determinista compacto, vectores para la detección de conflictos, y calculo los metadatos de vectores más una política de membresía/época antes de considerar completo el diseño”.

Errores comunes

• Ordenar por tiempo de reloj físico → el sesgo del reloj (clock skew) y el retraso pueden invertir la causalidad → define happened-before explícitamente.
• Afirmar que L(a) < L(b) prueba a -> b → los relojes escalares solo proporcionan una implicación unidireccional → proporciona el contraejemplo concurrente.
• Olvidar el incremento de recepción → los eventos locales posteriores pueden parecer más antiguos que el mensaje → aplica max + 1 antes de procesar.
• Fusionar vectores mediante suma → los contadores representan conocimiento, no cantidades para sumar → toma el máximo componente a componente.
• Comparar vectores lexicográficamente → el orden lexicográfico oculta la concurrencia → usa la comparación componente a componente.
• Tratar un reloj vectorial como resolución de conflictos → detecta concurrencia pero no puede elegir la semántica de dominio → define una fusión o decisión del usuario.
• Ignorar la membresía y el reinicio → los IDs reutilizados pueden confundir historiales → usa épocas o una política de membresía explícita.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Pueden los relojes de Lamport detectar concurrencia?

No. Pueden probar que un evento precede a otro cuando el orden escalar se deriva de una ruta causal conocida, pero un par ordenado de valores escalares también puede pertenecer a procesos no relacionados.

Pregunta de seguimiento 2: ¿Por qué agregar un ID de proceso a una marca de tiempo de Lamport?

El ID desempata para producir un orden total determinista. No mejora el conocimiento causal y no debe presentarse como un sustituto del reloj vectorial.

Pregunta de seguimiento 3: ¿Qué significa un vector incomparable?

No se sabe que ninguno de los eventos haya influido en el otro dentro del conjunto de procesos rastreados, por lo que son concurrentes. La aplicación aún decide si fusionar, conservar ambos o rechazar uno.

Pregunta de seguimiento 4: ¿Qué sucede cuando se duplica un mensaje?

El receptor toma los máximos componente a componente, por lo que reproducir el mismo vector no reduce el conocimiento. Es posible que la aplicación aún necesite IDs de mensaje para efectos secundarios idempotentes.

Pregunta de seguimiento 5: ¿Cómo se acotan los metadatos vectoriales?

Rastrea miembros activos, usa representaciones dispersas o con puntos (dotted), o debilita la garantía con una aproximación documentada. Un límite fijo que descarta miembros silenciosamente puede producir falsa concurrencia o falso ordenamiento.

Pregunta de seguimiento 6: ¿Los relojes físicos sincronizados hacen innecesarios a los relojes lógicos?

No. La sincronización tiene márgenes de error y fallos; las marcas de tiempo físicas pueden ayudar con la visualización y la retención, mientras que los relojes lógicos codifican la causalidad derivada de los mensajes.

Pregunta de seguimiento 7: ¿Cómo probarías la implementación?

Genera trazas con eventos locales, de envío, de recepción, retrasados, duplicados y concurrentes. Asegura que cada arista conocida de happened-before esté ordenada, que cada fusión de vectores sea monótona y que los pares intencionalmente concurrentes permanezcan incomparables.