많은 현대적인 애플리케이션들은 대단히 비결정적이다. 이것은 애플리케이션의 디자인되고, 실행되는 방법에 기인한다. 대부분의 애플리케이션들이 시간마다 통신을 주고 받으며 독립적인 여러개의 쓰레드로 되어있다.(서버 애플리케이션이 많은 비동기적인 클라이언트로 부터 요청을 받는 경우, 수 백개의 유저 인터페이스 이벤트를 GUI 를 통해서 주고 받는 애플리케이션)
모든 이런 통신은 방향과 비결정성을 조정할 수 있다. 먼저 실행이 되는 동안 어떠한 현상을 복구하는 것을 막음으로써, 소프트웨어 개발기간 동안에 비결정성은 많은 문제를 내포한다.
몇몇 질적으로 향상된 소프트웨어 기술은 프로그램 실행을 반복될 수 있거나, 최소한 사용자에 의해서 콘트롤 될 수 있다. 적용범위(coverage) 분석 기술을 예로 들 수 있다. 포괄적인 애플리케이션에서 모든 코드 조각(fragment)을 테스트 하는 것은 최소 한번(once) 으로 실행되어야 한다.(step)
만일 이벤트가 콘트롤 하지 않은 상태의 프로그램이라면, coverage 를 보장할 방법이 없다. 또 다른 예는 벤치마킹으로서, 참조(reference) 실행 성능을 비교하는데 사용할 수 있다. 공정한 비교를 위해서는 같은 결과를 내는 같은 platform 에서 보장할 수 없는 비결정적인 프로그램으로 두 번 벤치마킹을 수행해야 한다. 복귀(regression) 테스트를 위한 test set 프레임워크가 필요하다. 이 테스트는 소스(soruce)의 최근 수정사항에 의해 현재 기능성 보존을 검사하기 위해 수행되어진다. 이 것은 보장 테스트를 적당히 실행하기 위해 실행 콘트롤을 할 수 있는 상황이 필요하다.

다른 소프트웨어 개발 기술의 경우, 예를 들면 (interactive or online) debugging, profiling 또는 extended checking 은 프로그램의 속도 저하를 유발한다. 이 지연 결과는 런타임 실패의 확률 가능성과 동작을 변화시킴으로서, 애플리케이션에 영향을 미친다. 결과로서, 사용자는 프로그램 분석 동안에 혼동을 일으키게 된다.

대부분 널리 사용되는 기술로서 비결정적인 프로그램의 수행을 record/replay 한다. 이것은 두개의 phase 로 동작하는 데, 초기 record phase 와 record 된 trace file 로 부터 재실행하는 것이다. replay phases 동안에 예전 실행을 trace file 로 부터의 data 를 사용함으로써 재실행한다.
재실행하기 위해서 어떤 정보가 필요한가에 대한 결정은 아주 중요하다. 이에 대한 간단한 답은 필요한 input, output 의 모든 machine 실행 instruction 을 제공하면 동등한 실행을 할 수 있다. 이 방법을 'content-based or data-driven execution' 이라고 한다. 추가적으로 input 을 알고 있기 때문에 격리된(isolation) 어떤 명령어든지 재실행할 수 있다. 하지만, 주요 단점은 trace file 을 저장한 거대한 저장 공간이 필요하다는 것이고, 그것은 실행할 수 있을지 확실하지 않다.
그러나 우리는 각 격리된 명령어가 실행하는 데 필요가 없다. 우리는 앞선 명령어를 통해 생성된 결과를 신뢰할 수 있다. 명령(instuction)은 아마도outside source 로 부터 추가적인 input 이 시작하는 것을 필요로 할 지도 모른다.(original program file, DMA channels, I/O port 또는 다른 쓰레드등)
실행 지연 동안에 input 이 같은 시간에 들어오면 동일하게 재실행을 한다. 이 방법은 'ordering-based or control-driven replay' 라 부르고, 저장되는 정보를 줄일 수 있도록 장점을 제공한다. 현재 오직 비결정적인 input data 는 어딘가로 부터 온 프로그램 자체에 의해서 수행할 수 없다.

