공유 스냅샷 개체

분산 컴퓨팅에서 공유 스냅샷 개체는 여러 스레드 또는 프로세스 간에 공유되는 데이터 구조의 한 유형입니다.많은 작업에서는 메모리 상태를 일관되게 볼 수 있는 데이터 구조를 갖는 것이 중요합니다.실제로는, 이 처리중에, 개개의 레지스터에 격납되어 있는 값을 언제라도 변경할 수 있기 때문에, 공유 레지스터에 차례차례 액세스 하는 것만으로, 이러한 메모리 상태를 일관되게 하는 것은 불가능하다는 것을 알 수 있다.이 문제를 해결하기 위해 스냅샷 객체는 n개의 컴포넌트의 벡터를 저장하고 다음 2개의 원자 연산을 제공합니다.update(i,v)는 ih 컴포넌트의 값을 v로 변경하고 scan()은 모든 n개의 ^[1]^[2]컴포넌트에 저장된 값을 반환합니다.스냅샷 객체는 원자성 싱글 라이터 멀티 리더 공유 레지스터를 사용하여 구성할 수 있습니다.

일반적으로 싱글 라이터 멀티 리더(swmr) 스냅샷 객체와 멀티 라이터 멀티 리더(mwmr) 스냅샷 객체를 구분합니다.swmr 스냅샷 오브젝트에서는 컴포넌트의 수가 프로세스 수와 일치하고, 메모리 위치 i에 쓸 수 있는 것은 1개의 프로세스_i P뿐이며, 다른 모든 프로세스는 메모리를 읽을 수 있다.이와는 대조적으로 mwmr 스냅샷 오브젝트에서는 모든 프로세스가 메모리의 모든 위치에 쓰기가 허용되며 메모리를 읽을 수도 있습니다.

일반

공유 메모리는 여러 부분으로 분할됩니다.이러한 각 부품은 단일 데이터 값을 보유합니다.싱글 라이터 멀티 리더 케이스에서는, 각_i 프로세스 P가 메모리 위치 i를 할당해, 이 프로세스만이 메모리 위치에 기입할 수 있다.단, 모든 프로세스는 메모리 내의 임의의 위치를 읽을 수 있습니다.멀티 라이터 멀티 리더 케이스에서는, 제한이 변경되어 어느 프로세스에서도 메모리의 위치를 변경할 수 있다.n 프로세스 시스템의 프로세스 P p_i $\in$ {1,...n}은(는) 스냅샷 오브젝트에 대해 scan()과 update(i,v)의 2개의 조작을 실행할 수 있습니다.검색 작업에는 인수가 없으며 메모리에 대한 일관된 보기를 반환합니다.업데이트(i,v) 작업은 위치 i의 메모리를 값 v로 업데이트합니다.

