ALGORITMO DE ELECCION

ALGORITMO DE ELECCION

1. DEFINICION

   • Son algoritmos diseñados para problemas en los cuales uno de los procesos ha de realizar una tarea especial: Elección de un coordinador
     • Estos mecanismos se activan cuando el coordinador ha fallado.

2. OBJETIVO

   • Elección única
   • Dentro de estos algoritmos encontramos las siguientes elecciones:
     • ALGORITMO EN ANILLO
       • Sobre un anillo lógico de procesos se emite un mensaje de elección
         • Cuando un proceso recibe un mensaje de elección compara el identificador recibido con el suyo.
           • –Si es menor el recibido y el proceso no es un participante, sustituye el identificador en el mensaje por el suyo y lo reenvía al vecino y se marca como participante.
           • – Si es mayor el recibido, reenvía el mensaje y se marca como participante.
           • – Si es menor el recibido y el proceso es un participante, no hace nada (no envía ningún mensaje).
           • –Si el identificador coincide con el del proceso, ese proceso es el líder.
           • ESQUEMA DEL ALGORITMO DEL ANILLO
           • EJEMPLO DIDACTICO https://www.youtube.com/watch?v=ZjDbvdwBV4M
             • ALGORITMO DE ELECCION
     • ALGORITMO DE INVITACIÓN
       • DEFINICION
         • • Se basan en timeouts: Retrasos de transmisión pueden causar la elección de múltiples líderes.
           • La pérdida de conexión entre dos grupos de procesadores puede aislar permanentemente los procesadores
       • CARACTERISTICAS
         • • Definición de grupos de procesadores con líder único.
           • • Detección y agregación de grupos
             • • Reconocimiento por parte del líder de los miembros del grupo.
       • PASOS
         • • Si un procesador detecta la pérdida del líder, entonces se declara líder y forma su propio grupo. Periódicamente el líder de cada grupo busca otros líderes de otros grupos.
           • • Dos grupos se unen por medio de mensajes de aceptación: - Como respuesta a mensajes de invitación. – De forma explícita
       • ESQUEMA DEL ALGORITMO DE INVITACION
     • ALGORITMO DEL MATÓN
       • DEFINICION
         • Este algoritmo es Tolerante a caídas de procesos durante la elección:
           • – pi conoce a los que tienen mayor id
           • – pi puede comunicarse con cualquier proceso
       • MENSAJES
         • – Election. Para iniciar una elección.
         • – Answer. Respuesta un mensaje Election.
         • – Coordinator. Mensaje para anunciar al líder
       • Algoritmo se inicia cuando pi detecta caída (timeout) del líder.
         • – Pi inicia la elección enviando un mensaje Election a todos los que tienen pid > pi, y espera algún mensaje Answer.
           • – Si ninguno de ellos responde, entonces pi supone que él tiene mayor id, y envía un mensaje Coordinador auto-anunciándose como nuevo líder
             • – Si pi recibe un Answer de lo que tiene pid > pi, entonces espera un tiempo T para que ´ese proceso se anuncie como líder. De lo contario reenvía el mensaje Election.
               • Si pi recibe un Election de un pid < pi, entonces responde con un Answer, e inicia una nueva elección.

Bilder und Dateien der Mindmap