이것은 content-based 와 ordering-based record/replay 의 사이에서 replay 방법의 연속이다. 키보드로 부터의 input 을 예로 들면, ordering-based replay 를 사용하면 record 하지 않는다. 누군가 keystroke 가 실행할 동안의 동작을 정확히 반복하기를 요청한다면, 30 분 동안의 워드 프로세서의 작업일 것이다. 이것은 정확히 실행가능하지 않다. 그래서 워드 프로세서에 입력되는 keystroke 는 content-based record/replay 를 사용함으로서 정확히 record 되어질 수 있다. 나머지 input 은 ordering-based record/replay 로 record 할 수 있을 것이다.
때때로 기술적으로 실행가능 하지만, ordering-based record/replay 를 사용하는 것이 타당하지 않을 수 있다. 우리가 6 개월동안의 갑자기 에러가 발생한 ATM 기계의 동작을 record 한다고 가정한다. 우리는 ordering-based record/replay 를 사용함으로서 버그를 조사하기 위해서 6 개월 동안을 replay 하고 싶지는 않다. 우리는 ATM 이 정상적으로 동작한 마지막 시간으로 빠르게 replay 할 수 있는 매커니즘이 필요하다. checkpoint(content-based replay) 는 매 몇 시간을 상당히 짧게 디버깅 시간을 가진다. 그래서 습관적으로 모든 record/replay 방법들은 contect-based 와 ordering-based record/replay 를 실용적으로 혼용(mix)해서 사용한다.

컴퓨터가 발명된 이래로, 환경(disk, mouse, network card)으로 부터 input 을 받기 위해 주변 장치에 크게 의존적이었다. 일반적으로 두 가지 다른 방법으로 새로운 input 의 도착을 인식한다.(polling, interrupt)
polling 을 사용하면, 프로세서는 새로운 input 과 data 를 얻기 위해 일정한 간격으로 주변장치에 신호를 보낸다. polling 을 replay 하기 위한 동작은 간단하다. 물음(question) 과 record phase 동안의 같은 응답을 프로세서에 replay 를 제공하는 동안 주변장치의 응답을 record 한다.

polling 과 대조적으로 interrupt 는 새로운 input 이 활성화(available)될 때마다, 프로세서는 멈추는 하드웨어 매커니즘을 기본으로 한다.(interrupt를 재현하는 것을 허용하는 프로세서) interrupt 는 polling 보다 좀 더 어렵다. 문제는 interrupt 가 실행 도중의 어떤 시간에 발생한다는 것이다.
interrupt 를 replay 하기 위해서는 interrupt 가 발생하는 정확한 시간을 record 하기 위한 방법이 필요하다.
한가지 방법은 프로세서가 시작한 것으로 부터 몇 번째 사이클에서 수행되는지 카운터를 하기 위해서 프로세서의 cycle counter 을 사용하는 것이다.
우리는 interrupt 가 발생하기 전에 얼마나 많은 사이클이 실행되었는지 결정할 수 있다. replay 동안에 interrupt 가 초기화되기 전에 사이클 카운터가 다시 숫자에 도착할 때까지 기다려야 한다.
한가지 문제는 이 방법이 record/replay 구조의 활동 또한 사이클들로 가정한다는 것이다. replay 동안, 다른 replay code 를 보상하고, 그리고 나서 사이클 카운터는 다르게 영향을 미친다. 두 번째 문제는 프로세서가 쓰레드를 스위칭(switch) 하고, record 되어지는 쓰레드가 더이상 실행되지 않을 때 카운터가 하기 위하여 사이클 카운터가 카운팅되는 것이다. 이 사이클 카운터의 again offset 은 반드시 보상되어야 한다.

다른 방법은 interrupt 가 발생하는 순간을 정확히 가리키게 하기 위해서 software instruction counter(SIC) 를 사용하는 것이다. SIC 는 프로그램이 실행하는 동안에 계속적으로 업데이트 되어지는 data 구조체이다. 실행에서 정확한 포인트를 가리킬 수 있다.
주요한 장점은 하드웨어 버전이 SIC 를 증가시키는 이벤트를 콘트롤 할 수 있다. 우리는 예를 들면, 쓰레드가 스위치 되거나 또는 record/replay 특정한 코드가 수행될 때 업데이트된 프로세스를 중지시킬 수 있다.

SIC 는 backward branches 의 숫자(number)와 현재 프로세서의 명령 포인터로 구성된다. 그러나 SIC 는 큰 오버헤드를 초래하고, record phase 동안 만족스럽지 못할 수도 있다.

