stringtranslate.com

Algoritmo de Hirschberg-Sinclair

El algoritmo de Hirschberg-Sinclair es un algoritmo distribuido diseñado para problemas de elección de líderes en una red de anillo síncrona . Lleva el nombre de sus inventores, Dan Hirschberg y JB Sinclair.

El algoritmo requiere el uso de ID únicos (UID) para cada proceso. El algoritmo funciona en fases y envía su UID en ambas direcciones. El mensaje sale a una distancia de 2 saltos de número de fase y luego regresa al proceso de origen. Mientras los mensajes "salen", cada proceso de recepción comparará el UID entrante con el suyo. Si el UID es mayor que su propio UID, continuará con el mensaje. De lo contrario, si el UID es menor que su propio UID, no transmitirá la información. Al final de una fase, un proceso puede determinar si enviará mensajes en la siguiente ronda si recibió ambos mensajes entrantes. Las fases continúan hasta que un proceso recibe sus dos mensajes de salida, de sus dos vecinos. En este momento el proceso sabe que es el UID más grande del ring y se declara líder.

Referencias