HS algorithm
Encyclopedia
The HS Algorithm is named after Dan Hirschberg
and J. B. Sinclair. It is a distributed algorithm designed for the Leader Election
problem in a Synchronous Ring.
The algorithm requires the use of unique IDs (UID) for each process. The algorithm works in phases and sends its UID out in both directions. The message goes out a distance of 2Phase Number hops and then the message heads back to the originating process. While the messages are heading "out" each receiving process will compare the incoming UID to its own. If the UID is greater than its own UID then it will continue the message on. Otherwise if the UID is less than its own UID, it will not pass the information on. At the end of a phase, a process can determine if it will send out messages in the next round by if it received both of its incoming messages. Phases continue until a process receives both of its out messages, from both of its neighbors. At this time the process knows it is the largest UID in the ring and declares itself the leader.
Dan Hirschberg
Daniel S. Hirschberg is a full professor in Computer Science at University of California, Irvine. His research interests are in the theory of design and analysis of algorithms....
and J. B. Sinclair. It is a distributed algorithm designed for the Leader Election
Leader election
In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers . Before the task is begun, all network nodes are unaware which node will serve as the "leader," or coordinator, of the task...
problem in a Synchronous Ring.
The algorithm requires the use of unique IDs (UID) for each process. The algorithm works in phases and sends its UID out in both directions. The message goes out a distance of 2Phase Number hops and then the message heads back to the originating process. While the messages are heading "out" each receiving process will compare the incoming UID to its own. If the UID is greater than its own UID then it will continue the message on. Otherwise if the UID is less than its own UID, it will not pass the information on. At the end of a phase, a process can determine if it will send out messages in the next round by if it received both of its incoming messages. Phases continue until a process receives both of its out messages, from both of its neighbors. At this time the process knows it is the largest UID in the ring and declares itself the leader.