input 은 2 가지의 이유로 재현할 수 없다. 재현할 수 없는(Web 서버의 요청, 키보드로 부터의 keystroke, 두 개 이상의 프로세스가 비동기적 방법에 의한 데이터 접근을 하여 변수값) 또는 타이밍을 재현할 수 없다.(keystroke 의 시간, 마우스 클릭 또는 서버의 요청)

input 의 내용은 재현할 수 있다. 시간을 결정적으로 유효하게 만든다. 타이머는 좋은 예이다. 그것은 어떤 카운터도 제공하지 않는다.(그러므로 재현하기도 쉽다) 그러나 순간의 그것의 실행은 결정적이다. 정확히 재현되는 실행을 위해서는 타이머를 쓰레드들 사이에서 같은 종류의 인터리빙을 얻기위해 정확히 바로 그때에 발포(fire)해야 한다.
타이밍은 외부의 input 보다 중요한 이유이다. 만일 두 쓰레드로 부터 비동기적으로 일반적인 변수에 같은 프로세서가 write 를 할 때, 복잡한 data race 를 갖는다. 만일 두개의 오퍼레이션의 정확한 순서가 record phase동안에 record 되지 않으면, replay 는 달라질 것이다. 그럼에도 불구하고 재현 가능한 것과 재현 불가능한 input 사이는 개념상 간단하다. 그것은 런타임에 이것을 구별하는 것은 쉽지 않다.

메세지 전달 프로그램은 동시에 수행되는 쓰레드로 구성된다.(물리적으로 나누어진 노드 상에서)
커뮤니케이션의 유일한 의미는 어떤 네트워크로 메세지를 통해 보내는 것이다. 메세지의 도착(오직 비동기적 메세지를 위한)과 메세지의 내용은 쓰레드를 위한 input, 비결정적인 소스의 가능성을 재현한다.

content-based replay 는 동기적인 메세지를 위한 실행은 간단하다. record phase 동안 받은 모든 메세지의 내용을 trace file 에 저장한다. replay 동안에, 각 메세지를 받은 시간을 trace file 로 부터 참조하고, 복원한다. content-based replay 의 주요한 특징으로는 message-passing program 의 모든 쓰레드는 다른 쓰레드의 실행할 필요없이 격리하여 replay 한다.
단점은 trace file 이 매우 크고 다루기 힘들다.
ordering-based record/replay 시스템은 작은 trace file 을 필요로 한다. FIFO channels 을 가진 message-passing systems 의 ordering-based record/replay 는 각 받은 오퍼레이션을 위한 송신자의 동일함을 저장하기 위해 충분하다. replay 하는 동안에, 받는 오퍼레이션은 알고 있는(known) 송신자의 받은 오퍼레이션에 의해서 수정될 수 있다. 이 받은 오퍼레이션은 계속하기 전에 올바른 메세지가 도착할 때까지 기다린다.

Netzer 과 Miller 는 naive 매커니즘이 아직 발전할 수 있다는 것을 발견했다. 아래 그림을 보기 바란다.

