Tiempo y causalidad

Tiempo, causalidad y estado global
Sistemas Distribuidos
Alberto Lafuente, Mikel Larrea Dpto. ATC, UPV/EHU

Tiempo, causalidad y estado global
1 Introducción 2 Tiempo físico
2.1 Sincronización externa 2.2 Sincronización interna 2.3 Compensación de desviaciones 2.4 Ejemplos

3 Tiempo lógico y orden de eventos
3.1 Modelo de eventos 3.2 Relojes lógicos de Lamport 3.3 Vectores de tiempos4 Estado global y consistencia
4.1 Modelo del sistema 4.2 Determinación de estados globales consistentes 4.3 Algoritmo de Chandy y Lamport
Tiempo, causalidad y estado global - Alberto Lafuente, Mikel Larrea, UPV/EHU 2

1 Introducción
• En un sistema distribuido el estado global se encuentra distribuido entre los nodos
– reloj estándar en cada nodo – comunicación entre nodos: retardos –cada nodo posee una visión subjetiva del estado global

• Ejemplos:
– en el instante t1 se manda un mensaje desde el nodo A al nodo B, que lo recibe en el instante t2, con t2 < t1 – establecer con precisión absoluta el montante de los depósitos en todas las cuentas bancarias de todos los bancos del mundo en un instante de tiempo dado
Tiempo, causalidad y estado global - Alberto Lafuente, MikelLarrea, UPV/EHU 3

1 Introducción
• Propuesta de solución: un único reloj preciso + red dedicada para transmitir la señal sin retardos
– no es práctico (coste), o es inviable (Internet)

• Solución: tiempo distribuido
– cada nodo posee su propio reloj (tiempo físico local) – los relojes son imprecisos: necesario ajustarlos periódicamente a un tiempo físico de referencia

• Por otra parte,la gestión consistente del estado global requiere al menos ordenar los eventos producidos por los nodos (causalidad)
– tiempo lógico
Tiempo, causalidad y estado global - Alberto Lafuente, Mikel Larrea, UPV/EHU 4

Clock Synchronization

• When each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time.
Tiempo, causalidad y estadoglobal - Alberto Lafuente, Mikel Larrea, UPV/EHU 5

2 Tiempo físico
• Los relojes de los computadores son de cuarzo
• La frecuencia de oscilación varía con la temperatura • deriva: ~10-6 (90ms en un día, 1s cada 11,6 días)

• Relojes atómicos: gran precisión, muy caros
• deriva: ~10-13 (9ns en un día, 1s cada 300000 años) • precio: $50.000 - $100.000 !!!

• Tipos de sincronización:
•conocer el instante preciso en que se produce un evento en un nodo: sincronización externa • medir el intervalo entre dos eventos producidos en nodos diferentes (por ejemplo, envío y recepción de un mensaje), usando los relojes locales de cada nodo: sincronización interna • la interna no implica la externa, pero al revés sí
Tiempo, causalidad y estado global - Alberto Lafuente, Mikel Larrea,UPV/EHU 6

Relojes atómicos

NIST-7 (1993) Deriva: 5 x 10-15

NIST-F1 (2005) Deriva: 5 x 10-16
7

Tiempo, causalidad y estado global - Alberto Lafuente, Mikel Larrea, UPV/EHU

2 Tiempo físico
• Definiciones:
– Segundo solar o astronómico: 1/86.400 del periodo de rotación de la Tierra (mean solar second)
• pese a ser perfectamente válido para las situaciones de la vida cotidiana, laTierra no gira a velocidad constante (va perdiendo lentamente velocidad), por lo que no sirve como referencia

– Segundo atómico (IAT, 1967): 9.192.631.770 periodos de transición en un átomo de Cesio-133. Los relojes atómicos miden este tiempo
• deriva de 3*10-8 con el segundo solar (~1 s al año)

– Tiempo universal coordinado (UTC): medido en segundos atómicos, sincronizado con tiempo astronómico(diferencia > 900 ms ⇒ inserción de 1 s)
Tiempo, causalidad y estado global - Alberto Lafuente, Mikel Larrea, UPV/EHU 8

2 Tiempo físico
• Definiciones:
– Tiempo físico de referencia: normalmente UTC – Resolución: periodo entre dos actualizaciones del registro del tiempo local
• debe ser menor que el intervalo de tiempo mínimo entre dos eventos producidos consecutivamente en el nodo

–...