1. Clock Synchronization

1-1. Physical Clocks

Timer: 높은 진동수의 진동자 (quartz crystal)

하나의 컴퓨터라면 각각의 프로세스는 같은 클락을 사용하기에 문제가 되지 않는다.

하지만 네트워크 상에서는 클락이 다를것이기 때문에 시간의 오차(clock skew)가 존재한다. 클락은 아주 미세하지만 다른 속도(rate)로 왕복운동(oscillate)한다.

이 때 두 가지 문제가 있는데,

1. 서로 어떻게 동기화 할 것인가?

2. 다수의 클락과 실제 시간을 어떻게 동기화 할 것인가?

간단히 실제 시간을 알고 싶을 때

Universal Coordinated Time (UTC): 인공 위성은 각자의 원자 시계를 가지고 있다. UTC는 GPS 위성과 동기화되어 시간을 방송한다.

1-2. GPS

Global Positioning System

인공 위성 기반 분산 시스템

31개의 인공 위성은 대략 20,000km 높이의 궤도를 돌고있다.

각각의 인공위성은 3개의 원자 시계를 가지고 있다.(매우 정확함)

메시지를 지속적으로 방송한다

• 위치(position)
• 타임 스탬프

Time-of-Arribal (ToA)

인공 위성으로부터 GPS receiver까지의 거리는 어떻게 구할까?

신호를 보냈을 때 시간과 받았을 때 시간차를 이용해 거리를 구할 수 있다.

• 신호의 속도 c: 빛의 속도 (3x10^8m/s)
• 인공 위성에서의 타임 스탬프: Ti
• GPS receiver 에서 받았을 때 타임 스탬프: Tnow
• 인공위성 i 에서부터 여기까지의 거리
  • di=c * (Tnow-Ti)

Trilatertation

3개의 인공위치의 위치를 알고 타임스탬프를 안다면 우리의 실제 위치를 구할 수 있다.

• 문제점: 모든 시계가 정확하고 동기화되어 있다는 가정이 필요하다.
  • receiver의 시계는 보통 위성과 동기화 되어있지 않다.
  • 신호가 receiver에 도달하는데 시간이 걸린다.
  • 해결방법: Unsynchronized clock at receiver

Unsynchronized clock at receiver

Δdelay i= ( Tnow + Δr ) − Ti= ( Tnow − Ti) + Δr

Δr: receiver의 clock skew (아직 모름)

Ti: 인공위성 i에서의 타임 스탬프

c * Δdelay i (정확한 거리) = c( Tnow − Ti) + cΔr (clock skew로 인해 잘못 구한 거리)

c: 빛의 속도

즉, 정확한 위치를 구하기 위해서는 오차를 빼줘야한다.

di=c Δdelay Δdelay i− c Δr =  `sqrt(a)`  (a: (xi−xr)2+(yi−yr)2)

이 때 , xr, yr은 receiver의 2D 좌표이다. (아직 모름)

3개의 인공위성: Trilateration을 이용해 pinpoint (x,y)를 특정하여 receiver의 정확한 시각을 구할 수 있다.

4개의 인공위성: clock skew를 구하기 위한 식을 하나 더 가져올 수 잇다.

1-3. Clock Synchronization Algorithms

지상에 있는 서버가 정확한 시간을 알려줘 동기화 하는 방식

NTP(Network Time Protocol)

timer server로 부터 클라이언트가 현재 시간을 가져온다.

• Timer server는 원자 시계 등을 통해 정확한 시계를 가지고 있다.
• 문제점: propogation delay (서버에서 클라이언트로 전송될 때 걸리는 시간)
• 클라이언트가 아는 정보: 요청 send(T1)/receive(T2), 응답 요청 send(T3)/receive(T4)

A 라는 시계가 B 시계보다 θ만큼 느릴때  CB(t) = CA(t) + θ 가 성립하며 양 측을 오가는 propogation delay는 동일하다.

T2 – (T 1+ θ) = (T 4+ θ) -T3

따라서 clock skew θ = [(T 2-T1) + (T 3– T4)]/2

Review Question 추가 필요

2. Logical Clocks

Lamport's Logical Clocks

Happen-Before (HB) Relation

내용 추가 필요

3. Distributed Mutual Exclusion

Distributed Mutual Exclusion

3-1. Centralized Algorithm

Coordinator가 각각의 프로세서 시스템에게 뭘 해야할지 지시함. (coordinator는 election algorithm으로 결정)

