Cada sistema distribuido tiene una serie de procesos que se ejecutan en una serie de servidores físicos diferentes. Estos procesos se comunican entre sí a través de canales de comunicación mediante mensajes de texto. Estos procesos no tienen una memoria compartida ni un reloj físico común, esto dificulta el proceso de determinación del estado global instantáneo.
Un proceso podría registrar su propio estado local en un momento dado, pero los mensajes que están en tránsito (en camino a ser entregados) no se incluirían en el estado registrado y, por lo tanto, el estado real del sistema sería incorrecto después del tiempo en se entrega el mensaje de tránsito.
Chandy y Lamport fueron los primeros en proponer un algoritmo para capturar el estado global consistente de un sistema distribuido. La idea principal detrás del algoritmo propuesto es que si sabemos que todos los mensajes que ha enviado un proceso han sido recibidos por otro, entonces podemos registrar el estado global del sistema.
Cualquier proceso en el sistema distribuido puede iniciar este algoritmo de grabación de estado global usando un mensaje especial llamado MARKER . Este marcador atraviesa el sistema distribuido a través de todos los canales de comunicación y hace que cada proceso registre su propio estado. Al final, se registra el estado de todo el sistema (estado global). Este algoritmo no interfiere con la ejecución normal de los procesos.
Supuestos del algoritmo:
- Hay un número finito de procesos en el sistema distribuido y no comparten memoria ni relojes.
- Hay un número finito de canales de comunicación y son unidireccionales y ordenados FIFO.
- Existe una ruta de comunicación entre dos procesos en el sistema.
- En un canal, los mensajes se reciben en el mismo orden en que se envían.
Algoritmo:
- Regla de envío de marcador para un proceso P :
- El proceso p registra su propio estado local
- Para cada canal saliente C del proceso P , P envía un marcador a lo largo de C antes de enviar cualquier otro mensaje a lo largo de C.
( Nota: el proceso Q recibirá este marcador en su canal entrante C1).
- Regla de recepción de marcadores para un proceso Q :
- Si el proceso Q aún no ha registrado su propio estado local, entonces
- Registre el estado del canal entrante C1 como una secuencia vacía o nula.
- Después de registrar el estado del canal entrante C1, el proceso Q sigue la regla de envío del marcador
- Si el proceso Q ya registró su estado
- Registre el estado del canal entrante C1 como la secuencia de mensajes recibidos a lo largo del canal C1 después de que se registrara el estado de Q y antes de que Q recibiera el marcador a lo largo de C1 del proceso P.
- Si el proceso Q aún no ha registrado su propio estado local, entonces
Necesidad de tomar una instantánea o registrar el estado global del sistema:
- Puntos de control: ayuda a crear puntos de control. Si la aplicación falla de alguna manera, este punto de control se puede reutilizar
- Recolección de basura: Se puede utilizar para eliminar objetos que no tienen ninguna referencia.
- Se puede utilizar en la detección de interbloqueo y terminación.
- También es útil en otras depuraciones.