히르슈베르크-싱클레어 알고리즘

Hirschberg–Sinclair algorithm

Hirschberg-Sinclair 알고리즘은 동기 링 네트워크에서의 리더 선출 문제를 위해 설계된 분산 알고리즘입니다.이것의 이름은 발명가 댄 허쉬버그와 J. B.의 이름을 따서 지어졌다. 싱클레어

이 알고리즘에서는 각 프로세스에서 Unique ID(UID; 고유 ID)를 사용해야 합니다.알고리즘은 단계별로 동작하며 UID를 양방향으로 전송합니다.메시지는 2홉의 거리를Phase Number 벗어나 발신 프로세스로 돌아갑니다.메시지가 "아웃"되는 동안 각 수신 프로세스는 착신 UID를 자체 UID와 비교합니다.UID가 자신의 UID보다 클 경우 메시지는 계속됩니다.그렇지 않으면 UID가 자신의 UID보다 작을 경우 UID는 정보를 전달하지 않습니다.국면의 마지막에, 프로세스는, 양쪽의 착신 메세지를 수신했는지 아닌지에 의해서, 다음의 라운드에서 메세지를 송신할지를 판단할 수 있습니다.프로세스는 프로세스가 양쪽 네이버에서 양쪽 출력 메시지를 수신할 때까지 계속됩니다.이 시점에서 프로세스는 링 내에서 가장 큰 UID임을 인식하고 자신을 리더로 선언합니다.

레퍼런스

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


Stub icon

이 알고리즘 또는 데이터 구조 관련 문서는 stub입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.