그림의 왼쪽 그림을 보면, M1 과 M2 는 T2 쓰레드에 불특정한 순서로(racing) 도착한다. 오른쪽의 경우, 더이상 racing 이 나타나지 않는다.
메세지들은 race 하지 않고, message-passing system 에 재 실행될 때, 문제가 없는 원인이 된다. 그러므로 해서 그들의 도착 순서를 record 할 필요가 없고 왼쪽 그림은 필요하다. Netzer`s 테크닉과 대부분 비교가능한 방법들은 인과 관계와 메세지들 사이의 확립된 시간의 순서에 의존한다.
이 순서는 관찰된 실행의 많은 특징에서 얻어진 것을 기반으로 한다.

record/replay 의 가장 큰 목적은 가능한 정확하게 record 된 실행을 replay 하는 데 있다. 이를 향상시키기 위해서는 많은 양의 정보가 요구된다. 두번째 목적으로는 가능한 적게 영향을 줌으로써 record 하기 위함이다. 이 프로그램 실행은 record phase 동안에 recording switched on 없이 수행하는 것과 거의 비슷하다. 이것은 최소한의 정보 저장소가 불가피하다.
세번째 목적은 빠르게 수행하기 위함이다. 예를 들어 ATM 의 명백한 버그 전에 6 개월간의 실행은 상기(recall) 한다. 우리는 가능한 빠르게 결점이 있는 코드를 수행하기를 원한다. 6 개월을 기다리지 않고, 실패를 찾아내기 위해 말이다. 이것은 정확성과 속도의 한편과 간섭 사이는 trade-off 관계에 있다. 높은 정확도는 많은 양의 trace 정보를 요구한다. 이 정보는 생성하고, 저장하고, 광범위한 간섭의 원인이 될 수 있는 것을 필요로 한다.
비슷하게, 실행의 조각의 빠른 재실행은 추가적인 정보를 요구한다. 또한 다시 추가적인 간섭과 저장을 필요로 한다.
record 를 위한 올바른 abstraction level 의 선택과 좀 더 또는 적은 input 을 recording 에 의해서 3 가지 주요 목적을 일치시킬 수 있다.

공유 메모리 프로그램에서 모든 공유 메모리 위치(location)은 쓰레드들 사이의 communication channel 을 고려한다.
공유 메모리 프로그램의 정확한 replay 의 실행을 위해서, record phase 동안의 실행된 같은 순서로 공유 메모리의 모든 접근(access)들은 모두 replay 되어진다. content-based trace 를 만들기 위해 모든 메모리의 접근을 가로채는 것은 record phase 동안에 지나친 오버헤드를 초래한다. 다행히도 ordering-based replay 는 가능하다.
보통 공유 메모리 프로그램은 공유 메모리 위치에 접근하는 것을 보호하기 위해 몇가지 동기화 방법을 사용한다. 동기화 오퍼레이션은 세마포어(mutual exclusion)를 보장하고 critical section 의 접근을 쓰레드들 사이에 정적(static)으로 순서(order) 하는 것을 강요하지 않는다. 이 현상은 아래 그림에 나타나 있다.

그림에 두 개의 쓰레드가 있는데, T1 과 T2 둘다 임계영역에 진입과 해제(exiting)를 한다.(그림에서 네모박스를 가리킴)
왼쪽에서 T1 는 T2 보다 약간 빠르게 실행되고 임계영역에 먼저 진입한다. T2 는 T1 이 임계영역에서 빠져나올 때까지 기다려야 한다. 오른쪽 그림은 반대의 상황이다. 임계영역 안에서 일반 변수는 수정되어 진다.(화살표를 가리킴)
동기화 생성(construct) 에 의해서 일반 변수를 보호할 수 없기에 수정하지 않는 다는 가정을 만든다. 만일 그렇다면, 보통 프로그램 에러가 data race 를 호출하도록 구성한다. data race 없이 프로그램의 수행을 재생산하기 위해서는 동기화 오퍼레이션을 수행됨으로서 충분하다.
왼쪽 그림을 묘사한 경우로는 임계영역은 첫번째로 T1 이 들어가고 그리고 다음에 오직 T2 가 들어가는 것을 record 한다.
동기화 이벤트들 사이에서 순서를 결정하는 것은 쓰레드들 사이의 인과관계를 체크함으로서 똑바르게 한다. 한번 동기화 오퍼레이션이 record 되면, 메모리 접근의 순서는 동등한 방법으로 replay 된다.(no data race 를 제공함)
record/replay 를 위한 하나의 시스템은 앞선 방법 RecPlay 가 실행된다. 그것은 no data race 를 포함하는 공유 메모리 프로그램의 record/replay 를 허용한다. record phase 동안, 동기화 오퍼레이션의 순서는 모든 동기화 오퍼레이션들의 Lamport timestamps 를 attach 함으로서 trace 된다.
Lamport timestamps 는 trace file 안에 압축되어 저장되고, 아주 작은 시간 오버헤드의 원인이 된다.

replay 동안에, trace file 은 각 시간 동기화 오퍼레이션이 실행되는것을 참고한다. trace file 로 부터 동기화 오퍼레이션의 Lamport timestamp 를 얻는다. 이 정보를 사용하는 것은 동기화 오퍼레이션의 실행이 모든 동기화 오퍼레이션이 더 작은 timestamp 를 가지고 실행되어질 때까지 지연된다.

이 모든 동기화 오퍼레이션의 보장은 만일 no data race 가 없다면 충실한 재실행 보장을 하기 위해 수행된다. replay 동안 data race detector 을 실행함으로서, race 상태가 replay 에 손해를 입히기 전에 탐지해낸다. 이 점들 외에 실행을 replay 하기 위해서는 data race 가 첫번째로 없어야 하고, record/replay 사이클이 다시 초기화 되어야 한다.

abstraction level 은 replay 동안에 충실하게 재실행되어야 하는 이벤트들의 모음으로 정의되어 진다. 극히 상세한 실행의 재생산은 보통 불가능하다.
예를 들어, 우리는 원자(atomnic) level 의 chip 의 동작을 관찰하고 집행하지 못한다. 약간 상위 level(우리는 아키텍처 연구를 수행함) 우리는 보통 예언자(predictor) 분기(branch) 의 동작 또는 프로세서의 파이프라인의 다른 단계(stage) 를 통해서 어떻게 명령어를 증가시키는(propagate) 것에 대해 정확히 흥미를 느끼지 못한다.

우리는 공유 메모리 컴퓨터 프로세서들의 cache 의 상호 작용(interaction) 에 관심을 두었다. 그러나 아마도 우리는 단순히 프로세서와 내부의 작업을 무시하고, 주위의 전체적인 하드웨어 상에서의 명령을 replay 하는 것을 원했다.
abstraction 의 상위 level 은 바란다. 예를 들면, 많은 개발 환경은 현재 프레임워크 안에 프로그래머가 코드를 집어넣는 것을 허용하고 있다.
개발자는 오직 그들 코드의 동작을 replay 하는 것을 원하고 실행하는 동안 프레임워크 안에서 어떠한 일이 벌어지는지 알고 싶어하지 않을 것이다.
프레임워크의 코드 동작이 전혀 외부 영향을 받지 않았다고 하는 가정이 필요하다. 이것은 record/replay 를 위한 abstraction level 을 올바르게 선택하기 위해 아주 중요하다. 만일 level 이 매우 느리다면, 낮은 간섭을 줘야 하는 본래의 취지를 만족하지 못할 것이다.(너무 많은 정보를 모아서 저장한다면)
만일 level 이 너무 빠르다면, 어떤 이벤트는 replay 할 수 없고 record 된 실행과 replay ehlsms 실행 사이에 불일치가 일어날 것이다.
input replaying 에 대한 좀더 세부적인 정보는 공유 메모리 프로그램, 그리고 메세지 전달 프로그램은 3 가지의 블럭에서 설명했다.

현재 많이 알려진 record/replay 방법들은 비결정적 프로그램의 실행을 콘트롤 하는데 효과적이다. 특별한 실행은 오직 작은 오버헤드의 비율과 함께 record 함으로써 프로그램 실행을 보여줄 수 있다. 모든 시간의 recording 장비로 바꾼다면, 별 대수롭지 않은 일이다.
이 작업은 한정된 실행 시간에 모든 실행을 좋게한다. 계산이 끝난 후의 종료하기 위해 계획되지 않은 프로그램을 위해 예를 들어 서버 애플리케이션과 임베디드 애플리케이션 완벽한 실행의 record 를 하기는 힘들다. 아무도 6 개월 또는 더 긴 동안 실행된 프로그램을 replaying 하는 데 흥미를 갖지는 않는다.

ordering-based replay 로서 content-based record/replay 를 위한 trace 는 아무런 문제가 없다고 처음에 언급했었다. 문제점은 프로그램의 정기적인 checkpoint 를 이용해서 해결할 수 있다. 그러나 checkpoint 는 또한 공간과 시간 그리고 실시간 애플리케이션을 위한 실행 불가능하게 만들 수 있는 큰 오버헤드를 야기한다.
중요한 문제는 재현불가능한 input 의 record 이다. keystrokes 와 mouse click 은 low-bandwidth input 이지만, 그러나 네트워크 activity, sensor read, print job 을 record 하는 것은 쉽고 빠르게 몇 메가 바이트의 trace file 로 만들 수 있다.

이런 관계로 연구의 초점은 모든 input 이 유효화 없이 가능할 때까지 애플리케이션의 의미심장한 replay 가 record 되는 필터링 하는 것에 맞췄다.