Time, Clocks, and the Ordering of Events in a Distributed System (정리)

Time, Clocks, and the Ordering of Events in a Distributed System

Leslie Lamport

Massachusetts Computer Associates, Inc.

July 1978 Volume 21 Number 7

"happened before" 

"a partial ordering"

"totally ordering"

이 페이퍼는 헤픈 비포의 개념과 파셔 오더링 그리고 현실적으로 실현하기 힘든

토털 오더링에 대해 서술하고 있다.

먼저 DS은 시간이 기초가 되는 기술이며

3:15분의 이벤트와 3:16의 이벤트가 있다면 먼저 시각 15분에 일어난

이벤트를 처리할 것이다. 

이것은 우리 일상에서 쉽게 찾을 수 있는 일이다.

비행기 예약 시스템을 예를 들면 비행기 좌석이 모두 차기 전에

우리가 예약을 해야만 좌석을 받을 수 있는 것과 같은 이야기이다.

DS의 존재는 많은 프로세스들과 메세지 교환을 통해 이루어지는 

일련의 커뮤니케이션 과정이다.

ARPA NET 또한 하나의 DS의 종류일 것이다.

여기에서 우리는 멀티 프로세싱되는 환경의

최적안을 고려해야만 한다.

The partial Ordering

"There is still the problem that such physical time."

 We will therefore define the "happened before" relation without using physical clocks.

결국 물리적인 시간을 통해 모든 DS를 관리하는 것은 불가능한다.

그렇기 때문에 우리는 "happened before" 관계를 이용하여 파셔오더링을 실현하겠다.

정의(Definition)

(1) If a and b are events in the same process and a comes before b, then a->b

(2) If a is the sending of a message by one process and b is the receipt of the same message  by another process then a->b

(3) If a -> b and b - > then a -> c

이러한 정의에서 분리된 a , b가  a->b가 아니면 b->a가 아니다.

즉 한 프로세스 안에서 a1 a2로 진행된 프로세스라면 a1->a2가 될 것이고,

분리되니 프로세스라고 하더라도 a와 b사이에 메세지 파싱이 있었다면, a->b

또한 이것을 유추했을 때 a1와 b1사이에서 또 b2와 c1사이에 순차적으로 메세지 파싱이 있었다면,

a1->c1가 가능하다는 것이다.

Logical Clock

간단히 설명하면, 다수의 프로세스를 관리 가능한 하나의 시계가 있거나

동기화를 통해 다른 시계 x1 , y1 사이에서 타임스템프를 통해 서로 관리를 하는 것이다.

즉 a 프로세스에서 시간 a1 a2 a3 a4 an b 프로세스에서 시간 b1 b2 b3 b4 bn이 존재하면,

a5가 진행될 때 b프로세스에서는 b1밖에 진행하지 못하였지만

서로의 DS를 실현하기 위해

a5를 b프로세스로 전송할 때 타임스템프를 같이 전송하여

b의 프로세스에서는 a5보다 큰 거나 같은 값으로 변환하여 시스템 간의 분산 처리를 가능하게 하는 것이다.

Ordering the Events Totally

현실적인 모델으로 사용 불가능 함

만약 실현되려면 5가지 가정을 만족해야 함.

1) To request the resource, process Pi sends the message Tm:Pi requests resource toe every other process~

2) When process Pj receives the message Tm:Pi requests resource~

3) To release the resource message from its request queue and sends~

4) When process Pj receives a Pi releases resource message~

5) Process Pi is granted the resource when the following two conditions are satisfied~

Anomalous Behavior

-타인의 해킹이나 불법적인 간섭으로 인해 발생하는 현상에 대해 서술 

Physical Clocks

어쩔 수 없이 불가능 하나, 실제 사용하려면, 두 가지 가정을 지켜야 한다.

PC1. There exists a constant k<<1 such that for all i : |dCi(t)/dt-1| < k

시간 단위의 한번 이동하는 간격이 모두 동일 해야 한다. [Resolution]

PC2: For all i,j : |Ci(t)j - Cj(t)| < ε [약 10^-6]

시간 사이의 오차가 약 100분에 1초로 적용된다면 사용 가능 하다.