어느 타입의 조작도 프로세스에 의한 콜과 메모리에 의한 리턴 사이에 원자적으로 발생하는 것으로 간주됩니다.보다 일반적으로 데이터 ${\overline {d}}$ d ${\$ {\ $displaystyle {d}}$ 에서 $\overline{d}$ 각_k 엔트리 d는 메모리의 ^[1]일부 k를 업데이트하는 마지막 선형 업데이트 작업의 인수에 해당합니다.

공유 스냅샷 개체의 이점을 최대한 활용하기 위해 검증 및 구성을 단순화하는 측면에서 스냅샷 ^[1]개체의 구성에 두 가지 다른 제한 사항이 추가되었습니다.첫 번째 제한은 아키텍처입니다.즉, 스냅샷 오브젝트는 싱글 라이터 멀티 리더 레지스터를 기본 요소로만 구성됩니다.이것은 싱글 라이터 멀티 리더의 스냅샷에 대해서 가능합니다.멀티 라이터 멀티 리더 스냅샷 오브젝트의 경우 멀티 라이터 멀티 라이터 레지스터를 사용할 수 있으며, 멀티 라이터 레지스터는 싱글 라이터 멀티 리더 ^[1]^[3]^[4]레지스터로 구성할 수 있습니다.

분산 컴퓨팅에서 시스템 구축은 실행 중에 시스템 전체가 진행된다는 목표에 의해 추진됩니다.따라서 프로세스의 동작으로 인해 전체 시스템이 정지되어서는 안 됩니다(잠금 해제).이 보다 강력한 버전은 wait-freedom 속성입니다.즉, 어떤 프로세스도 다른 프로세스가 동작을 종료하는 것을 막을 수 없습니다.보다 일반적으로, 이것은 모든 작업이 다른 프로세스의 동작에 관계없이 한정된 수의 단계를 거쳐 종료되어야 함을 의미합니다.매우 기본적인 스냅샷 알고리즘은 시스템 전체의 진척을 보장하지만 잠기지 않습니다.이 알고리즘은 쉽게 확장할 수 있기 때문에 대기 시간이 필요 없습니다.구현 섹션에 나와 있는 Afek ^[1]등의 알고리즘에는 이 특성이 있습니다.

실행

공유 스냅샷 개체를 구현하는 방법은 여러 가지가 있습니다.처음 제시된 알고리즘은 스냅샷 개체의 주요 구현을 제공합니다.단, 이 실장에서는 lock-free 속성만 제공됩니다.두 번째는 Afek ^[1]등에 의해 제안된 구현을 제시했다.웨이트리스라고 불리는 더 강한 성질을 가지고 있습니다기타 구현의 개요는 Fich에 ^[2]의해 제공됩니다.

기본 swmr 스냅샷 알고리즘

이 알고리즘의 기본 개념은 이 알고리즘을 실행하는 모든 프로세스가scan()모든 메모리 값을 두 번 읽습니다.알고리즘이 같은 메모리 내용을 2회 정확하게 읽어낼 경우 그 사이에 값을 변경한 프로세스는 없으며 결과를 반환할 수 있습니다.프로세스, 이 프로세스에서는update(i,v)메모리내의 값을 갱신해 주세요.

true a [1 . n ] : = collect ; b [ 1 . n ] : = collect ; b [ 1 . n ] : = collect ; (두 수집 중 읽기 간에 위치 i가 변경되지 않은 경우) b; // 이중 수집 성공 루프 엔드를 반환한다.

함수 업데이트(i, v) M[i] := v; end

그림 1: 한 프로세스는 다른 프로세스의 이중 수집 중에 항상 메모리를 업데이트합니다.따라서 스캔 프로세스는 종료할 수 없습니다.

이 알고리즘은 스냅샷 개체의 매우 기본적인 구현을 제공합니다.개별 프로세스의 동작으로 인해 개별 스레드가 부족할 수 있지만 시스템이 계속 진행되도록 보장합니다.프로세스_i P는, 다른_j 프로세스 P가, 다른 프로세스 P를 종료하는 것을 방지할 수 있습니다.scan()2개의 메모리 수집 사이에 항상 값을 변경함으로써 동작합니다.따라서 알고리즘은 잠금이 필요 없지만 대기 시간이 필요 없습니다.이 속성을 더 강하게 유지하기 위해 다른 프로세스의 동작으로 인해 프로세스가 부족해지는 것은 허용되지 않습니다.그림 1은 문제를 나타내고 있습니다.P가 다음 명령어를 실행하려고 하는₁ 동안scan()두 번째 프로세스₂ P는 항상 "이중 수집"을 방해합니다.따라서 스캔 프로세스는 항상 작업을 재시작해야 하며 종료할 수 없으며 부족해질 수 없습니다.

Afek 등에 의한 싱글 라이터 멀티 리더의 실장.

Afek 등의 swmr 스냅샷 알고리즘의 기본 개념은 프로세스가 다른 프로세스가 메모리 위치를 변경했는지 여부를 검출할 수 있으며 프로세스가 서로 도움이 되는지 여부입니다.다른 프로세스가 그 값을 변경했는지 여부를 검출하기 위해 각 레지스터에 카운터를 부가하고 갱신할 때마다 카운터를 증가시킨다.두 번째 아이디어는 메모리 위치를 업데이트하는 모든 프로세스에서 또한scan()레지스터의 "메모리 보기"를 다른 프로세스에 제공합니다.스캔 프로세스에서 이를 빌릴 수 있습니다.scan결과를 반환한다.

무제한 메모리 기반

이 아이디어를 사용하면 무제한 크기의 레지스터를 사용하는 대기 없는 알고리즘을 구성할 수 있습니다.업데이트 작업을 수행하는 프로세스는 스캔을 완료하는 프로세스에 도움이 될 수 있습니다.기본 개념은 프로세스가 메모리 위치를 두 번 업데이트하는 다른 프로세스를 볼 경우 해당 프로세스는 그 사이에 완전한 선형화된 업데이트 작업을 실행해야 한다는 것입니다.이를 구현하기 위해 각 업데이트 동작은 먼저 메모리를 스캔한 후 새로운 값 v 및 시퀀스 번호와 함께 스냅샷 값을 아토믹하게 쓴다.프로세스가 메모리의 스캔을 실행 중이고 프로세스가 메모리 부분을 2회 갱신한 것을 검출했을 경우, 갱신 프로그램의 「임베디드」스캔을 「빌려서」스캔 조작을 ^[1]완료할 수 있다.

function scan() // j = 1 to n do moved [j] := 0 엔드에 대한 일관된 메모리 뷰를 반환하고 true do a [1 . n ] : = collect; // collect ( data, sequence, view) triple b [1 . n ] : = collect; /// collect; // collect (데이터, 시퀀스, scollect) 3배 수집(a[j])의 경우.seq = b[j]seq) 그런 다음 (b[1.data, ..., b[n].data) // a[j]의 경우 j = 1~n에 대해 프로세스 변경 메모리가 없습니다.seq b b [ j ]seq 다음 // 프로세스가 이동된 경우 [j] = 1로 이동한 후 // 프로세스가 b[j]를 반환하기 전에 이미 이동되었습니다.보기, 그렇지 않으면 이동됨 [j] : = 이동됨 [j] + 1, 엔드 엔드 함수

프로시저 업데이트(i,v) // 데이터 값으로 레지스터 업데이트, 시퀀스 번호 업데이트, 내장형 스캔 s[1..n] := 스캔, // 내장형 스캔_i r :=(v, r_i.seq = r_i.seq + 1, s[1..n]), 프로시저 종료

그림 2: 싱글 라이터 멀티 리더 스냅샷 객체의 선형화 순서 예.첫 번째 스캔()은 성공적으로 이중 수집을 수행할 수 있지만 두 번째 스캔의 "이중 수집"은 두 번째 프로세스에 의해 두 번 중단됩니다.따라서 프로세스는 내장된 스캔을 빌립니다.

모든 레지스터는 데이터 값 필드, 시퀀스 번호 및 마지막 업데이트 전에 수집된 마지막 내장 스캔 결과 필드로 구성됩니다.각 스캔 동작에서 프로세스_i P는 시퀀스 번호를 사용하여 프로세스가 메모리를 변경했는지 여부를 판정할 수 있다.이중 수집 중에 메모리에 변화가 없으면 P는 두 번째 스캔 결과를 반환할 수 있습니다_i.프로세스에서 다른 프로세스가 그 사이에 메모리를 업데이트한 것을 확인하면 이 정보가 이동필드에 저장됩니다.스캔 실행 중에 프로세스_j P가 메모리를 2회 변경했을 경우, 스캔 프로세스_i P는 갱신 동작 중에 자신의 레지스터에 저장한 갱신 프로세스의 내장 스캔을 반환할 수 있다.

이러한 연산은 레지스터에 쓸 때 각 update() 연산을 선형화함으로써 선형화할 수 있습니다.스캔 작업은 선형화하기 더 복잡합니다.스캔 작업의 이중 수집이 성공하면 두 번째 스캔이 끝날 때 스캔 작업을 선형화할 수 있습니다.다른 경우 - 한 프로세스가 레지스터를 두 번 업데이트 - 업데이트 프로세스가 내장 스캔을 수집한 시점에서 레지스터에 ^[1]값을 쓰기 전에 작업을 선형화할 수 있습니다.

한정된 메모리에 근거하다

제시된 알고리즘의 제한 중 하나는 시퀀스 번호가 지속적으로 증가하기 때문에 무제한 메모리를 기반으로 한다는 것입니다.이 제한을 극복하기 위해서는 프로세스 간에 메모리 위치가 두 번 변경되었는지 여부를 검출하는 다른 방법을 도입해야 합니다.각 $\langle P_{i},P_{j}\rangle$ 쌍 $\langle P_{i},P_{j}\rangle$ $\langle P_{i},P_{j}\rangle$ " { $displaystyle \langle P_{i$ }, $P_{j}\rangle}$ 는 2개의 단일 라이터 싱글 리더(swsr) 레지스터를 사용하여 통신합니다.이 $\langle P_{i},P_{j}\rangle$ 레지스터에는 2개의 원자 비트가 포함되어 있습니다.프로세스가 "이중 수집"을 수행하기 전에 파트너 프로세스의 가치를 자체 레지스터에 복사합니다.스캐너 프로세스_i P가 「더블 콜렉트」를 실행한 후에, 그 사이에 상대 프로세스_j P의 값이 변화한 것을 관찰했을 경우는,^[1] 메모리에 대해서 갱신 조작을 실행한 것을 나타낸다.

반면 j=1를 위해 하는 n qi,j 할 진정한 기능 scan()을 끓여j=1에 0말 하고 있는 걸까 moved[j]:=n에:)rj.pj,i 끝 a[1..n]:=수집,//성냥곽(데이터, bit-vector, 토글을)배 b[1..n]:=수집, // 사의 기억을 일관된 입장을 반환합니다llects(data, bit-timeout, toggle, view) (a[j].p_j,i = b[j]인 경우, (data, bit-time, toggle, view) 세 배입니다.p_j,i = q_i,j) 및 a[j].= b[j] 전환전환한 다음 반환(b[1.data, ..., b[n].data) // (a[j.p_j,i_i,j † q) 또는 (a[j].p_j,i † q_i,j) 또는 (a[j])인 경우 j=1에서 n do에 대해 프로세스가 변경된 메모리가 없습니다.§ b[j]를 토글하다전환) 그런 다음 // 프로세스 j가 이동한 경우 업데이트를 수행한 후 b[j] = 2를 반환하기 전에 // 프로세스가 이미 이동되었습니다.보기, 그렇지 않으면 이동됨 [j] : = 이동됨 [j] + 1, 엔드 엔드 함수

