논리적 클록과 물리적 클록

논리적 클록은 실제 시간에 관계없이 인과 관계에 따라 이벤트를 정렬하는 반면, 물리적 클록 동기화는 드리프트에도 불구하고 개별 기계의 실시간 클록을 가깝게 유지합니다.

Definition

논리적 클록은 각 이벤트에 대해 각 프로세스에서 단조롭게 증가하고 통신을 통해 증가하는 정수 타임스탬프를 할당하여 인과적 순서를 포착합니다. 물리적 클록 동기화는 기계의 하드웨어 클록을 조정하여 대략 동일한 실제 시간을 읽도록 하는 과정입니다.

Scope

이 주제는 램포트의 논리적(스칼라) 클록과 이들이 존중하는 선행 관계(happened-before relation), 논리적 타임스탬프에서 전체 순서를 구성하는 방법, 그리고 물리적 클록 동기화—드리프트 제한, 오프셋 추정을 위한 타임스탬프 교환, 그리고 실제로 사용되는 알고리즘(크리스티안 방식, 버클리 알고리즘, NTP)을 다룹니다. 또한 인과적 논리적 시간이 충분한 경우와 실제 시간이 진정으로 필요한 경우를 대조합니다.

Core questions

• 선행 관계(happened-before relation)를 존중하도록 타임스탬프를 어떻게 할당할 수 있는가?
• 논리적 클록으로부터 이벤트에 대한 일관된 전체 순서는 어떻게 구축되는가?
• 가변적인 네트워크 지연과 드리프트를 고려할 때 물리적 클록을 얼마나 가깝게 동기화할 수 있는가?

Key theories

램포트 논리적 클록

각 프로세스는 모든 이벤트에서 증가하고 메시지에 실려 전달되는 카운터를 유지합니다. 결과적인 타임스탬프는 선행 관계를 존중하며, 프로세스 식별자로 동점을 해결하면 인과 관계와 일치하는 전체 순서가 생성됩니다.

확률적 및 왕복 동기화

크리스티안 방식은 왕복 시간을 측정하고 대칭 지연을 가정하여 원격 클록을 추정하며, 네트워크를 통해 달성할 수 있는 동기화 오류에 대한 확률적 경계를 제공합니다.

네트워크 타임 프로토콜

NTP는 시간 서버를 계층적 구조로 조직하고 반복적인 오프셋 측정의 통계적 필터링을 사용하여 인터넷 전반의 클록을 밀리초 이내로 조정합니다.

Clinical relevance

논리적 클록은 벽시계 시간을 신뢰하지 않고 복제된 저장소와 메시지 큐에서 작업을 정렬하는 반면, 물리적 동기화는 타임스탬프 순서 데이터베이스, 분산 추적, 그리고 제한된 클록 오류에 의존하는 보안 프로토콜의 기반이 됩니다.

History

램포트의 1978년 논리적 클록 논문은 분산 시스템의 시간을 물리적 개념이 아닌 인과적 개념으로 재구성했습니다. 동시에 크리스티안과 다른 연구자들은 확률적 동기화를 개발했으며, 밀스의 NTP는 인터넷 클록을 정렬하는 표준 메커니즘이 되었습니다.

Debates

작업 순서 지정을 위한 논리적 시간 대 물리적 시간

논리적 클록은 하드웨어 클록을 신뢰하지 않고도 인과적 정확성을 보장하지만, 이벤트를 실제 시간과 관련시킬 수 없습니다. 물리적 클록은 드리프트가 메시지 지연을 초과할 때 잘못된 순서 지정의 위험을 감수하면서 실시간 추론을 가능하게 하므로 하이브리드 접근 방식이 필요합니다.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

a의 램포트 타임스탬프가 b보다 작다면, a가 b보다 먼저 발생했습니까?

반드시 그렇지는 않습니다. 더 작은 타임스탬프는 선행 관계와 일치하지만 그것을 의미하지는 않습니다. 왜냐하면 동시 이벤트가 순서가 있는 타임스탬프를 받을 수 있기 때문입니다. 인과 관계를 정확하게 결정하려면 스칼라 논리적 클록이 아닌 벡터 클록이 필요합니다.