유한한 선점(Bounded Preemptions) 하에서의 순차적 일관성(Sequential Consistency) 검증

요약

본 논문은 멀티스레드 프로그램에서 최대 π번의 선점(preemptions)이 발생하는 조건 하에 순차적 일관성(Sequential Consistency) 인터리빙의 존재 여부를 검증하는 문제를 다룹니다. 연구 결과, 작성자(writer)의 수에 따라 문제의 복잡도가 다항 시간, NP-hard, 그리고 지수 시간 하한으로 나뉘는 삼분법적 특성을 발견했습니다. 또한 선점 횟수 π가 제한되지 않을 경우 이 문제가 W[1]-hard임을 증명하여 고정 파라미터 계산 가능성(FPT)이 낮음을 보여줍니다.

핵심 포인트

• 유한한 선점(Bounded Preemptions) 조건에서의 순차적 일관성 검증 문제 연구
• 작성자 수에 따른 복잡도 삼분법: 단일 작성자(다항 시간), 두 명(NP-hard), 세 명(ETH 기반 조건부 하한)
• 선점 횟수 π가 제한되지 않을 경우 W[1]-hard임을 증명
• 실제 버그가 적은 횟수의 선점적 전환 내에서 발생한다는 경험적 근거를 바탕으로 연구 수행