Algoritmo de elección por invitación

El algoritmo de elección por invitación es un método (diseñado por Héctor García Molina^[1] en 1982) que se utiliza en los sistemas distribuidos. Su función principal es seleccionar un coordinador entre varios procesos (cada cuál con su identificador) para organizarlos en un grupo mayor por medio de invitaciones.

Principios editar

Este algoritmo se basa en dos principios:

Recuperación: cuando el coordinador del grupo falla, los procesos detectan este fallo, creando un nuevo grupo de un miembro, del cual son coordinadores. Esto mismo sucede cuando un proceso es incorporado o después de fallar se vuelve a activar.
Grupos grandes: el coordinador de cada grupo de procesos invita a su grupo al resto de coordinadores para hacer su grupo más grande.

Características editar

Se crean los grupos de procesadores con un único líder.
Detección y agregación de grupos.
Reconocimiento de los miembros del grupo por parte del líder.

Funcionamiento editar

Inicialmente, cada proceso está en un grupo de un proceso (del cual es su coordinador). Estos procesos disponen de un identificador de grupo y un 'ID'.

Frecuentemente los coordinadores buscarán otros coordinadores, invitándoles a unirse a su grupo con el mensaje de invitación, dando prioridad a los mensajes que le lleguen de un proceso con el 'ID' más alto.

Una vez que el coordinador recibe la invitación, la aceptará (en caso de que tenga una prioridad menor que el transmisor) y notificará a los miembros de su grupo (en el caso de que tenga alguno), y dichos miembros aceptarán con un mensaje de confirmación, siendo el coordinador nuevo el que envió la invitación.

Todo esto se repetirá hasta que se consiga el grupo más grande que se pueda o hasta que se necesite otro grupo para alguna otra tarea.

Si en el transcurso de este proceso se produce algún tipo de fallo, el proceso se reinicia.

Imagen del proceso del algoritmo

Como podemos ver en el ejemplo de la imagen superior,^[2] el grupo compuesto por el proceso coordinador '1' envía invitaciones a los grupos compuestos por '2' y por '3', '4' y '5' (primer paso), de manera que estos aceptan la invitación del grupo compuesto por '1' (paso dos), formándose un nuevo grupo más grande con el proceso cuatro fallido (tercer paso).

Mensajes editar

Mensaje de invitación: es enviado por un coordinador de un grupo hacia otro coordinar para que se una a él.
Aceptar mensaje: es enviado por el coordinador del grupo hacia el coordinador que le ha invitado a unirse a su grupo.
Mensaje de coordinador a miembro: es enviado por el coordinador a los miembros de su grupo diciéndoles que se van a unir a un grupo nuevo.
Mensaje de confirmación para los miembros: enviado por los miembros que aceptan el nuevo 'id' del grupo o su cambio de grupo.
Mensaje de confirmación del coordinador: es enviado por el coordinador del nuevo grupo unido para confirmar a los miembros el nuevo 'id'.

Referencias editar

↑ «Héctor García Molina».
↑ «Sincronización de sistemas distribuidos». ETS de Ingenieros Informáticos.

Bibliografía editar

Datos: Q111737389

[1] «Héctor García Molina».

[2] «Sincronización de sistemas distribuidos». ETS de Ingenieros Informáticos.

[1]

[2]