[Cloud computing] 10. Coordination

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. DIstributed Systems: Concepts and Design (5th Ed), PEARSON, 2001

 

Introduction

non-distributed system에서의 Concurrency control을 먼저 정리하자.

• 공유 변수가 있으면, race condition이 발생하여 synchronization problem이 발생
• semaphore와 monitor를 사용하여 해결

마찬가지로 DS에서도 특정 자원에 대해 동시 접근을 방지해야 한다. 독립적인 process간 동등하게 맞춰야 하는 action은 다음과 같다.

1. Failure detection - peer의 생존 여부 확인
2. Mutual exclusion - 상호배제
3. Election - master 정하기
4. Consensus in presence of faults (byzantine problem)

Failure assumptions and failure detectors

• Failure detector: 특정 process에게 fail 여부를 질의하는 service
• Unreliable failure detector
  • unsuspected: 최근 process가 fail하지 않았다는 증거를 접수
  • suspected: 최근 process가 fail했다는 증거를 접수
• unreliable failure detector 구현: 각 process는 주기적으로 살아있음을 전송하고, 특정 시간 D가 지나도 못받으면 그 process에 문제가 생겼다고 인지한다.

---

Distributed mutual exclusion

일반적인 OS 내에서가 아닌 DS 환경에서 mutual exclusion이 일어나야 함

Algorithms for mutual exclusion

요구사항

1. safety - 반드시 Critical Section(이하 CS) 내에 한 process만 존재한다.
2. liveness - CS에 들어가고 나가는 Request는 결국은 성공해야 한다. (progress와 유사) → deadlock이나 starvation이 걸리지 않도록 한다.
3. ordering(→) - 먼저 요청한 process를 먼저 처리한다. logical clock을 사용한다.

mutual exclusion algorithm 평가 기준

1. Bandwidth - operation 당 처리하는 message 개수
2. Client delay
3. Throughput - CS에 들어갈 수 있는 process 개수

가정

1. 네트워크는 reliable → 모든 메시지는 목적지에 제 시간내에 돡
2. 비동기 네트워크 → message passing에 오랜 시간 소요 가능
3. process는 언제든 죽을 수 있다.

DS의 상호 배제 프로토콜

1. CS에 진입하기 전에 process는 반드시 다른 process의 허락을 받아야 한다.
2. CS에서 나올 때, process는 다른 process에게 자신이 끝났음을 반드시 알린다.
3. 먼저 요청을 허락받은 process가 먼저 CS에 진입한다.

The Central Server Algorithm

• 중앙 server가 CS 진입에 대한 권한을 grant
  • process는 CS 진입 시 서버에게 요청 후 응답 대기
    • 만일 당시 다른 process들에게 token없다면, server는 즉시 token을 발급한다.
    • 만일 당시 다른 process가 token을 이미 들고 있다면, 응답하지 않은 채 request를 queue에 넣는다.
    • 만약 queue가 꽉 찼다면, 가장 오래된 process를 골라 제거하고 해당 process에게 응답
  • process가 CS를 나갈 때 server에게 message를 전송 후 token을 반납한다.
• liveness 만족: queue에 들어가면 결국은 CS에 진입 가능
• ordering 만족 X: request 발생 시점으로 ordering 한다. logical clock이 아니므로 ordering 보장X
• CS 진입 → request & grant 메시지 2개
• CS 나감 → release 메시지 1개
• fault tolerance 하다.

Ring-Based Algorithm

• N개의 process가 logical ring에 정렬된다.
• token 1개가 한 방향으로만 흘러간다
• CS에 진입할 필요가 없다면 바로 다음으로 token을 넘긴다.
• CS에서 나갈 때 token을 다음으로 넘긴다.
• Safety, liveness 만족 (token 1개가 어디선가 존재하여 한 방향으로 계속 흐름)
• ordering 만족 X
• CS 진입 시 0~N개의 메시지 발생
• CS 나갈 시 1개의 메시지 발생
• delay - 1 ~ N message transmission time

Algorithm using multicast and logical clocks (Ricart and Agrawala)

• CS 진입시 process는 request를 multicast 하고, 모든 process가 응답해야만 진입할 수 있다.
• process state
  • RELEASED : CS 밖
  • WANTED : CS 진입 희망
  • HELD : CS 안
