Algoritmo de acoso

En computación distribuida , el algoritmo bully es un método para elegir dinámicamente un coordinador o líder de entre un grupo de procesos informáticos distribuidos. El proceso con el número de identificación más alto entre los procesos que no han fallado es seleccionado como coordinador.

Supuestos

El algoritmo supone que: ^{[ 1 ]}

El sistema es síncrono.
Los procesos pueden fallar en cualquier momento, incluso durante la ejecución del algoritmo.
Un proceso falla al detenerse y se recupera del fallo reiniciándose.
Existe un detector de fallos que detecta los procesos que han fallado.
La entrega de mensajes entre procesos es fiable.
Cada proceso conoce su propio ID y dirección, así como los de todos los demás procesos.

Algoritmo

El algoritmo utiliza los siguientes tipos de mensajes:

Mensaje electoral: Enviado para anunciar las elecciones.
Respuesta (en vivo) Mensaje: Responde al mensaje de Elección.
Mensaje del coordinador (de victoria): Enviado por el ganador de las elecciones para anunciar la victoria.

Cuando un proceso P se recupera de un fallo, o el detector de fallos indica que el coordinador actual ha fallado, P realiza las siguientes acciones:

Si P tiene el ID de proceso más alto, envía un mensaje de victoria a todos los demás procesos y se convierte en el nuevo coordinador. De lo contrario, P difunde un mensaje de elección a todos los demás procesos con ID de proceso superiores al suyo.
Si P no recibe respuesta después de enviar un mensaje de Elección, entonces transmite un mensaje de Victoria a todos los demás procesos y se convierte en el Coordinador.
Si P recibe una respuesta de un proceso con un ID superior, no envía más mensajes para esta elección y espera un mensaje de victoria. (Si no recibe un mensaje de victoria después de un tiempo, reinicia el proceso desde el principio).
Si P recibe un mensaje de Elección de otro proceso con un ID más bajo, envía un mensaje de Respuesta y, si aún no ha iniciado una elección, inicia el proceso de elección desde el principio, enviando un mensaje de Elección a los procesos con números más altos.
Si P recibe un mensaje de Coordinador, trata al remitente como si fuera el coordinador.

Análisis

Seguridad

La propiedad de seguridad esperada de los protocolos de elección de líder es que cada proceso no defectuoso elija un proceso Q o ninguno. Cabe destacar que todos los procesos que eligen un líder deben decidir que el mismo proceso Q sea el líder. El algoritmo Bully satisface esta propiedad (bajo el modelo de sistema especificado), y en ningún momento es posible que dos procesos del grupo tengan una visión contradictoria sobre quién es el líder, excepto durante una elección. Esto es cierto porque, de no ser así, habría dos procesos X e Y tales que ambos enviarían el mensaje de Coordinador (victoria) al grupo. Esto implicaría que X e Y también se habrían enviado mensajes de victoria mutuamente. Pero esto no puede ocurrir, ya que antes de enviar el mensaje de victoria, se habrían intercambiado mensajes de Elección entre ambos, y el proceso con un ID de proceso menor entre los dos nunca enviaría mensajes de victoria. Tenemos una contradicción, y por lo tanto, nuestra suposición inicial de que hay dos líderes en el sistema en cualquier momento dado es falsa, lo que demuestra que el algoritmo Bully es seguro.

En vivo

La disponibilidad también está garantizada en el modelo síncrono de recuperación ante fallos. Consideremos el proceso que pretende ser el líder y que falla tras enviar un mensaje de Respuesta (Disponible) pero antes de enviar un mensaje de Coordinador (de victoria). Si no se recupera antes de que expire el tiempo de espera establecido para los procesos con ID inferior, uno de ellos acabará convirtiéndose en líder (incluso si otros procesos fallan). Si el proceso que falló se recupera a tiempo, simplemente envía un mensaje de Coordinador (de victoria) a todo el grupo.

utilización del ancho de banda de la red

Suponiendo que los mensajes del algoritmo de acoso tienen tamaños fijos (conocidos e invariables), se intercambia la mayor cantidad de mensajes en el grupo cuando el proceso con el ID más bajo inicia una elección. Este proceso envía (N−1) mensajes de elección, el siguiente ID más alto envía (N−2) mensajes, y así sucesivamente, lo que resulta en $\Theta \left(N^{2}\right)$ mensajes electorales. También están los $\Theta \left(N^{2}\right)$ Mensajes vivos y $\Theta \left(N\right)$ mensajes del coordinador, lo que hace que el número total de mensajes intercambiados en el peor de los casos sea $\Theta \left(N^{2}\right)$ .

Véase también

Referencias

↑ Coulouris, George; Dollimore, Jean; Kindberg, Tim (2000). Sistemas distribuidos: conceptos y diseño (3.ª ed.). Addison Wesley. ISBN 978-0201619188.

Witchel, Emmett (2005). "Coordinación distribuida" . Recuperado el 4 de mayo de 2005.
Hector Garcia-Molina, Elecciones en un sistema de computación distribuida, IEEE Transactions on Computers, Vol. C-31, No. 1, enero (1982) 48–59
L. Lamport, R. Shostak y M. Pease, "El problema de los generales bizantinos", ACM Transactions on Programming Languages and Systems, vol. 4, n.º 3, julio de 1982.