Step1: 프로세스1이 coordinator에게 공유된 리소스에 접근할 수 있을지 허락을 구한다. queue가 비었기 때문에 승인된다.

Step2: 프로세스2가 같은 리소스에 접근할 수 있는지 물어본다. coordinator는 답(reply)를 보내지 않음. (다른 방법으로는 사용하지 못한다(no)는 답을 보낼 수 있다. 이 경우, 기다리라는 건지 single point failure인지 구분하여 해결할 수 있음.)

Step3: 프로세스1이 리소스를 다 쓰고 해제하면 coordinator에게 말해주고, 이 때 프로세스2는 써도 된다는 답을 받게 된다.

• 장점: ME(mutual exclusion) 보장, 공평하다 (no starvation), 구현이 쉽다.
• 단점: single-point failure(coordinator가 죽어버린 경우, permission이 거절될 경우),  coordinator의 퍼포먼스가 병목(bottleneck)될 수 있다. 
• ME entry/exit 당 메시지 수 : 3 (request/OK/release)
• entry이전의 딜레이: 2 (request/OK)

3-2. Token Ring

1. 링이 만들어지면 프로세스0에게 토큰을 준다.
2. 토큰은 point-to-point 메시지를 통해 링을 돌게된다.
3. 프로세스가 CS(critical section)에 입장하고 싶다면 토큰을 가질 때 까지 기다린다. 사용할 땐 토큰을 가지고 있다가 다 썼으면 토큰을 패스한다.

• Mutual Exclusion? 지켜진다.
• Starvation? 발생하지 않는다. 언젠가 토큰을 가질 수 있게되는 구조이기 때문
• Lost tocken? 여기서 토큰이란, 특수한 토큰인데 전달 과정에서 잃어버리게 된다면 어떤 프로세스가 토큰을 새로 생성해야한다는 문제가 발생한다.

Token-based

Token: 프로세스 사이를 넘나드는 특수한 메시지

하나의 토큰만 이용할 수 있다.

토큰을 가진 프로세스만이 공유된 리소스에 접근 가능하다.

장점: starvation, deadlocks 발생하지 않음

단점: 토큰을 잃어버리게 되면 새로 토큰을 생성해야 한다.

ME entry/exit 당 메시지 수: 1 에서 무한대 (예시의 경우 최대 8)

entry 딜레이: 0(마침 내가 들고 있을 때) 에서 n-1(방금 전에 지나갔을 때)

평균 딜레이: (n-1)/2

3-3. Distributed Algorithm

모든 프로세스가 다 coordinator라고 할 수 있다. 모든 프로세스가 허락 해줘야 사용할 수 있음.

1. 프로세스가 리소스를 사용하길 원할 때, 리소스의 이름, 해당 프로세스의 넘버, 현재 logical time를 쓴 메시지를 만든다.
2. 모든 프로세스에게 메시지를 보내고 모든 프로세스로부터 OK 메시지를 받을 때 까지 기다린다.
3. 각 프로세스가 메시지를 받았을 때:
   1. receiver 프로세스가 리소스에 접근하지도 않고, 접근하려고 시도하지도 않을 때 OK 메시지를 sender 프로세스에게 보낸다. "너 그 리소스 써도된다!"
   2. receiver 프로세스가 리소스를 이미 가지고 있을 때, 답(reply)를 보내지 않는다. 그 대신, 그 프로세스의 큐에 리퀘스트를 쌓는다. "지금 쓰고 있기 때문에, 일이 다 끝나면 OK 라고 알려줄게!"
   3. receiver 프로세스도 해당 리소스를 사용하고 싶지만 아직 사용하고있지 않을 경우, 메시지에 적힌 타임스탬프를 비교해서 더 빨리 온 것(수가 적은 쪽)을 보낸다. (타임스탬프는 logical time이라 정확하진 않지만 사용에 무리없다.)
4. 허락을 얻기 위한 요청 메시지를 보낸 후에는 모든 프로세스로부터 허락(OK 메시지)받을 때 까지 기다린다. 허락을 받은 후에는 리소스를 사용하고 다 사용하고 난 후에는 OK 메시지를 큐에 있는 모든 프로세스에게 보낸다. 

Centralized Algorithm	Distributed Algorithm
Single point of failure	n points of failure : n개 중에서 아무나 하나가 문제가 생기면 동작을 안한다.(;;) n개의 노드 중 하나만 크래쉬가 나도 ok message를 보내지 못하고 모든 리소스가 block된다. centralized algorithm에 비해 최소 n 배의 메시지가 필요하다.(계속 실패할 경우)

