Algoritmo de elección y procesamiento distribuido

El algoritmo distribuido es un algoritmo que se ejecuta en un sistema distribuido. El sistema distribuido es una colección de computadoras independientes que no comparten su memoria. Cada procesador tiene su propia memoria y se comunican a través de redes de comunicación. La comunicación en redes se implementa en un proceso en una máquina que se comunica con un proceso en otra máquina. Muchos algoritmos utilizados en sistemas distribuidos requieren un coordinador que realice funciones necesarias para otros procesos en el sistema. Los algoritmos de elección están diseñados para elegir un coordinador.

Algoritmos de elección:
los algoritmos de elección eligen un proceso de un grupo de procesadores para que actúe como coordinador. Si el proceso del coordinador falla debido a alguna razón, se elige un nuevo coordinador en otro procesador. El algoritmo de elección básicamente determina dónde se debe reiniciar una nueva copia del coordinador.

El algoritmo de elección asume que cada proceso activo en el sistema tiene un número de prioridad único. El proceso con mayor prioridad será elegido como nuevo coordinador. Por lo tanto, cuando falla un coordinador, este algoritmo elige el proceso activo que tiene el número de prioridad más alto. Luego, este número se envía a cada proceso activo en el sistema distribuido.

Tenemos dos algoritmos de elección para dos configuraciones diferentes de sistema distribuido.

1. El algoritmo Bully:
este algoritmo se aplica al sistema en el que cada proceso puede enviar un mensaje a todos los demás procesos del sistema.

Algoritmo: supongamos que el proceso P envía un mensaje al coordinador.

1. Si el coordinador no responde dentro de un intervalo de tiempo T, entonces se asume que el coordinador ha fallado.
2. Ahora el proceso P envía un mensaje de elección a todos los procesos con un número de alta prioridad.
3. Espera respuestas, si nadie responde durante el intervalo de tiempo T, entonces el proceso P se elige a sí mismo como coordinador.
4. Luego envía un mensaje a todos los procesos de número de menor prioridad de que es elegido como su nuevo coordinador.
5. Sin embargo, si se recibe una respuesta dentro del tiempo T de cualquier otro proceso Q,
   • (I) El proceso P nuevamente espera el intervalo de tiempo T’ para recibir otro mensaje de Q de que ha sido elegido como coordinador.
   • (II) Si Q no responde dentro del intervalo de tiempo T’, se supone que ha fallado y se reinicia el algoritmo.

2. El algoritmo del anillo:
este algoritmo se aplica a los sistemas organizados como un anillo (lógica o físicamente). En este algoritmo asumimos que el enlace entre los procesos es unidireccional y cada proceso puede enviar mensajes al proceso a su derecha solamente. La estructura de datos que utiliza este algoritmo es lista activa , una lista que tiene el número de prioridad de todos los procesos activos en el sistema.

Algoritmo –

1. Si el proceso P1 detecta una falla en el coordinador, crea una nueva lista activa que inicialmente está vacía. Envía mensaje de elección a su vecino de la derecha y agrega el número 1 a su lista activa.
2. Si el proceso P2 recibe el mensaje elect de los procesos de la izquierda, responde de 3 formas:
   • (I) Si el mensaje recibido no contiene 1 en la lista activa, entonces P1 agrega 2 a su lista activa y reenvía el mensaje.
   • (II) Si este es el primer mensaje de elección que recibe o envía, P1 crea una nueva lista activa con los números 1 y 2. Luego envía el mensaje de elección 1 seguido de 2.
   • (III) Si el Proceso P1 recibe su propio mensaje de elección 1, la lista activa para P1 ahora contiene números de todos los procesos activos en el sistema. Ahora el Proceso P1 detecta el número de mayor prioridad de la lista y lo elige como el nuevo coordinador.