프로시저 업데이트(i,v) // 모든 레지스터의 데이터 값, "쓰기 상태"로 레지스터를 업데이트하고, j = 1 ~ n do f[j] := 스캔_j,i, // 내장형_i 스캔 r :=(v, f[1..n], embeddedr, s[1_i..n] 종료 절차를 위해 토글 비트와 내장형 스캔을 반전합니다.

무제한 시퀀스 번호는 각 프로세스 쌍에 대해2개의 핸드쉐이크비트로 대체됩니다.이러한 핸드쉐이크 비트는 swsr 레지스터에 기반하여 매트릭스 M으로 나타낼 수 있습니다.여기서 프로세스_i P는 행 i에 쓸 수 있고 열 i의 핸드쉐이크 비트를 읽을 수 있습니다.스캔 프로세스는 이중 수집을 수행하기 전에 해당 열을 읽어 모든 레지스터에서 모든 핸드셰이크 비트를 수집합니다.그 후, 공정이 두 배 값 동안 값을 변경했는지 여부를 판단할 수 있습니다.따라서 이 프로세스는 처음에 읽은 핸드쉐이크 비트와 열을 다시 비교하기만 하면 됩니다.1개의 프로세스_j P만이 2회 기입했을 경우, P의 수집중에_i, 스캔중에 핸드쉐이크 비트가 변화하지 않을 가능성이 있습니다.따라서 "toggle bit"라고 불리는 다른 비트를 도입해야 하며, 이 비트는 쓰기마다 변경됩니다.이것에 의해, 다른 프로세스가 레지스터를 갱신하지 않아도, 2개의 연속 기입을 구별할 수 있습니다.이 방법을 사용하면 스캔 절차에서 다른 내용을 변경하지 않고 무제한 시퀀스 번호를 핸드쉐이크 비트로 대체할 수 있습니다.

