[Cloud computing] 8. Logical Clock

Reference

1. Thomas Erl_ Zaigham Mahmood_ Ricardo Puttini - Cloud Computing_ Concepts, Technology & Architecture-Prentice Hall,

2. Cloud Computing class by Professor Heonchang-Yu of the Department of Computer Science and Engineering at Korea University

3. Time, Clocks, and the Ordering of Events in a Distributed System - Leslie Lamport

 

Concepts of Time and Clocks

• 한 system 내에서 틀린 clock 값이더라도 상관없이 ordering이 중요하다!
• 서로 다른 system 에서는 dependency가 있을 경우 clock값을 맞춰야 한다. (독립적인 event는 상관없음)
• 하지만 서로 다른 system 내에서 clock값을 맞추는 것은 불가능하다. order를 맞춰야 한다. ⇒ No Global Clock in DS
• computer clock을 대략적으로 동기화하고, 이벤트 발생 시점을 측정하지 않고 이벤트 순서를 정의하기 위해서 logical clock, vector clock을 사용한다.

Clock

• OS는 노드의 hardware clock H(t)을 읽는다.
• software clock : C(t) = aH(t) + b
• clock은 완전히 정확하지 안핟.
• clock resolution: clock 값 업데이트 간격

Clock skew and clock drift

• computer clock은 완전히 일치하지 않는다.
• Skew : 두 clock의 판독값 차이
• clock drift : 서로 다른 속도로 시간을 카운트하는 것
• clock drift rate : 기준 clock에 의해 측정된 시간 단위 당 clock과 nominal perfect reference clock간 offset 변화

---

Synchronizaing Physical Clocks

External synchronization

• process의 clock(Ci)을 신뢰할 수 있는 외부 시간(S)과 동기화 시킨다.
• |S(t) - Ci(t) | < D, i = 1, 2, … N
• D- bound

Internal synchronization

• 한 쌍의 computer clock을 서로 동기화 시킨다.
• | Ci(t) - Cj(t) | < D for i = 1, 2, … N
• clock Ci, Cj는 D 내에서 일치한다.
• 내부적으로 동기화된 clock은 반드시 외부적으로 동기화할 필요 없다.

Internal synchronization in a synchronous system

• 1개의 process가 time t에서의 local clock을 다른 process로 전송한다.
• 수신 process에서는 clock = t + T_trans 으로 설정한다. T_trans: m을 송신하는 데 걸리는 식나
• 메시지 전송 시간의 불확실성: u = max - min (전송 시간)
• 수신자가 clock = t + min으로 설정하면 clock skew 는 u만큼 될 수 있다.
• clock = t + (max+ min)/2 로 설정하면 skew는 최대 u/2가 된다.
• N개의 clock을 동기화할 때 clock skew로 얻을 수 있는 최적의 bound는 u(1-1/N)이다.

Probabilistic clock synchronization

• 프로세스 p는 메시지 mr 내의 시각을 요구하고, 메시지 mt 내의 시간값 t를 S로부터 수신한다.
• 프로세스 p는 mr 요청 전송에 소요된 총 round-trip time T_round 을 기록하고, mt * p set들이 그들의 clock을 t + T_round /2 으로 설정했다는 응답을 받는다.

• 정확도는 +-(T_round/2 - min) 이다.
• 응답 메시지 mt가 도착할 때까지의 시간 범위는 [t + min, t + T_round - min ]

---

Logical time and logical clocks

• 분산 시스템 전체에서 clock을 완벽하게 동기화할 수 없기 때문에 물리적인 시간을 사용하여 임의의 이벤트 쌍의 순서를 알아낼 수 없다.

For ordering

• 두 event가 동일한 process에서 발생하면, pi가 관측하는 순서대로 발생한 것이다.
• process 간 메시지가 전송될 때마다, 전송 event는 메시지를 수신하기 전에 발생한다.

Happended-before relation (→)

Logical clocks

• 단조롭게 증가하는 software counter

Vector clocks

+) Total ordering

• c1 : request → allocation → release
• c2 : request 발생 순서대로 자원 할당
• c3 : 모든 request는 손실없이 결국 도착한다.