싱크로나이저(알고리즘)

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "동기화기" 알고리즘 – 뉴스 · 신문 · 책 · 학자 · JSTOR(2020년 11월) 이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2020년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

컴퓨터 과학에서 싱크로나이저는 비동기 프로세서 네트워크 위에서 동기식 알고리즘을 실행하는 데 사용할 수 있는 알고리즘이므로 비동기식 시스템이 동기식 네트워크로 실행될 수 있다.

이 개념은 원래 (Awerbuch, 1985)에서 알파, 베타, 감마라는 세 가지 싱크로나이저 알고리즘과 함께 제안되었으며, 이는 시간과 메시지의 복잡성 측면에서 서로 다른 절충을 제공하였다. 본질적으로, 그것들은 비동기 알고리즘(글로벌 클럭이 없는 네트워크에서 작동)이 설계하기 더 어렵고 종종 동등한 동기 알고리즘보다 덜 효율적이라는 문제에 대한 해결책이다. 싱크로나이저를 사용함으로써 알고리즘 설계자는 단순화된 "이상적 네트워크"를 처리한 다음 나중에 보다 현실적인 비동기 사례에서 작동하는 버전을 기계적으로 만들 수 있다.

사용 가능한 싱크로나이저 알고리즘

아우베르부치가 원문에서 제공한 3가지 알고리즘은 다음과 같다.

• 알파 싱크로나이저: 이것은 시간 복잡성은 낮지만 메시지 복잡성은 높다.
• 베타 동기화 장치: 이것은 시간 복잡성은 높지만 메시지 복잡성은 낮다.
• 감마 싱크로나이저: 이것은 상당히 낮은 시간과 메시지의 복잡성을 제공함으로써 알파와 베타 사이의 합리적인 절충을 제공한다.

원본 논문 이후 문헌에서 다른 싱크로나이저 알고리즘이 제안되었다.

참조

• Baruch Awerbuch (1985). "Complexity of Network Synchronization" (PDF). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)