Algoritmo de Hirschberg-Sinclair

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

El algoritmo requiere el uso de identificadores únicos (UID) para cada proceso. El algoritmo funciona por fases y envía su UID en ambas direcciones. El mensaje viaja una distancia de 2 saltos ^{de número de fase} y luego regresa al proceso de origen. Mientras los mensajes se envían, cada proceso receptor compara el UID entrante con el suyo. Si el UID es mayor que el suyo, continúa el mensaje. De lo contrario, si el UID es menor que el suyo, no transmite la información. Al final de una fase, un proceso puede determinar si enviará mensajes en la siguiente ronda según si ha recibido ambos mensajes entrantes. Las fases continúan hasta que un proceso recibe ambos mensajes salientes de ambos vecinos. En ese momento, el proceso sabe que tiene el UID más alto en el anillo y se declara líder.

• Hirschberg, DS ; Sinclair, JB (noviembre de 1980), "Búsqueda de extremos descentralizada en configuraciones circulares de procesadores", Communications of the ACM , 23 (11): 627–628 , doi : 10.1145/359024.359029 , S2CID 15299430 
• Lynch, Nancy A. (1996), "15.1.2 El algoritmo HS", Algoritmos distribuidos , Morgan Kaufmann Publishers, Inc., págs. 482–483 , ISBN  9780080504704
• Tel, Gerard (2000), Introducción a los algoritmos distribuidos , Cambridge University Press, pp. 232–233 , ISBN  9780521794831
• Garg, Vijay K. (2002), "9.4 Algoritmo de Hirschberg–Sinclair", Elementos de computación distribuida , John Wiley & Sons, pp. 111–112 , ISBN  9780471036005