• CS 진입
  • process가 진입 request를 보낼 때, 다른 모든 process가 RELEASED 이면 즉시 응답하여 CS에 진입할 수 있다.
  • 만약 일부가 HELD 라면, 그 process들은 CS 내 작업이 끝날 때까지 응답하지 않는다.
  • 만약 2개 이상의 process가 같은 시간에 요청한다면, 응답을 모두 받은 시간이 더 짧은 process가 들어간다.
  • ⇒ 이때도 만약 동일한 Lamport timestamp를 낳았다면, identifier 순으로 결정한다.
• Safety, Liveness, Ordering 만족
• CS 진입 시 2(N-1) 메시지 발생
• delay - 1 message transmission time

Maekawa’s Voting Algorithm

• process는 peer의 subset에 들어가기 위해서는 permission을 획득해야 한다.
• 각 process에 대해서 Voting set을 만든다.
  • pi ∈Vi
  • Vi ∩ Vj ≠Ø : there is at least one common member of any two voting sets
  • |Vi| = K : to be fair, each process has a voting set of the same size
  • Each process pj is contained in M of the voting sets Vi
• CS 진입
  • pi는 K개의 Vi의 모든 member들에게 request message을 보낸다.(자기 자신도 포함)
  • K개의 모든 reply를 받기 전까지는 CS 진입 불가
  • Vi에 있는 pj가 “HELD 상태가 아니거나”, “이미 응답하지 않았다면” pi의 요청을 받았을 때 즉시 응답한다.
  • 그 외에는 request message를 queue에 넣고 응답하지 않는다.
  • release message를 받았을 때, queue에서 request message를 꺼내서 응답한다.
• CS 나감
  • CS에 나가기 위해서 pi는 K개의 Vi의 모든 member들에게 release message를 보낸다. (자기 자신도 포함)
• safety 만족
• logical clock을 사용하지 않아 ordering 만족 X
• fault tolerance 하다.
  • 앞선 알고리즘은 process의 failure를 허용할 수 없다.
  • Maekawa’s 알고리즘에서는 crashed process가 voting set에 없다면 failure가 다른 process에게 영향을 주지 않는다.
• Deadlock prone
• 

---

Elections

• 어떤 unique process에게 특정 역할을 부여하기 위해 고르는 것

Election algorithm

• participant: election 알고리즘에 참여
• non-participant: 어떠한 election에도 관여 X
• the largest identifier → 당선
• 여러 프로세스가 동시에 선거를 호출하더라도 선출된 프로세스는 고유해야 한다.
• property
  • (E1) safety - 선출된 process는 crash되지 않음
  • (E2) liveness - 선거에 참여한 후에 선출된다.

Ring-based Election Algorithm

• process들이 logical하게 ring에서 순서를 가진 채 존재한다. 한 방향으로 통신한다.
• (1) Initial pahse
  • 모든 process를 non-participant 로 mark
  • process들이 스스로를 participant로 mark 후, 시계 방향으로 election message를 전달
• (2) election message 수신
  • 자신의 identifier와 message의 것과 비교한다.
    • 만약 자신의 것보다 message의 것이 크다면, 해당 message를 앞으로 보내고 스스로를 participant로 지정한다.
    • 만약 자신의 것보다 message의 것이 작고 && 자신이 participant가 아니라면, message의 identifier를 자신의 것으로 교체한 후 앞으로 보낸다.
• (3) 수신된 identifier가 자신의 것인 경우
  • 이 경우, 해당 process의 identifier는 반드시 최대이다. 따라서 coordinator가 된다.
  • coordinator는 스스로를 non-participant로 한번 더 지정하고, elected message를 앞으로 보내서 당선을 알리고 자신의 identifier를 message에 담는다.
• (4) elected message를 수신하는 경우
  • 스스로를 non-participant로 지정하고, elected_i 를 message의 identifier로 지정한다.
  • 자신이 새로운 coordinator가 아니라면 앞으로 메시지를 전달한다.

⇒ 돌아가면서 id가 큰 애가 elect되고, 자기 자신으로 돌아오면 끝난다!

• E1, E2 만족 (elected message는 무조건 한 바퀴를 돌기 때문)
• 성능
  • worst case: 반시계 쪽으로 이웃이 highest identifier를 가졌을 경우 → N-1개의 message가 해당 이웃에게 닿기 위해 필요.
  • elected message가 N번 전송 → 3N-1 message 발생

The Bully Algorithm

