Synchronization

Synchronization Clock

6.1 Clock Synchronization Physical Clocks Logical Clocks Vector Clocks

6.1.1 Physical Clocks (1) 데이터 전달/요청에 대한 순서가 아닌 정확한 시간이 필요할 때가 있음 해결 방안 협정 표준시,Universal Coordinated Time (UTC) Cesium 133 원소의 초당 전이 시간에 기초하여 시간을 구함 현재는, 50 cesium-clock의 평균값을 실제 시간으로 사용 매일의 마지막 시간은 61초(윤초) 로 하여 시간을 조정 UTS는 단파 라디오와 위성을 이용하여 broadcasting되며 위성의 UTC는 +-0.5ms 의 오차 범위를 가짐

6.1.1 Physical Clocks (2)

6.1.1 Physical Clocks (3) 문제 점 기본 원리 UTC를 받아서 시간을 구하는 분산 시스템이 있을 때 시간을 각 머신들에게 배포해야 함 기본 원리 각 머신들은 timer를 가지고 있어서 매 초마다 H 횟수 만큼 interrupt를 발생 시킴 머신 (p)의 clock timer interrupt마다 tick을 발생 Cp(t) (t:UTC) 머신(P), Cp(t) = t라면 이상적인 경우가 될 것임 dC/dt = 1

6.1.1 Physical Clocks (4)

6.1.2 Global Positioning System GPS 정보 이용의 부작용으로 시간 정보를 얻을 수 있음 GPS 위성으로 부터 받는 시간이 정확하고 동기화 되어 있다면 신호를 받을 때 마다 시간을 조정하면 됨 Computing a position in a two-dimensional space

6.1.3 Clock Synchronization algorithm (1) Clock synchronization principles 모든 기계들은 정확한 시간을 얻기 위해서 적어도 매 시간 마다 time server에게 시간을 요청함 다음의 값들을 고려해야 함 Round trip delay Interrupt handling Processing incoming message Time server가 주기적으로 모든 머신을 검사하고 평균값을 계산하여 각 머신들에게 현재 시간으로 부터 상대적으로 정정할 값을 알려줌

6.1.3 Clock Synchronization algorithm (1) Network Time Protocol 개요 인터넷을 통해 컴퓨터 시각을 기준 클락원 (reference clock)에 동기시키는 프로토콜 네트워크 상에 분산된 시각 서버와 크라이언트간에 시각 동기화에 사용 정확도 유지 클락 시간을 동기화 하기 위해서 UTC를 사용 UTC에 비교하여 수 밀리초 이하의 정확도를 유지할 수 있음 (1초 ~ 50ms) 사용 포트 : UDP, 서버 123, 클라이언트 1023 이상 메시지 구성 : 64비트의 timestamp 네트워크 지연에 따른 오류 교정 : 4개의 timestamp를 사용

6.1.3 Clock Synchronization algorithm (2) The Berkeley Algorithm The time deamon tells everyone how to adjust their time The machines answer The time deamon asks all the other machines for their clock values

The Happened-before relationship 같은 프로세스 내에 두 개의 사건 a와 b가 발생하고, a 가 b 보다 앞서면 a  b 만약 a가 메시지 전송이고 b가 메시지 수신이라면 위의 전이관계에 놓임 a  b and b  c then a  c

Logical clocks (1) Question How do we maintain a global view on the system’s behavior that is consistent with the happened-before relation?

Logical clocks (2) Question Solution How do we maintain a global view on the system’s behavior that is consistent with the happened-before relation? Solution Attach a timestamp C(e) to each event e, satisfying the following properties: P1: If a and b are two events in the same process, and a  b, then we demand that C(a) < C(b) P2: If a corresponds to sending a message m, and b to the receipt of that message, then also C(a) < c(b)

Logical clocks (3) Question Solution Problem How do we maintain a global view on the system’s behavior that is consistent with the happened-before relation? Solution Attach a timestamp C(e) to each event e, satisfying the following properties: P1: If a and b are two events in the same process, and a  b, then we demand that C(a) < C(b) P2: If a corresponds to sending a message m, and b to the receipt of that message, then also C(a) < c(b) Problem How to attach a timestamp to an event when there’s no global clock  maintain a consistent set of a logical clocks, one per process

Logical clocks (4) Three processes, each with its own clock. The clocks run at different rates. Lamport’s algorithm correct the clocks

Logical clocks (5) The positioning of Lamport’s logical clocks in distributed systems

Logical clocks (6) Totally ordered multicast Problem 복제 데이터 베이스에 갱신이 항상 어디에서든지 같은 순서로 이루어짐을 보장할 필요가 있음 P1 add $100 to an account (initial value: $1000) P2 increments account by 1% There are two prelicas 10만원 입금 이자 지급 100만원 잔고 Updating a replicated database and leaving it in an inconsistent state