스캔 프로세스_i P는 핸드쉐이크 비트를 사용하여 더블 콜렉트를 사용할 수 있는지 여부를 검출하는 한편, 다른 프로세스에서도 갱신 조작을 실행할 수 있습니다.첫 번째 단계에서는 다른 프로세스가 제공하는 핸드쉐이크 비트를 다시 읽어내고 그 보완을 생성한다.그런 다음 이러한 프로세스가 내장된 스캔을 다시 생성하고 업데이트된 데이터 값, 수집된 보완된 핸드쉐이크 비트, 보완된 토글 비트 및 내장된 스캔을 레지스터에 저장합니다.

핸드쉐이크 비트는 시퀀스 번호를 동등하게 대체하기 때문에 리니어라이제이션은 무제한 메모리 케이스와 동일합니다.

Feek 등에 의한 멀티 라이터 멀티 리더의 실장.

멀티 라이터 멀티 리더 스냅샷 객체의 구성에서는 n개의 프로세스가 m개의 레지스터로 구성된 메모리 내의 임의의 위치에 쓸 수 있다고 가정합니다.따라서 프로세스 ID와 메모리 위치 사이에는 더 이상 상관 관계가 없습니다.따라서 핸드쉐이크 비트 또는 내장 스캔을 데이터 필드와 더 이상 연결할 수 없습니다.따라서 핸드쉐이크 비트, 데이터 메모리 및 임베디드 스캔은 동일한 레지스터에 저장할 수 없으며 메모리에 대한 쓰기는 더 이상 원자적인 작업이 아닙니다.

