¿Cómo implemento un algoritmo de sincronización de reloj Berkeley en C ++?
Trataré esto como una pregunta de tarea, y en su lugar esbozaré mi propia versión de la implementación.
En lo sucesivo, todos los mensajes de red UDP están representados por [math] \ Pi_ {} [] [/ math], donde [math] [/ math] es uno de:
- ¿Cómo se puede probar que la ruta única a través de un árbol de expansión mínima entre dos nodos es una ruta más corta de "cuello de botella"?
- ¿Cuáles son los algoritmos comunes que uno debe conocer?
- ¿Qué es la fuerza bruta?
- Si todos los códigos de computadora son 0s y 1s, ¿cómo reconoce y entiende la computadora estos símbolos en primer lugar?
- ¿Cuál es la complejidad temporal del uso de un árbol de búsqueda binario para ordenar los números de un grupo?
- [math] req [/ math] – “aquí está mi hora actual, ¿cuál es la suya?”
- [math] resp [/ math] – “Veo tu hora actual y voy a ir por mi cuenta”
- [matemáticas] adj [/ matemáticas] – “aquí está su ajuste de tiempo en adelante”
Paso 0 : Elija un líder entre los nodos [math] n [/ math] en su clúster. El protocolo de elección de líder específico depende en gran medida de sus circunstancias, por lo que solo le señalaré esta descripción general para conocer algunas opciones.
Paso 1 : Para cada “cliente” [matemática] x = 1 .. (n-1) [/ matemática], el líder:
- Obtenga su hora actual, [matemáticas] T_ {M_x} [/ matemáticas]
- Enviar [math] C_x [/ math] su hora actual: [math] \ Pi [/ math] [math] _ {req} [T_ {M_x}] [/ math]
Paso 2 : Cuando cada cliente recibe [matemática] \ Pi [/ matemática] [matemática] _ {req} [T_ {M_x}] [/ matemática], hará lo siguiente:
- Obtenga su hora actual, [matemáticas] T_ {C_x} [/ matemáticas]
- Envíe [math] M [/ math] tanto el tiempo recibido de [math] M [/ math] como su hora actual: [math] \ Pi [/ math] [math] _ {resp} [T_ {M_x}, T_ {C_x}] [/ matemáticas]
Paso 3 : Cuando el líder recibe [matemática] \ Pi [/ matemática] [matemática] _ {resp} [T_ {M_x}, T_ {C_x}] [/ matemática], hará lo siguiente:
- Obtenga su hora actual, [matemáticas] T_ {R_x} [/ matemáticas]
- Calcule el retraso de comunicaciones unidireccional de [math] C_x [/ math]: [math] \ delta_ {C_x} = \ frac {T_ {R_x} – T_ {M_x}} {2} [/ math]
- Calcule la compensación de tiempo de [math] C_x [/ math]: [math] \ Delta_ {C_x} = T_ {C_x} – T_ {M_x} – \ delta_ {C_x} [/ math]
Paso 4 : Una vez que ha acumulado [math] \ Delta_ {C_x} [/ math] de todos los clientes [math] n-1 [/ math], calcula el desplazamiento de tiempo promedio para todo el clúster:
[matemáticas] \ Delta_ \ tau = \ frac {\ sum ^ {x = 1} _ {n-1} {\ Delta_ {C_x}}} {n} [/ matemáticas]
(Tenga en cuenta que estamos sumando los términos [matemática] n-1 [/ matemática] pero dividiendo por [matemática] n [/ matemática], porque el desplazamiento propio del líder [matemático] \ Delta_M [/ matemático] es, por definición, [ matemáticas] 0 [/ matemáticas].)
Paso 5 : El líder entonces:
- Registre su propio ajuste de tiempo: [matemática] \ Phi_M = – \ Delta_ \ tau [/ matemática]
- Calcule la compensación de tiempo de cada cliente: [matemática] \ Phi_ {C_x} = \ Delta_ {C_x} – \ Delta_ \ tau [/ math]
- Envíe [math] C_x [/ math] su ajuste de tiempo: [math] \ Pi [/ math] [math] _ {adj} [\ Phi_ {C_x}] [/ math]
A partir de este momento, todos los nodos agregarán sus [math] \ Phi_n [/ math] a cada medición de tiempo para obtener el Tiempo de clúster coordinado (CCT).
–
Algorith El algoritmo de sincronización de reloj de Berkeley es un proyecto popular en las clases de sistemas distribuidos, porque es un algoritmo simple que está dentro de las capacidades del estudiante universitario promedio. De hecho, la parte más difícil para la mayoría de los estudiantes es en realidad administrar las comunicaciones UDP; para todo lo demás, incluidas las elecciones de líderes, el pseudocódigo correspondiente se traduce casi directamente a su lenguaje de programación favorito.
Además, en la vida real, la respuesta a “¿cómo sincronizo los relojes de mi clúster?” Es casi siempre “usar NTP”, no “implementar el algoritmo de Berkeley”.
