Elección de Líder Flashcards
Qué proceso puede ser elegido líder? Y cuáles no?
Los algoritmos normalmente eligen como líder al que tenga el id mayor, pero a priori, cualquiera de los procesos pueden ser elegidos como líder
Por qué se elige un líder?
Porque se necesita que uno de los procesos actúe de manera diferente al resto. Ya sea para coordinar o para ejecutar código especial que sólo debe ser ejecutado por una única entidad.
Explicar el algoritmo bully de elección de líder.
En el algoritmo bully, el proceso de mayor id será elegido líder.
- Inicialmente, un proceso A detecta que se cayó el líder.
- Proceso A envía mensaje de tipo ELECTION a todos los procesos con mayor Id que él.
- Si algún proceso responde al mensaje, es porque hay nodos con id mayores a él vivos, por lo que él no es el líder.
- Si ningún proceso responde al mensaje, no hay nodos vivos con id mayores a él, por lo que él es el nuevo líder.
- Si al proceso B le llega un mensaje de tipo ELECTION, es porque otro proceso ya se dio cuenta de que el líder se cayó y se está ejecutando el algoritmo de elección de líder. Como le llegó el mensaje, el emisor del mismo es un proceso de menor id que B. Proceso B responde al mensaje y manda mensajes a los procesos con mayor id que él.
- El que se reconoce como líder manda un mensaje de tipo COORDINATOR con la info del nuevo líder.
Explicar el algoritmo ring de elección de líder.
Este algoritmo requiere que los procesos estén organizados en forma lógica de anillo, como una lista circular simplemente enlazada.
- Inicialmente, un proceso A detecta que se cayó el líder.
- Proceso A crea un mensaje de tipo ELECTION, incluyendo una lista con su id, que se lo envía a su siguiente.
- Proceso B recibe el mensaje tipo ELECTION, agrega su id a la lista, y se lo pasa a su siguiente.
- Eventualmente, A vuelve a recibir la lista, y al revisar que su id ya se encuentra en la lista, busca el mayor id; ése sería el nuevo líder. Cuando se define el id del nuevo líder, A envía un mensaje de tipo COORDINATOR a su siguiente con la información del líder.
- Eventualmente, A vuelve a recibir el mensaje de tipo COORDINATOR. Cuando ya dio una vuelta entera, se descarta el mensaje.
Qué pasa si dos nodos independientes reconocen a la vez que se cayó el líder? Funcionarán los algoritmos explicados?
Los dos algoritmos explicados funcionan sin importar cuántos procesos detectan a la vez que el líder se cayó. Ambos son determinísticos, se llegará al mismo resultado no importa cuántas veces se ejecute.