• 3가지 message 타입
  • Election: election을 알림
  • Answer: election message의 응답
  • Coordinator: elected process의 id를 알림
• 가정
  • synchronous한 system이다. ⇒ reliable failure detector
  • process failure를 탐지하기위해 timeout 사용 (2T_trans + T_process)
  • 각 process는 어떤 process가 더 높은 id를 갖는지 알고 있다.
• (1) Election phase
  • id가 낮은 process가 높은 id process들에게 election message를 보내서 election을 시작, 이후 응답을 대기한다.
  • 만약 Time T가 지날 때까지 응답이 없다면, 스스로를 coordinator 로 인식하고, 낮은 id를 가진 process들에게 coordinator message 를 보낸다.
  • 그게 아니라면, 새로운 coordinator에게서 coordinator message가 오기를 기다린다.
    • answer 는 왔는데, coordinator message 가 안 오면, 또 다른 election을 시작한다.
  • election message를 받으면, answer 를 응답으로 보내고 election을 시작한다.
• (2) Coordinator phase
  • 자신이 가장 높은 id를 가짐을 알고 있는 process는 id가 낮은 모든 process에게 coordinator message 를 보낸다.
  • 이를 받은 process는 elected_i를 coordinator의 id로 설정한다.
• (3) crashed process를 대체하기 위해서 어떤 process가 시작할 때
  • election을 시작한다.
  • 만약 가장 높은 id를 가진 경우, coordinator가 되고 이를 알린다.
  • 현재 coordinator가 있더라도 경쟁하여 빼앗는다.

⇒ higher id한테만 물어본다. election->answer 받으면 높은 애가 election을 시작한다. timeout을 두어 answer가 올 때까지 시간을 기다리고 아무것도 안 오면 해당 process가 coordinator가 된다.

• E1 만족 - if no process is replaced → 보장 안됨(crash 후 같은 id로 대체될 경우)
• E2 만족 - reliable message 전송을 가정했으므로
• 성능
  • best case → N-2
  • worst case → O(N^2)

---

Consensus and related problems

여기서의 합의란 **분산 시스템 내에서 process들이 동일한 데이터를 공유하는 상태(동기화)**가 되는 것을 의미한다.

Problems of agreement

하나 이상의 프로세스가 값을 제안한 후 값에 동의하는 방법

• mutual exclusion에서 process들은 어떤 process가 CS에 진입하는 것을 동의해야 함
• election에서, process들은 당선된 process를 동의해야 함
• totally ordered multicast에서 process들은 message 전송 순서를 동의해야 함

System model and problem definitions

• N개의 process들이 message passing으로 통신
• 통신은 reliable, process는 fail 가능

 

Definition of the consensus problem

• consensus에 도달하기 위해, 모든 process들은 undecided state에서 시작하고 단일 값 vi를 제시한다.
• 서로 값을 교환하며 통신한다.
• 각 process들은 decision value di를 지정한다. (decided state에 진입)
• consensus 알고리즘 요구사항
  • Termination : 각 correct process들은 decision variable을 결국은 set한다.
  • Agreement : 모든 correct process들의 decision value는 동일하다.
  • Integrity : 모든 correct process들에 대해서 특정 값을 제시한다면, decided state내 process는 그 값과 같은 값을 받아야 함

To solve consensus

• process들을 group으로 묶고, 각 process들이 group 내의 member들에게 reliable한 multicast로 값을 제시한다.
• 각 process들은 N개의 값들을 모을 때까지 대기한다.
• 값들 중 가장 자주 발생하는 값을 반환하는 majority 함수를 평가한다. 없을 경우 특별한 값을 반환한다.
• Termination 만족 - multicast operation
• Agreement, integrity 만족 - majority 와 reliable multicast

특정 process가 crash → detect해야됨

Fault process → 악의적으로 랜덤 값 전송

The byzantine generals problem

적군의 도시를 공격하려는 비잔티움 제국군의 여러 부대가 지리적으로 떨어진 상태에서 각 부대의 장군들이 (중간에 잡힐지도 모르는) 전령을 통해 교신하면서 공격 계획을 함께 세우는 상황을 가정하고 있다.

