버클리 알고리즘

버클리 알고리즘은 기계에 정확한 시간원이 없다고 가정하는 분산 컴퓨팅에서 클럭 동기화의 방법이다.1989년 구셀라와 자티가 버클리 캘리포니아 대학에서 개발했다.^[1]크리스티안의 알고리즘처럼 인트라넷 내에서 사용하도록 되어 있다.

알고리즘

크리스티안의 알고리즘과는 달리 리더라고 불리는 버클리 알고리즘의 서버 프로세스는 주기적으로 다른 팔로워 프로세스를 폴링한다.일반적으로 알고리즘은 다음과 같다.

1. 리더는 장, 로버츠 알고리즘과 같은 선거 과정을 통해 선택된다.
2. 리더는 크리스찬의 알고리즘과 비슷한 방식으로 자신의 시간을 답하는 추종자들을 대상으로 여론조사를 한다.
3. 리더는 메시지의 왕복 시간(RT)을 관찰하고 각 추종자와 자신의 시간을 추정한다.
4. 그런 다음 리더는 다른 값의 범위를 훨씬 벗어나 수신되는 값을 무시한 채 시계 시간을 평균한다.
5. 업데이트된 현재 시간을 다른 프로세스로 다시 보내는 대신 리더는 각 추종자가 시계를 조정해야 하는 양(양 또는 음)을 전송한다.이는 추종자 프로세스에서 RTT로 인한 추가적인 불확실성을 방지한다.

이 방법으로 평균은 개별 시계의 표류 경향을 상쇄한다.구셀라와 자티는 그들의 프로토콜을 사용하여 약 20-25밀리초 이내에 시계가 동기화되는 15대의 컴퓨터와 관련된 결과를 발표했다.

컴퓨터 시스템은 보통 리더로부터 음의 시계 변경을 받을 때 시계를 다시 감는 것을 피한다.그렇게 하는 것은 시스템 자체의 특정 알고리즘이나 make와 같은 프로그램에서 근본적인 가정인 단조로운 시간의 속성을 깨뜨릴 것이다.이 문제에 대한 간단한 해결책은 리더가 지정한 기간 동안 시계를 정지시키는 것이지만, 이 간단한 해결책도 덜 심각하지만 문제를 일으킬 수 있다.사소한 보정의 경우 대부분의 시스템은 시계를 느리게 하여 보정을 장기간에 걸쳐 적용한다.

종종 주어진 허용오차 외의 값으로 시계가 다른 클라이언트는 결과를 평균화할 때 무시된다.이것은 하나의 잘못된 시계로 인해 전체 시스템 시간이 급격히 왜곡되는 것을 방지한다.

참조