Chapter 4 Coordination and Agreement(조정 그리고 동의[1/2])

1. 서론

분산시스템은  프로세스 안에서 각각의 속성을 동의를 받는 것과 조정하는 것이다.

- 하나의 우주선 같은 그것은 필수적이다. 각각의 컴퓨터를 조정하는 것에 대해 실행할지 중지시킬지 정한다.

주종관계로 이루어진 관계가 아니다.

- 고정된 마스터의 객체를 통해 실패를 사전에 방지한다.

비동기 시스템 : 시간 범위를 정하지 않는다.

동기 시스템 : 메세지의 최대 용량, 변환 지연, 각 시간이 계량범위, 정해진 시간에 실행, 타임아웃의 구간을 충돌로 발견

각가의 독립된 프로세스의 조정 활동은 필요로 한다.

- Failure detection : 비동기 네트워크에서 나의 Peer가 죽었는지 살았는지 어떻게 파악할 것인가?

- Mutual exclusion : 두개 이상의 프로세스에서 상호 연결되어있으면 어떻게 공유할 것인가?

- Election : 마스터-슬레이브 시스템에서 어떻게 마스터를 선출할 것인가?

- Multicast : 받는 그룹에게 전송

  * 멀티캐스트의 안정성

  * 처리 순서 예약

- Consensus  : 비잔틴과 같은 오류 처리

  * 어떻게 파악할 것인가? 비동기에서는 더욱 불안정적인 커뮤니케이션을 통하는 상황에서

- 오류 추정 그리고 실패 추적

  * 안정적인 커뮤니케이션 프로토콜; 보다 안정적인 메세지 채널 확보

  * Failure detector; 특정한 프로세스 실패인지에 대한 프로세스 주문(쿼리)의 서비스 형태

  * Unreliable failure detector

     - unsuspected : 고장나지 않았다고 예상

     - suspected : 고장났다고 예상

  * Reliavle failure detector (실현 힘듬)

     - unsuepected : 힌트에 지나치지 않음

     - Failed : 그 프로세스는 충돌이 있었다고 확정

2. 내용

2.1 Distributed mutual exclusion 

- 종종 분산된 프로세스는 자신들의 행동을 조정하는 것을 필요로 한다.

  * 만약 집약된 프로세스들의 공유된 자원 그리고 제약식은 요구된다. 간섭 보호와 일치성 보장

  * 처리 영역 문제

- Mutual exclusion을 위한 알고리즘

  * Assumptions 

    - 비동기, 프로세스상의 오류는 없다, 메세지 전송은 안정적이다

  * 어플리케이션 레벨의 프로토콜

    - enter(), resoureceAcceses(), exit()

  * 요구되는 상호간 제약 사항

    - Safety, Liveness, Ordering

  (1) The central server algorithm - 중앙 집중식 서버 알고리즘

      && Satisfy properties sfety and liveness, but not for ordering

  (2) A ring-based algorithm; 논리적으로 링의 형태를 가질뿐 네트워크상의 물리적 형태는 아님

      && 일방통행

      && 토큰을 통한 critical section 공유

      && Satisfy properties sfety and liveness, but not for ordering

  (3) An algorithm using multicast and logical clocks

      (RELESED;빈상태, WANTED;요청상태, HELD;진행상태) 

      && N개의 브로드캐스팅으로 인한 효율 및 속도 저하

      && Safety, Liveness, Ordering properties are satisfied

  (4) Algorithms for mutual exclusion

      (Voting Set; 메인 포인트를(중첩구간)을 통해 한쪽 군으로만 투표 가능)

      && A,B,C 가정에 의한 상호 DeadLock 문제 발생

2.2 Election 

- Participant, Non-participant

- Safety; 프로세스 처음부터 끝까지 가장 영향력있는 마스터 선출

- Liveness; 모든 참여와 선출

   

  (1) A ring-based election algorithm

      Election message는 자기 자신만 Master 확인 가능 

      확인 후 마스터 선출 및 브로드캐스팅

      가장 큰(MASTER) N 앞에 위치한 N+1값은 2N-1로 진행된다.

  (2) The bully algorithm

      자기 보다 큰 값에게 MSG 전송

      && 제한시간이 있음 - Synchronous system