[병렬프로그래밍] Consensus

Mutual Exclusion 이 안 좋은 이유 - Lock을 잡고 sleep 할 수 있다

Falut tolerance - 장애가 발생해도 정상적, 부분적으로 기능을 수행할 수 있음

 

Wait-Free synchronization 은 좋지만 어렵다 (Wait-Free : 일정 step 내에 method를 처리할 수 있음)

systematically 하게 구현 하고싶지만 non deterministic 함 (현재 상태에서 여러 선택을 할 수 있음 - 오토마타 개념)

 

Queue에서 Dequeuer가 여러 명일 때, Lock을 사용하지 않고 어떻게 처리할 수 있을까?

Consensus (합의) 문제를 해결 할 수가 없음 -> race condition

 

Consensus : Thread 별 값을 각각 갖고 있던 것을, Communicate를 통해 합의

 ㄴ consistent : 모든 쓰레드가 같은 값을 가져야함

 ㄴ valid : 어떤 하나의 쓰레드가 가지고 있던 값이어야 함

 

Impossible1

 No Wait-Free Implementation of Consensus using Register (레지스터로는 wait free implementation 이 불가능)

 

Wait-free computation is a tree.

 

proof) 레지스터로 wait-free를 구현할 수 없음을 증명

register에 할 수 있는 동작은 read, write

2번의 read와 2번의 write를 한다. 파란 화살표 - read, 빨간 화살표 - write

2갈래로 선택 가능한 상태 Bivalent, 1갈래로 선택 가능한 상태 Univalent.

read, write 를 두번씩만 하기 때문에 생김.

Bivalent 에서는 outcome (결과) 가 정해져 있지 않음 (not fixed)

 

최종 상태에서 어떤 값이 나올지 모르기 때문에 구현 할 수없다.

 

Critical State - 자식 노드가 0-valent 와 1-valent로 나뉘어 진 상태

Critical State가 생기면, wait-free 가 될 수 없음(혹은 bivalent 상태가 이어질 때) (step 이 얼마나 이어질지 모름)

 

값이 같더라도, Consensus 값이 다를 수 있음.

Read & Read 에서도 Consensus 하지 못한 상황

 

모든 곳에서 Register만으로는 Consensus를 할 수 없음

 

N 개의 thread가 합의하기 위해선 consensus number N 이 필요

atomic register 은 consensus number가 1이기 때문에 2명의 dequeuer를 구현 할 수 없음

 

다음 장에서 하고 싶은 것

queue 에서 enqueue와 dequeue가 동시에 들어왔을 때 상태가 두갈래로 나뉘지 않고 하나가 되도록 consensus 문제를 해결