그림 3: 멀티 라이터 멀티 리더 스냅숏 오브젝트의 선형화의 예를 나타냅니다.

그 때문에,update()프로세스는 3개의 다른 레지스터를 개별적으로 업데이트해야 합니다.먼저 읽은 핸드쉐이크 비트를 저장한 후 내장된 스캔을 수행하고 마지막으로 지정된 메모리 위치에 값을 저장해야 합니다.각각의 쓰기는 독립적으로 원자적으로 행해지는 것처럼 보이지만, 동시에 행해지지 않습니다.새로운update()절차는 몇 가지 변경으로 이어집니다.scan()기능.핸드쉐이크 비트를 읽고 메모리 내용을 두 번 수집하는 것만으로는 충분하지 않습니다.시작을 감지하기 위해update프로세스는 메모리 내용을 수집한 후 핸드쉐이크 비트를 두 번째로 수집해야 합니다.

이중 수집이 실패하면 내장된 검색을 대여하기 전에 프로세스가 다른 프로세스를 세 번 이동해야 합니다.그림 3은 문제를 나타내고 있습니다.첫 번째 이중 수집이 실패하는 이유는update첫 번째 이중 수집 중에 검색 작업이 메모리 쓰기를 완료하기 전에 프로세스가 시작되었습니다.그러나 P가 메모리 스캔을 시작하기 전에₁ 이 쓰기의 내장 스캔이 수행 및 저장되므로 유효한 선형화 지점이 없습니다.프로세스₂ P가 두 번째 쓰기를 시작하고 핸드쉐이크 비트를 업데이트하기 때문에 두 번째 이중 수집은 실패합니다.swmr 시나리오에서는 임베디드 스캔을 빌려서 반송합니다.mwmr 시나리오에서는 두 번째부터의 삽입 스캔이 있기 때문에 이것이 가능하지 않습니다.write는 여전히 스캔 간격 내에서 선형화되지 않았습니다(스캔 간격 및 작동 종료).따라서 프로세스에서는 스캔 간격 동안 적어도1개의 임베디드 스캔이 선형화되었는지 확인하기 위해 다른 프로세스에서 세 번째 변경을 확인해야 합니다.제3의 변경 후, 스캔 프로세스는 리니어라이제이션 기준을 위반하지 않고 오래된 메모리 값을 빌릴 수 있다.

복잡성

