[병렬프로그래밍] Universality of Consensus

lower consensus can not built higher consensus

Consensus is universal (만능)

n-thread consensus build (wait-free, linearizable, n-threaded implementation, any sequentially specified object)

wait-free - stronger (system), lock-free (per thread)

 

Lock-free : infinitely often some method call finishes (how to prevent starve)

Wait-free : each method call takes a finite number of steps to finish

 

lock 없이 execution order를 만들기 위해 도움을 받아야 함. 만약 실패한다면 새 상태를 포인팅 해야 함

consensus state return new state

 

중요 : 아래 내용은 enqueuer와 dequeuer각각 하나의 쓰레드만 있을 때 적용되는 사항

Decide는 2-consensus를 해결해줌

 

Decide

 

상태가 갈리는 안 좋은 예시

상태가 여러갈래로 나뉘면 안됨

 

 

Next pointer points next method. Decide uniquely.

If fail, step back and re read - not violate

linked list - global execution order

마지막까지 읽은 후에 내 method를 추가

아래 그림까지는 Linearizable 한 상태이고 Lock-free & Wait-free 상태는 아님

 

중요 : 아래 내용부터 Universal Construction (n consensus)

Threads use one-time consensus object to decide which node goes next

Threads update actual next field to reflect consensus outcome

 

Unique global order is important

Global execution order need uniquely -> n 개의 쓰레드가 합의 가 가능하다 consensus number n

Bottleneck -> sequentially execution , so make concurrently

유니크한 global order를 사용하는 것으로 Lock-free implement

아래 그림 - 하지만 실패 시 계속 찾아가야 하므로, Wait-free는 안됨

Wait-free로 만드는 방법

가장 빠른 쓰레드와, 느린 쓰레드의 distance를 제한하는 것이 wait-free가 됨

finite step n에 모두 다 끝남

Announce array를 사용