Algoritmo abusón
# Algoritmo abusón

El algoritmo abusón es un método, dentro de la computación distribuida, para la elección dinámica de un coordinador según el ID de los procesos. El proceso con el ID mayor será seleccionado como el coordinador del sistema distribuido.

Es un algoritmo parecido al de Anillo, ya que utiliza mensajes de elección, respuesta y coordinación para determinar al nodo líder.

## Premisas

* El sistema es síncrono y utiliza tiempo de espera para la identificación de fallos en los procesos.
* Se permite que los procesos se bloqueen/caigan durante la ejecución del algoritmo.
* La entrega de mensajes entre procesos se supone fiable.
* Los IDs de los procesos deben ser conocidos.

Comparado con el Algoritmo en Anillo:

* Se supone que el sistema es síncrono.
* Utiliza el tiempo de espera para detectar fallos/caídas en los procesos.
* Cada proceso conoce qué procesos tienen el ID más alto que el suyo y puede comunicarse con ellos.

## Tipos de mensaje

* Mensaje de Elección: Enviados para comunicar que se va a seleccionar un nuevo coordinador.
* Mensaje de Respuesta: Encargados de responder al mensaje de elección.
* Mensaje de Coordinador: Enviado para comunicar el ID del proceso seleccionado.

## Funcionamiento del algoritmo

Cuando un proceso P detecta que el coordinador actual, por mensaje de tiempo de espera o fallo, está caído o bloqueado, se encarga de iniciar unas elecciones, este procedimiento se encargará de elegir el nuevo coordinador realizando las siguientes acciones: (Hay que tener en cuenta que es posible que varios procesos puedan descubrir la caída del coordinador de forma concurrente).

* P emite un mensaje de elección a todos los demás procesos con ID de proceso más alto, esperando un "estoy aquí" (mensaje de respuesta u OK) como respuesta de los procesos aún activos.
* Si P no recibe ninguna contestación de algún proceso cuyo ID sea superior, automáticamente es elegido como coordinador y multidifunde al resto de procesos que es el nuevo coordinador (mensaje de coordinador).
* Si P recibe una contestación de un proceso con ID más alto, P espera una cierta cantidad de tiempo para que el proceso multidifunda el mensaje comunicando al resto de procesos que ahora es él el coordinador. Si no recibe este mensaje a tiempo, reenvía el mensaje de elección.
* Si P recibe un mensaje de elección de otro proceso con un ID menor, envía un mensaje "estoy aquí" de vuelta y empieza de nuevo la elección de coordinador.

Aquel proceso con identificador más alto (el más "grandullón") es el que se hace coordinador. De esto le viene el nombre al algoritmo - un proceso con un ID más alto intimida a un proceso con un ID más bajo. Hay que tener en cuenta que si P recibe un mensaje de coordinador de un proceso con un ID más bajo, inmediatamente inicia una nueva elección.

* El Proceso 4 detecta que el Coordinador (Proceso 7) está caído.
* El Proceso 4 notifica a los procesos con un ID superior que el Coordinador está caído.
* Los procesos que están vivos y han recibido el mensaje, devuelven un OK.
* Los Procesos 5 y 6 repiten los pasos efectuados por el Proceso 4.
* El Proceso 6 envía OK al proceso 5 y detecta que es el proceso con mayor ID.
* Como el Proceso 6 es el que tiene el mayor ID se proclama Coordinador y se lo comunica al resto de procesos.

## Procesos

Si un proceso sabe que tiene el ID más alto:

* Se elige a sí mismo coordinador enviando el mensaje coordinador a todos los procesos cuyo ID sea más bajo (proceso abusón).
* Si no tiene el ID más alto:
   * Multidifunde el mensaje de elección entre todos los procesos con el ID más alto y espera un mensaje respuesta.

   * Si tras un tiempo T no recibe ningún mensaje respuesta, se elige a sí mismo como coordinador.

   * Si recibe un mensaje respuesta, espera un mensaje coordinador.

   ** Si recibe un mensaje coordinador, almacena el ID del nuevo coordinador.

   ** Si no recibe ningún mensaje, comienza una nueva elección.
* Si un proceso se recupera, o se lanza un proceso sustituto con el mismo ID, éste comienza una nueva elección, aunque el coordinador actual esté funcionando.

## Características

* Cumple la Pervivencia del sistema distribuido, ya que todos los procesos conocen el identificador del coordinador al finalizar el proceso de elección.
* Presenta algunos problemas de Seguridad del sistema distribuido:
* Si se cae el proceso P (coordinador), pero se recupera al mismo tiempo que otro proceso Q decide ser el coordinador, algún proceso puede recibir dos mensajes coordinador con distintos identificadores.
* Los valores de los tiempos de espera son imprecisos (el sistema no es síncrono).

## Rendimiento

| Mejor caso | Peor caso |
| - | - |
| El proceso con el segundo identificador más alto detecta el fallo del coordinador | El proceso con identificador más bajo detecta el fallo del coordinador |
| N-2 mensajes coordinador | $O(N^2)$ |
