Hirschberg-Sinclair-algoritm

Hirschberg -Sinclair-algoritmen är en distribuerad algoritm designad för problem med ledareval i ett synkront ringnätverk . Den är uppkallad efter dess uppfinnare, Dan Hirschberg och JB Sinclair.

Algoritmen kräver användning av unika ID:n (UID) för varje process. Algoritmen arbetar i faser och skickar ut sitt UID i båda riktningarna. Meddelandet går ut ett avstånd på 2 ^{fasnummerhopp} och sedan går meddelandet tillbaka till ursprungsprocessen. Medan meddelandena är på väg "ut" kommer varje mottagningsprocess att jämföra det inkommande UID:t med sitt eget. Om UID är större än dess eget UID kommer det att fortsätta meddelandet på. Annars om UID är mindre än dess eget UID kommer det inte att vidarebefordra informationen. I slutet av en fas kan en process avgöra om den kommer att skicka ut meddelanden i nästa omgång genom att ta emot båda sina inkommande meddelanden. Faserna fortsätter tills en process tar emot båda sina ut-meddelanden, från båda sina grannar. Vid denna tidpunkt vet processen att det är den största UID i ringen och förklarar sig själv som ledare.

•   Hirschberg, DS ; Sinclair, JB (november 1980), "Decentralized extrema-finding in circular configurations of processors", Communications of the ACM , 23 (11): 627–628, doi : 10.1145/359024.359029 , S2CID 3029
•   Lynch, Nancy A. (1996), "15.1.2 The HS Algorithm", Distributed Algorithms , Morgan Kaufmann Publishers, Inc., s. 482–483, ISBN 9780080504704
•   Tel, Gerard (2000), Introduction to Distributed Algorithms , Cambridge University Press, s. 232–233, ISBN 9780521794831
•   Garg, Vijay K. (2002), "9.4 Hirschberg–Sinclair Algorithm", Elements of Distributed Computing , John Wiley & Sons, s. 111–112, ISBN 9780471036005