Logical clocks (7) Solution Process Pi sends timestamped message msgi to all others. The message itself is put in a local queuei Any incoming message a Pj is queued in queuej, according to its timestamp, and acknowledged to every other process. Pj passes a message msgi to its application if: msgi is at the head of queuej For each process Pk, there is a message msgk in queuej We are assuming that communication is reliable and FIFO ordered.

Vector clocks (1) Lamport’s의 clock은 다음의 사항을 보장하지 않음 If C(a) < C(b) that a casually preceded b Event a: m1 is received at T=16 Event b: m2 is send at T = 20 We cannot conclude that a casually precedes b Concurrent message transmission using logical clocks

Vector clocks (1) 프로세스 Pi는 VCi[1…n]는 갖음 Pi가 메시지 m을 보낼 때 VCi[j]: 프로세스 Pj 에서 발생한 event의 숫자 Pi가 메시지 m을 보낼 때 VCi[i]++, VCi 를 m과 함께 vector stamp vt(m)으로 보냄 메시지가 도착할 때 수신자는 Pi 의 timestamp를 알 수 있게 됨 Pj가 Pi로 부터 받은 메시지 m을 배달할 때 VCj[k] = max{VCj[k], ts(m)[k]} VCj[j]++;

Vector Clocks (2) Vector clocks are constructed by letting each process Pi maintain a vector VCi with the following two properties: VCi [ i ] is the number of events that have occurred so far at Pi. In other words, VCi [ i ] is the local logical clock at process Pi . If VCi [ j ] = k then Pi knows that k events have occurred at Pj. It is thus Pi’s knowledge of the local time at Pj .

Vector Clocks (3) Steps carried out to accomplish property 2 of previous slide: Before executing an event Pi executes VCi [ i ] ← VCi [i ] + 1. When process Pi sends a message m to Pj, it sets m’s (vector) timestamp ts (m) equal to VCi after having executed the previous step. Upon the receipt of a message m, process Pj adjusts its own vector by setting VCj [k ] ← max{VCj [k ], ts (m)[k ]} for each k, after which it executes the first step and delivers the message to the application.

Enforcing causal communication. VC2 = [0,2,2], ts(m)=[1,3,0] from P0 P2의 정보는

Mutual Exclusion 다수의 프로세스들이 어떤 자원에 배타적으로 접근하고자 할 때 Via a centralized server Completely decentralized, using a peer-to-peer system. Completely distributed, with no topology imposed. Completely distributed along a (logical) ring.

Mutual Exclusion A Centralized Algorithm (1) Figure 6-14. (c) When process 1 releases the resource, it tells the coordinator, which then replies to 2. Process 1 asks the coordinator for permission to access a hared resource. Permission is granted Figure 6-14. (b) Process 2 then asks Permission to access the same resource. The coordinator does not reply

Mutual Exclusion Decentralized 가정 모든 자원은 n회 복제됨 각각의 복제품(replica)는 조정자(coordinator)를 가짐

6.3.4 Distributed Algorithm 메시지를 받는 프로세스는 자원의 공유에 관심이 없음 메시지를 받는 프로세스는 우선 순위가 낮다면 자원을 할당 받기를 기다림 모든 다른 경우 응답은 연기됨 자원 요청을 받은 프로세스의 3가지 상태 메시지를 받은 프로세스가 자원에 접속하지 않거나 접속하기를 원하지 않는다면 메시지를 보낸 프로세스에게 OK 메시지를 되돌려 줌 메시지를 받은 프로세스가 이미 자원에 접속해 있다면 응답하지 않고 요청을 큐에 보관함 메시지를 받은 프로세스가 자원에 접속하기를 원하지만 아직 접속하지 않았다면 메시지의 timestamp를 비교 작은 값의 timestamp가 우선 순위를 갖게 함

A Distributed Algorithm (2) Figure 6-15. (a) Two processes want to access a shared resource at the same moment. Figure 6-15. (b) Process 0 has the lowest timestamp, so it wins. Figure 6-15. (c) When process 0 is done, it sends an OK also, so 2 can now go ahead.

6.5 Election Algorithm 많은 분산 시스템들은 어떤 한 프로세스가 중재자(coordinator)로 동작할 필요가 있음 동적으로 특별한 기능을 하는 프로세스를 선택할 것인가? 대부분의 많은 시스템은 수동으로 중재자를 선정 집중 제어  single point failure 중재자가 동적으로 선택된다면?

Election Algorithms The Bully Algorithm P sends an ELECTION message to all processes with higher numbers. If no one responds, P wins the election and becomes coordinator. If one of the higher-ups answers, it takes over. P’s job is done.

The Bully Algorithm (1) P4 holds an election P5,P6 response P4 stop P5,P6 hold an election 이전의 중재자 P7 crash (a) P4가 이를 인지  send election message higher P(5,6,7) (b) P5,P6  send OK to P4 (c) P5  send P(6,7), P6  send P(7)

The Bully Algorithm (2) P6 tells 5 to stop P6 wins and tells every one