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