충직한 장군들은 합의된 규칙을 충실하게 따르며 이 외의 행동은 하지 않는다. 그러나 전체 장군 중 일부는 배신자일 수 있으며, 배신자는 규칙에 얽매이지 않고 마음대로 행동할 수 있다. 이 때 배신자의 존재에도 불구하고 충직한 장군들이 동일한 공격 계획을 세우기 위해서는 충직한 장군들의 수가 얼마나 있어야 하며, 장군들이 어떤 규칙을 따라 교신해야 하는지에 대한 문제가 비잔티움 장군 문제다.

오직 다수의 합의를 이끌어내는 것에만 초점을 맞춘다.

보장해야 하는 것은 아래와 같다.

1. 모든 충직한 장군들은, 같은 정보를 획득해야 한다. (누가 배신자인지 모르기 때문에, x번째 장군이 직접 보낸 메시지를 받았다 하더라도, 바로 사용할 수 없다.)
2. 만약 n번째 장군이 충직하다면, n번째 장군이 보낸 값은 충직한 장군들한테 같게 보내져야 한다.

The byzantine generals problem in a synchronous system

• process에게서 임의의 failure 발생 가능
• faulty process는 아무때나 아무런 값을 담은 메시지를 아무에게나 전송할 수 있고, 메시지 전송을 생략할 수 있다.
• 최대 f개의 faulty process 허용
• correct process는 시간 초과를 통해 메시지의 부재를 알아차릴 수 있지만, 다시 보낼 수 있기 때문에 보낸 이가 crash되었음을 결론 내릴 수 없다.
• 만약 통신 채널이 private이었다면 faulty process가 message를 inject할 수 없다.
• unsigned 메시지를 서로 보내는 세 가지 프로세스의 경우
  • 한 process가 fail할 수 있다면 solution X
  • N ≤ 3f → solution X
  • N ≥ 3f + 1 → 알고리즘 존재

Impossibility with three processes

• 셋 중 하나가 faulty
• 두 번의 메시지 - 장군이 어떤 값을 보내고(frist round), 부관이 서로에게 그 값을 보낸다.(seconde round)
• Symbol : (says) ⇒ 3:1:u (3 says 1 says u)
• (1) In the left-hand scenario
  • 중위 중 p3가 faulty
  • 장군이 두 process에게 값 v를 보냄
  • p2는 p3에게 v를 보내지만, p3는 p2에게 u를 보냄 (v≠u)
  • 이 단계에서 p2가 아는 것은 다른 값을 받았다는 것뿐이며, v 와 u 중 어떤 것이 장군으로부터 전송되었는지 알 수 없다.
• (2) In the right-hand scenario
  • 장군 p1이 faulty
  • 잘못된 값을 중위 2명에게 보냄
  • p3가 수신한 값 x를 올바르게 전달한 후, p2는 p3이 faulty할 때와 같은 상황에 놓이게 된다.
  • 즉, p2, p3는 서로 다른 2개의 값을 받는다.
  N≤3f 이므로 해답이 없다. (N=3, f=1)

Solution with one faulty process

⇒ 매우 복잡하므로 “ N = 4, f = 1 “ 인 경우만 따져보자

올바른 장군들은 두 차례의 메시지에서 합의에 도달한다.

• 첫 번째 라운드에서 장군은 각각의 중위들에게 값을 보낸다.
• 두 번째 라운드에서, 각각의 중위들은 받은 값을 동료들에게 보낸다.
• 중위는 장군으로부터 값을 받고, 동료들로부터 N-2개의 값을 받는다.
• 만약 장군이 잘못되었다면, 모든 중위들이 옳았고 각각은 장군이 보낸 값들을 정확하게 모았을 것이다.
• 한 명의 중위가 결함이 있는 경우, 각 동료는 장군이 보낸 값과 결함이 있는 중위가 보낸 값의 N-2개의 사본을 받는다.
• 올바른 중위는 그들이 받는 일련의 값에 단순 다수결 기능을 적용하기만 하면 된다. N ≥ 4 이므로 (N-2) ≥ 2.
• 다수결 기능은 faulty 중위가 보낸 값을 무시하고, 장군이 정확하다면 장군이 보낸 값을 생성한다.
• 왼쪽의 경우 두 개의 올바른 중위 process agree
• p2와 p4는 majority(v, u, v) = v와 majority(v, v, w) = v를 결정한다.
• 오른쪽의 경우 장군이 faulty이지만, p2, p3, p4 3개의 correct process가 agree majority(u, v, w) = ⊥을 결정한다.

Fault proces가 있지만 consensus를 이룰 수 있다