ME entry/exit 당 메시지 수: 2(n-1)

entry 딜레이: 2(n-1)

3-4. Decentralized(Voting) Algorithm

1. 각각의 리소스는 n개의 coordinator를 갖는다.
2. 클라이언트는 n개의 coordinator에게 리퀘스트를 보내 허락을 구한다.
   1. 만일 m(>n/2)개의 coordinator로부터 승인(grant)으로 받으면 리소스를 얻을 수 있다.
   2. 과반수 이하일 경우 승인은 거절(deny)된다. (쓰고 싶으면 또 요청해야함)
3. Voting algorithm
   1. 클라이언트는 n개의 리퀘스트를 보내고 n개의 응답을 받는다. (승인 혹은 거절)
   2. 클라이언트는 리소스를 다 사용하고 나서 n 개의 release 메시지를 보낸다.

Reliability: coordinator가 fail 되어도 상관없이 다른 coordinator가 아직 동작하고 있기 때문에 역할을 대신해줄 수 있다.

단점: 많은 노드가 같은 리소스에 접근하려할 때, 어떤 노드도 허락을 얻지 못할 수 있다. (이 경우, 2N 개의 메시지가 낭비된다.), 그러면 노드들이 계속 리소스를 얻지 못하므로 starvation이 발생함.

3-5. Comparision of four ME algorithms

Algorithm	Total message per ME entry/exit	Delay before entry (in message times)	Problems
Centralized	3	2	Coordinator crash (single-point failure)
Decentralized (m coordinators, k failures)	2mk(failure)+m(permission)	2mk	Starvation
Distributed (N nodes)	2(N-1)	2(N-1)	N points of failure
Token Ring (N nodes)	1 to infinite	0 to N-1	Lost token, process crash

4. Election Algorithms

4-1. The Bully Algorithm

프로세스 중에서 coordinator를 선정하는 방법

1. 미리 정해진 순서 (initial state)
2. 현재 coordinator가 fail 일때 등

참고: 많은 시스템에서 coordinator는 수기로 정해진다.(서버 파일) 이 경우 centalied solution(single point of failure의 솔루션) 이 될 수 있다.

각각의 프로세스는 우선순위(weight)가 있다. 높은 우선순위를 가진 프로세스가 coordinator로 선출된다.

어떻게 우선순위 높은 프로세스를 찾을 수 있을까?

어떤 프로세스 k 가 coordinator가 제 역할을 못한다고 판단하면, election message를 다른 프로세스들에게 보낸다.

Election by Bullying

Bully: 큰 놈만 맨날 이겨서...

1. Pk : ELECTION 메시지 전송. 이 때, k 보다 높은 우선 순위를 가진 프로세스에게 보낸다. (Pk+1, Pk+2, ... , Pn-1)
2. 아무에게도 응답에 오지 않으면, Pk의 우선순위가 가장 높다는 말이기 때문에 coordinator가 된다. (더 높은 우선순위의 프로세스는 크래쉬 등의 이유로 될 수 없나보다.)
3. 응답이 온다면 Pk의 일은 끝난다.

(a) 프로세스4는 7번에 문제가 생겼음을 발견하고 ELECTION 메시지를 보낸다. 4보다 우선순위가 높은 5,6,7에게 전송

(b) 프로세스5와 프로세스6는 프로세스4에게 OK 메시지를 보낸다. "넌 안해도 된다!" 이 때, 프로세스 7은 크래쉬되었기 때문에 OK 메시지를 보낼 수 없다.

프로세스5는 프로세스6,7에게 ELECTION 메시지를 보내 프로세스6에게 응답을 받음.

프로세스6은 프로세스7에게 ELECTION 메시지를 보내지면 응답 받지 못하므로 coordinator가 된다.

(c) coordinator가 선출 된 후 Coordinator 메시지를 다른 프로세스에게 보낸다. (?? 이 경우 브로드캐스트 아니면 우선순위가 낮은 노드에게만?)

• 정리

1. heavy 프로세스가 lighter 프로세스에게 election 메시지를 받으면 Ok 메시지를 보낸다.( lighter는 race에서 제외됨)
2. 프로세스가 Ok 메시지를 받지 못하면 coordinator가 되고 다른 프로세스에게 coordinator 메시지를 보낸다.

Review Question 있음