[병렬프로그래밍] Universality of 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를 해결해줌
상태가 갈리는 안 좋은 예시
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를 사용
