Hirschberg–Sinclair algorithm
It is proposed that this article be deleted because of the following concern:
If you can address this concern by improving, copyediting, sourcing, renaming, or merging the page, please edit this page and do so. You may remove this message if you improve the article or otherwise object to deletion for any reason. Although not required, you are encouraged to explain why you object to the deletion, either in your edit summary or on the talk page. If this template is removed, do not replace it. This message has remained in place for seven days, so the article may be deleted without further notice. Find sources: "Hirschberg–Sinclair algorithm" – news · newspapers · books · scholar · JSTOR Nominator: Please consider notifying the author/project: {{subst:proposed deletion notify|Hirschberg–Sinclair algorithm|concern=Non notable concept. [[WP:OR]] from single page of a book. Not mentioned in [[Dan Hirschberg]]'s bio and the other co-inventor is non notable (redlink)}} ~~~~Timestamp: 20171124063300 06:33, 24 November 2017 (UTC) Administrators: delete |
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.
References
- Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers, Inc. (1996) pp. 31-35.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |