GOOD to GREAT

11.3.2 Cristian's method for synchronizing clocks

간단하게 계산하면 프로세스 P의 지연 시간은

11.3.4 The Network Time Protocol

Cristian's method나 Berkeley algorithm은 인트라넷을 위한 것이다. 

이장에서 다룰 Network Time protocol은 순전히 인터넷위에서의 타임 서비스와 분산환경에서의 타임 프로토콜을 위한 아키텍쳐이다.

NTP의 중요한 디자인 이념은 다음을 따른다.

인터넷 전반에 걸쳐서 클라이언트 서비스가 정확히 동기화되게 가능하도록 지원한다.

비록 인터넷 환경은 딜레이가 있지만, NTP는 통계적인 기술들을 이용해서 타이밍 데이터를 필터링하고 타이밍 데이터를 서로다른 서버들로부터 그 퀄리티를 식별해 내게 된다.

11.4 Logical time and logical clocks

어떤 이벤트가 발생했고 이러한 이벤트들의 쌍들에 대해서 정확하게 그 인과관계를 알아내는것은 어렵다. 이것을 지원하기 위한 매커니즘이다.

아래의 직관적인 두가지 포인트에 기반해서 이러한 인과관계를 파악하게 된다.

1) 같은 프로세스에서라면 이벤트들의 순서를 정할 수 있다.

2) 언제든지 발생된 이벤트들에대한 정보를 다른 프로세스들에게로 전송 할 수 있다.

이러한 원리들에 대해서 그림을 보며 이해를 하자.

그림 11.5를 보면 3개의 프로세스들이 정의가 되어 있다. 

여기서 핵심은 모든 이벤트들이 관계가 명확히 파악 되어지는것은 아니다. 

즉, a -> e 인지는 알 수 없다. 왜냐하면 서로 다른 프로세스에서 실행 되어졌기 때문이다. 그리고 그것들 사이에 어떠한 메시지 체인도 없기 때문에 더더욱 알 수가 없다.

우리는 이러한 이벤트들을 순서를 정할 수 없다고 하며 이것을 concurrent 하다고 한다.

그리고 그것을 a || e 라고 기술 한다.

Logical clock:

Lamport는 간단한 numerically에 기반한 이벤트 상관 관계를 기록하는 매커니즘을 개발 했다.

결국, Lamport logical clock은 단조 증가하는 소프트웨어 카운터이다. Lamport logical clock는 physical clock에 대한 정보를 가지고 있을 필요가 없다. 각각의 프로세스 pi들은 그것들이 소유하는 logical clock을 유지하고 있다. Li라고 그것을 부르며, 이것은 Lamport timestamp들에 의해서 적용되어 진다. 

우리는 프로세스 pi에서의 이벤트 e의 타임스탬프를 Li(e) 와 L(e)로 표현한다. 우리의 이 표식은 이벤트 e가 어떤 프로세스에서도 발생할수 있음을 뜻한다.

상관 관게를 기록하기 위해서, 프로세스들은 그들의 logical clock들을 갱신하고 메시지에서의 그들의 logical clock들의 값을 전송 한다. 다음과 같이.

비록 클락이 1씩 증가할지라도, 우리는 선택해 왔다 어떤 positive 값을. 그것은 어떤 이벤트들의 순서 관계에 의한 유도가 쉽게 파악될 수 있다. 

즉,  event e와 e'이 e-> e' => L(e) < L(e') 이다.

주목할 것은, 위 명제의 convers는 참이 아니다. 즉, L(e) < L(e')라고 해서, 우리는 e->e'라고 추론 할수는 없다. 

위 그림은 이전의 그림에 대한 logical clock들에 대한 그림으로 전환한 것이다. 

각각의 프로세스들 p1,p2,p3들은 초기 0의 logical clock을 가지게 된다.

The clock values given are those immediately after the event to which they are adjacent.

Totally ordered logical clocks

모든 페어들에 대해서 구별 가능하게 한다. 프로세스 구분자를 사용해서

즉, local Time stamp는 T이다.

(T1,p1) < (T2,p2) if either T1 < T2 or T1 = T2 and p1 < p2

Vector clocks ◇

vector clock은 Lamport timestamp가 가지는 단점을 극복하기 위해서 개발 되어 졌다.

이 단점이란 다음과 같다. 

의 경우 우리는 e와 e'의 관게를 결정 할 수 없다.

왜냐하면, 논리적인 클란은 물리적인 클락과 관계가없고 서로다른 프로세스에서 어떠한 상관 관계도 알 수 없기 때문이다.

N개의 프로세스에서의 벡터 클락은 N integer들의 array 이다. 각각의 프로세스들은 그것들의 vector clock Vi를 유지하게 된다. 이것은 local event들의 타임스탬프를 사용한다. Lamport 타임스탬프와 같이, 프로세스들은 벡터 타임스탬프들을 메시지위에 실어서 다른 프로세스로 보내게 된다. 그리고 다음과 같은 규칙에 의해서 그것을 갱신하게 된다.

아래의 그림14,7을 해석하면 아래와 같다.

V(a) < V(f)를 나타냄을 알 수 있다. 이것은 a->f라는것을 유도해 낼 수 있다. 비슷하게 우리는 2개의 이벤트가 concurrent할때 2개의 타임스탬프를 비교해서 이것을 구분해 낼 수 있다.

For example, that c ||e can be seen from the facts that neither V(c) <=  V(e) nor V(e) <= V(c).

벡터 타임 스탬프의 단점은 , 프로세스의 수 N에 비례해서 storage의 크기와 message payload가 늘어난다는 점이다.