Afek 등에 의해 공유 스냅샷 객체의 기본 구현이 제시되었다.에는 O $O(n^{2})$ ^[1]( $O(n^{2})$ $){$ $displaystyle$ O $(n^{2})$ 메모리 $O(n^{2})$ 조작이 $O(n^{2})$ 합니다.Anderson이 독자적으로 개발한 또 다른 구현에서는 기하급수적인 $O(2^{n})$ O( $)$ { $display style$ O $(2^{n$ ^[5]가 필요합니다.또한 O $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ 2 $O(n\log ^{2}n)$ $)\style$ O $(n\log$ ^{ $2}n)}$ ^[6]연산을 $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ 하여 swmr 레지스터에 기반한 스냅샷 객체의 랜덤화 구현도 있습니다.이스라엘과 Shirazi가 무제한 메모리를 사용하는 또 다른 구현에서는 ^[7]^[8]메모리 상에서 $O(n^{3/2}\log ^{2}n)$ O( $O(n^{3/2}\log ^{2}n)$ 3/ $O(n^{3/2}\log ^{2}n)$ log $O(n^{3/2}\log ^{2}n)$ n $O(n^{3/2}\log ^{2}n)$ )(\ $displaystyle O(n^3/2$ }\ $log ^{2$ }n $)}$ 연산이 $O(n^{3/2}\log ^{2}n)$ $O(n^{3/2}\log ^{2}n)$ 합니다.이스라엘 등은 다른 작업에서 업데이트 작업에 대한 낮은 수준의 작업 하한을 보여준다.하한은 $\Omega (\min\{w,r\})$ { $\Omega (\min\{w,r\})$ , $\Omega (\min\{w,r\})$ $\Omega (\min\{w,r\})$ $)(\displaystyle$ \Omega $(\min\{w,$ r $\Omega (\min\{w,r\})$ 입니다.여기서 w는 업데이트 프로그램 수, r은 스캐너 수입니다.Attiya 및 Rachman은 swmr 레지스터에 기반한 결정론적 스냅샷 알고리즘을 제시합니다.이 알고리즘은 업데이트 및 ^[8] $O(n\log n)$ 마다 O(n log $O(n\log n)$ n $){$ $displaystyle$ O $(n\log$ n $)}$ 개의 $O(n\log n)$ 연산을 $O(n\log n)$ 합니다.이스라엘, Shaham 및 Shirazi에 의한 일반적인 방법을 적용하면 무제한 스냅샷 알고리즘으로 개선할 수 있습니다. 이 알고리즘은 스캔당 O $O(n\log n)$ log $O(n\log n)$ style $)\displaystyle$ O $(n\log$ n $)$ 연산과 $O(n\log n)$ $O(n)$ O $)\displaystyle$ O $(n)$ 연산만 있으면 $O(n)$ $O(n\log n)$ .Inoue ^[10]등에서는 읽기 및 쓰기 작업을 선형적으로만 사용하여 한층 더 개선되었습니다.제시된 다른 방법과는 달리, 이 접근법은 swmr 레지스터가 아닌 mwmr 레지스터를 사용한다.

적용들

분산 컴퓨팅에는 공유 스냅샷 ^[1]개체를 사용하여 설계 및/또는 검증을 간소화할 수 있는 몇 가지 알고리즘이 있습니다.그 예로는 제외 문제,^[11]^[12]^[13] 동시 타임스탬프 시스템,^[14] 대략적인 합의,^[15] 무작위^[16]^[17] 합의 및 기타 데이터 ^[18]구조의 대기 없는 구현이 있다.mwmr 스냅샷 객체를 사용하여 원자성 멀티 라이터 멀티 리더 레지스터를 생성할 수도 있습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir (Sep 1993). "Atomic Snapshots of Shared Memory". J. ACM. 40 (4): 873–890. doi:10.1145/153724.153741.
^ ^a ^b Fich, Faith Ellen (2005). "How Hard is It to Take a Snapshot?". SOFSEM 2005: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 3381 (SOFSEM 2005: Theory and Practice of Computer Science ed.). Springer Berlin Heidelberg. pp. 28–37. doi:10.1007/978-3-540-30577-4_3. ISBN 978-3-540-24302-1.
^ Li, Ming; Tromp, John; Vitanyi, Paul M. B. (July 1996). "How to Share Concurrent Wait-free Variables". J. ACM. 43 (4): 723–746. CiteSeerX 10.1.1.56.3236. doi:10.1145/234533.234556.
^ Peterson, Gary L; Burns, James E. (1987). "Concurrent reading while writing ii: the multi-writer case". Foundations of Computer Science, 1987., 28th Annual Symposium on. pp. 383–392.
^ Anderson, James H (1993). "Composite registers". Distributed Computing. 6 (3): 141–154. doi:10.1007/BF02242703.
^ Attiya, Hagit; Helihy, Maurice; Rachman, Ophir (1995). "Atomic snapshots using lattice agreement". Distributed Computing. 8 (3): 121–132. doi:10.1007/BF02242714.
^ Israeli, Amos; Shirazi, Asaf (1992). "Efficient snapshot protocol using 2-lattice agreement". Manuscript.
^ ^a ^b Attiya, Hagit; Rachman, Ophir (April 1998). "Atomic Snapshots in O( n log n ) Operations". SIAM Journal on Computing. 27 (2): 319–340. doi:10.1145/164051.164055.
^ Israeli, Amos; Shaham, Amnon; Shirazi, Asaf (1993). "Linear-time snapshot protocols for unbalanced systems". Distributed Algorithms. Springer. pp. 26–38. doi:10.1007/3-540-57271-6_25. ISBN 978-3-540-57271-8.
^ Inoue, Michiko; Masuzawa, Toshimitsu; Chen, Wei; Tokura, Nobuki (1994). Linear-time snapshot using multi-writer multi-reader registers. Distributed Algorithms. Vol. 857. Springer. pp. 130–140. doi:10.1007/BFb0020429. ISBN 978-3-540-58449-0.
^ Dolev, Danny; Gafni, Eli; Shavit, Nir (1988). "Toward a non-atomic era: l-exclusion as a test case". Proceedings of the twentieth annual ACM symposium on Theory of computing. pp. 78–92.
^ Katseff, Howard P (1978). "A new solution to the critical section problem". Proceedings of the tenth annual ACM symposium on Theory of computing. pp. 86–88.
^ Lamport, Leslie (1988). "The mutual exclusion problem: partII—statement and solutions". Journal of the ACM. 33 (2): 327–348. CiteSeerX 10.1.1.32.9808. doi:10.1145/5383.5385.
^ Dolev, Danny; Shavit, Nir (1989). "Bounded concurrrent time-stamp systems are constructible". Proceedings of the twenty-first annual ACM symposium on Theory of computing. ACM. pp. 454–466.
^ Attiya, Hagit; Lynch, Nancy; Shavit, Nir (1990). "Are wait-free algorithms fast?". Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on. pp. 55–64.
^ Abrahamson, Karl (1988). "On achieving consensus using a shared memory". Proceedings of the seventh annual ACM Symposium on Principles of distributed computing. pp. 291–302.
^ Attiya, Hagit; Dolev, Danny; Shavit, Nir (1989). Bounded polynomial randomized consensus. Proceedings of the eighth annual ACM Symposium on Principles of distributed computing. pp. 281–293.
^ Aspnes, James; Herlihy, Maurice (1990). "Wait-free data structures in the asynchronous PRAM model". Proceedings of the second annual ACM symposium on Parallel algorithms and architectures. ACM. pp. 340–349.

[afek-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir (Sep 1993). "Atomic Snapshots of Shared Memory". J. ACM. 40 (4): 873–890. doi:10.1145/153724.153741.

[fich-hard-2] Fich, Faith Ellen (2005). "How Hard is It to Take a Snapshot?". SOFSEM 2005: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 3381 (SOFSEM 2005: Theory and Practice of Computer Science ed.). Springer Berlin Heidelberg. pp. 28–37. doi:10.1007/978-3-540-30577-4_3. ISBN 978-3-540-24302-1.

[3] Li, Ming; Tromp, John; Vitanyi, Paul M. B. (July 1996). "How to Share Concurrent Wait-free Variables". J. ACM. 43 (4): 723–746. CiteSeerX 10.1.1.56.3236. doi:10.1145/234533.234556.

[4] Peterson, Gary L; Burns, James E. (1987). "Concurrent reading while writing ii: the multi-writer case". Foundations of Computer Science, 1987., 28th Annual Symposium on. pp. 383–392.

[anderson-5] Anderson, James H (1993). "Composite registers". Distributed Computing. 6 (3): 141–154. doi:10.1007/BF02242703.

[6] Attiya, Hagit; Helihy, Maurice; Rachman, Ophir (1995). "Atomic snapshots using lattice agreement". Distributed Computing. 8 (3): 121–132. doi:10.1007/BF02242714.

[7] Israeli, Amos; Shirazi, Asaf (1992). "Efficient snapshot protocol using 2-lattice agreement". Manuscript.

[attiya-nlogn-8] Attiya, Hagit; Rachman, Ophir (April 1998). "Atomic Snapshots in O( n log n ) Operations". SIAM Journal on Computing. 27 (2): 319–340. doi:10.1145/164051.164055.

[9] Israeli, Amos; Shaham, Amnon; Shirazi, Asaf (1993). "Linear-time snapshot protocols for unbalanced systems". Distributed Algorithms. Springer. pp. 26–38. doi:10.1007/3-540-57271-6_25. ISBN 978-3-540-57271-8.

[inoue-10] Inoue, Michiko; Masuzawa, Toshimitsu; Chen, Wei; Tokura, Nobuki (1994). Linear-time snapshot using multi-writer multi-reader registers. Distributed Algorithms. Vol. 857. Springer. pp. 130–140. doi:10.1007/BFb0020429. ISBN 978-3-540-58449-0.

[11] Dolev, Danny; Gafni, Eli; Shavit, Nir (1988). "Toward a non-atomic era: l-exclusion as a test case". Proceedings of the twentieth annual ACM symposium on Theory of computing. pp. 78–92.

[12] Katseff, Howard P (1978). "A new solution to the critical section problem". Proceedings of the tenth annual ACM symposium on Theory of computing. pp. 86–88.

[13] Lamport, Leslie (1988). "The mutual exclusion problem: partII—statement and solutions". Journal of the ACM. 33 (2): 327–348. CiteSeerX 10.1.1.32.9808. doi:10.1145/5383.5385.

[14] Dolev, Danny; Shavit, Nir (1989). "Bounded concurrrent time-stamp systems are constructible". Proceedings of the twenty-first annual ACM symposium on Theory of computing. ACM. pp. 454–466.

[15] Attiya, Hagit; Lynch, Nancy; Shavit, Nir (1990). "Are wait-free algorithms fast?". Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on. pp. 55–64.

[16] Abrahamson, Karl (1988). "On achieving consensus using a shared memory". Proceedings of the seventh annual ACM Symposium on Principles of distributed computing. pp. 291–302.

[17] Attiya, Hagit; Dolev, Danny; Shavit, Nir (1989). Bounded polynomial randomized consensus. Proceedings of the eighth annual ACM Symposium on Principles of distributed computing. pp. 281–293.

[18] Aspnes, James; Herlihy, Maurice (1990). "Wait-free data structures in the asynchronous PRAM model". Proceedings of the second annual ACM symposium on Parallel algorithms and architectures. ACM. pp. 340–349.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Search

공유 스냅샷 개체

네임스페이스

더

목차

일반

실행

기본 swmr 스냅샷 알고리즘

Afek 등에 의한 싱글 라이터 멀티 리더의 실장.

무제한 메모리 기반

한정된 메모리에 근거하다

Feek 등에 의한 멀티 라이터 멀티 리더의 실장.

복잡성

적용들

「」를 참조해 주세요.

레퍼런스

Search

공유 스냅샷 개체

일반

실행

기본 swmr 스냅샷 알고리즘

Afek 등에 의한 싱글 라이터 멀티 리더의 실장.

무제한 메모리 기반

한정된 메모리에 근거하다

Feek 등에 의한 멀티 라이터 멀티 리더의 실장.

복잡성

적용들

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.