들어가며

분산 시스템 설계에 대해 학습하다보면, CAP 정리가 항상 언급되는 것 같습니다.

CAP 정리는 일관성(Consistency), 가용성(Availability), 분할 내성(Partition Tolerance) 세 가지를 동시에 만족할 수 없다는 원칙으로 요약되는데요

이 정리는 2000년 Eric Brewer가 학회 발표에서 처음 제안한 이후, 분산 시스템 설계의 기본 전제로 널리 인용되어 왔습니다.

처음 봤을 땐 그렇구나 하고 넘어갔는데, 계속 등장하니 조금 더 깊은 내용이 궁금해졌습니다.

그래서 이 글에서는 해당 추측을 이론적으로 증명한 논문, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services를 바탕으로 CAP가 어떤 의미인지 정확히 파악해보려고 합니다.

논문의 내용을 단락 단위로 해석하고, 그 의미를 함께 짚어보는 방식으로 살펴보겠습니다.

도입부

Brewer의 추측

At PODC 2000, Brewer, in an invited talk, made the following conjecture: it is impossible for a web service to provide the following three guarantees: consistency, availability, and partition-tolerance.

2000년 PODC 학회에서 Eric Brewer는 웹 서비스가 다음의 세 가지 특성을 동시에 만족시킬 수 없다는 추측을 언급했습니다.

• 일관성 (Consistency)
• 가용성 (Availability)
• 분할 내성 (Partition tolerance)

이 세 가지는 각각의 의미도 중요하지만, 무엇보다 “동시에 만족시킬 수 없다"는 점이 핵심입니다. 처음엔 추측으로 제안된 이 주장은, 지금은 CAP 정리라는 이름으로 잘 알려져 있죠.

그러한 이유로 CAP 정리를 브루어의 정리라고도 부르기도 합니다. 논문은 이 세 가지가 왜 동시에 만족될 수 없는지를 구체적인 모델 위에서 이론적으로 증명합니다.

일관성에 대한 기대

Most web services today attempt to provide strongly consistent data. … (중략) … once a transaction is committed it is permanent (durable).

요약하면, 현실의 웹 서비스는 ACID 트랜잭션을 전제로 강한 일관성을 기본 기대값으로 두고 있다고 볼 수 있습니다.

사용자는 데이터가 중간에 잘렸거나, 쓰기 도중 일부만 반영된 상태를 보는 것을 원하지 않습니다. 쓰기가 완료되었다면 어떤 노드에서 읽더라도 동일한 값을 받을 수 있어야 한다는 기대가 전제되어 있습니다.

이런 이유로 대부분의 시스템은 트랜잭션을 기반으로 한 일관성 보장 메커니즘을 필수 요소로 고려하게 됩니다.

가용성에 대한 기대

Web services are similarly expected to be highly available. … (중략) … The goal of most web services today is to be as available as the network on which they run: if any service on the network is available, then the web service should be accessible.

요약하면, 웹 서비스는 언제든지 요청에 응답할 수 있어야 한다는 기대를 받는다고 정리할 수 있습니다.

서비스 중단은 단순한 불편을 넘어서 실제 피해로 이어질 수 있습니다. 논문에서는 증권 거래 사이트(E-Trade)의 사례를 들어, 서비스가 중요한 시점에 응답하지 못할 경우 법적 문제까지 발생할 수 있다고 설명합니다.

그만큼 가용성은 기술적 요구를 넘어 서비스의 신뢰성과 직접 연결되는 특성입니다.

이 때문에 대부분의 시스템은 네트워크 어딘가에 살아 있는 노드가 있다면, 전체 시스템 역시 반드시 응답할 수 있어야 한다는 전제를 갖고 설계됩니다.

분할 내성에 대한 필요

Finally, on a highly distributed network, it is desirable to provide some amount of fault-tolerance. … (중략) … In this note we will not consider stopping failures, though in some cases a stopping failure can be modeled as a node existing in its own unique component of a partition.

요약하면, 분산 시스템에서는 네트워크 분할 상황에서도 동작을 계속할 수 있는 능력, 즉 분할 내성이 요구된다고 볼 수 있습니다.

노드나 통신 경로에 장애가 발생하는 상황은 실제 시스템에서 흔히 일어납니다. 이때 전체 시스템이 멈추지 않고 가능한 범위 내에서 계속 동작해야 한다는 요구가 생깁니다.

논문에서는 일부 노드나 메시지가 단절된 상황을 “분할(partition)“로 간주하고, 이러한 환경에서도 서비스가 가능한 상태를 유지할 수 있어야 한다는 점을 분할 내성의 핵심으로 설명합니다.

논문에서 정의하는 세 가지 특성

앞에서 소개한 세 가지 특성은 모두 중요하지만, 그 의미가 모호하거나 해석에 따라 다르게 받아들여질 수 있습니다.

따라서 논문에서는 본격적인 증명에 앞서, 이 세 가지 특성을 정확히 어떤 의미로 사용할지를 형식적으로 정의하고 있습니다.

각 정의는 논문 전체에서 사용하는 모델의 핵심 가정이기도 하며, 이후 증명의 기반이 되는 전제 조건으로 작용합니다.

Atomic Data Object

The most natural way of formalizing the idea of a consistent service is as an atomic data object. … (중략) … See [6] for a more complete definition of atomic consistency.

요약하면, Atomic Data Object는 분산된 환경에서도 순차적으로 동작하는 것처럼 보이는 일관성을 모델링한 개념이다라고 이해할 수 있습니다.

논문에서는 일관성을 형식적으로 정의하기 위해 Atomic Data Object를 사용합니다.

이 객체는 **atomic consistency (또는 linearizability)**를 만족해야 하며, 이는 모든 연산이 일관된 전역 순서를 따르는 것처럼 동작함을 의미합니다.

예를 들어, 어떤 쓰기 연산이 완료된 이후 시작된 읽기 연산은 반드시 그 값 또는 그 이후의 값을 반환해야 합니다.

이런 모델은 사용자 입장에서 시스템이 단일 노드처럼 예측 가능하게 동작한다고 느낄 수 있게 해줍니다.

Availability

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. … (중략) … even when severe network failures occur, every request must terminate.

요약하면, 고장나지 않은 노드로 들어온 요청은 반드시 응답을 받아야 한다라고 이해할 수 있습니다.

논문에서는 가용성을 “모든 요청이 언젠가는 응답을 받아야 한다"는 조건으로 정의합니다. 특히 이 정의는 메시지가 유실될 수 있는 환경에서도 요청을 포기하지 않고 처리해야 함을 전제로 하고 있습니다.

이는 단순한 성능 문제가 아니라 시스템이 지속적으로 응답 가능하다는 보장, 즉 실시간으로 동작하는 서비스가 가져야 할 기본 조건으로 제시됩니다.

또한 부분 실패 상황, 예를 들어 다른 모든 노드가 실패하더라도 하나의 노드만 살아 있다면 그 노드는 여전히 요청에 응답할 수 있어야 한다는 점을 강조합니다.

Partition Tolerance

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another. … (중략) … a valid (atomic) response must be generated.

요약하면, 분할 내성은 네트워크 일부가 단절되어도 시스템이 동작을 멈추지 않아야 한다는 특성을 의미한다고 볼 수 있습니다.

논문에서는 네트워크 분할을 모델링하기 위해, 일부 노드 간의 메시지가 영구적으로 손실되는 상황을 허용합니다. 이 경우 시스템은 전체가 멈추는 것이 아니라, 분리된 각 노드가 독립적으로 응답을 계속할 수 있어야 한다는 요구를 받습니다.

분할 내성을 만족하는 시스템은 하나의 노드만 살아 있고 나머지 노드들과 통신할 수 없는 상황에서도, 해당 노드는 자체적으로 요청을 처리하고 응답할 수 있어야 합니다.

이 정의는 논문 전반에서 Partition Tolerance를 ‘메시지 유실이 있는 환경에서의 정상 동작 보장’으로 해석한다는 점에서 중요합니다.

비동기 네트워크에서의 불가능성

논문에서는 본격적인 증명에 앞서 정의한 세 가지 특성이 어떤 조건 하에서 동시에 만족될 수 없는지를 순차적으로 보여줍니다.

이 섹션에서는 먼저 비동기 네트워크 모델에서의 불가능성을 다루고 있으며, 이를 통해 CAP 정리가 단순한 직관이 아니라 논리적으로 증명 가능한 제약임을 밝히고 있습니다.

정리 1: 비동기 모델에서 CAP 불가능성 증명

In the asynchronous model, there is no clock, and nodes must make decisions based only on the messages received and local computation. … (중략) … Theorem 1: It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: Availability, Atomic consistency, in all fair executions (including those in which messages are lost).

요약하면, 비동기 네트워크 모델에서는 가용성과 원자적 일관성을 동시에 만족하는 읽기/쓰기 객체를 구현할 수 없다는 것이 이 정리의 핵심입니다.

논문에서 사용하는 비동기 네트워크 모델은 다음과 같은 특징을 가집니다.

• 시스템에는 전역 시계가 없음
• 노드는 수신한 메시지와 로컬 상태만으로 동작을 결정
• 메시지는 유실될 수 있고, 언제 도착할지 보장되지 않음

이러한 조건 아래에서, 논문은 쓰기 연산이 완료된 후에도 일부 노드가 이전 값을 반환하는 상황이 발생할 수 있음을 보여줍니다.

sequenceDiagram
    participant Client
    participant G1 as 노드 G1
    participant G2 as 노드 G2

    Note over G1, G2: 초기 상태: v₀ (G1 = v₀, G2 = v₀)

    Client->>G1: 쓰기 요청 (v₁)
    G1->>G1: v₁ 저장
    G1-->>Client: 쓰기 완료 응답

    G1-xG2: 메시지 유실 (v₁ 전달 실패)

    Client->>G2: 읽기 요청
    G2-->>Client: v₀ 반환

1. 노드 G1에서 쓰기 연산이 완료
2. G1과 G2 사이의 네트워크가 분할되어, G2는 그 값을 전달받지 못함
3. 이후 클라이언트가 G2에 읽기 요청을 보냄
4. G2는 여전히 초기 값을 반환

이 상황에서 시스템은 가용성을 만족하기 위해 G2의 요청에 응답하지만, 그 결과 일관성이 깨지는 응답을 줄 수밖에 없다는 모순이 발생합니다.

이를 통해 CAP 정리에서 말하는 세 가지 특성이 왜 동시에 만족될 수 없는지를, 수학적 모델을 통해 명확히 보여주는 출발점이 됩니다.

따름정리 1.1: 메시지 유실 여부를 판단할 수 없는 상황

Corollary 1.1: It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: Availability, in all fair executions, and Atomic consistency, in fair executions in which no messages are lost.

요약하면, 메시지가 유실되지 않는 경우에도 가용성과 원자적 일관성을 동시에 만족하는 시스템은 구현할 수 없다는 것이 이 따름정리의 핵심입니다.

정리 1에서는 메시지 유실이 가능한 상황을 통해 모순을 구성했지만, Corollary 1.1에서는 메시지가 유실되지 않는 경우만 고려하더라도 동일한 모순이 발생함을 강조합니다.

그 이유는 비동기 모델에서는 메시지가 단순히 지연된 것인지, 실제로 유실된 것인지 시스템이 구분할 수 없기 때문입니다.

sequenceDiagram
    participant Client
    participant G1 as 노드 G1
    participant G2 as 노드 G2

    Note over G1, G2: 초기 상태: v₀ (G1 = v₀, G2 = v₀)

    Client->>G1: 쓰기 요청 (v₁)
    G1->>G1: v₁ 저장
    G1-->>Client: 쓰기 완료 응답

    Client->>G2: 읽기 요청
    G2-->>Client: v₀ 반환
    
    G1->>G2: 메시지 수신
    G2->>G2: v₁ 저장

위 상황은 G1의 메시지가 클라이언트가 G2에게 보내는 요청 보다 빨리 도달했을 때를 가정해봤습니다.

이처럼 메시지가 유실되지 않았더라도, 노드는 언제까지 기다려야 할지 알 수 없고, 결국 같은 방식의 일관성 위반이 발생하게 됩니다.

이 따름정리는 비동기 모델에서의 정보 부족의 한계를 명확히 드러냅니다. 즉, 유실 여부를 알 수 없다는 사실 하나만으로도, 어떤 실행에서는 일관성을 만족시키는 것이 불가능해질 수 있습니다.

논문에서는 완전한 비동기 환경이라면 노드가 메시지가 지연되는지, 유실되었는지 판단할 수 없기 때문에 메시지가 유실되지 않는 경우 가용성과 원자적 일관성을 동시에 만족한다는 의미는 결과적으로 모든 상황(유실, 지연)에 가용성과 원자적 일관성을 동시에 만족하는 상황이라고 강조합니다.

비동기 모델에서의 현실적인 조합

앞서 정리 1과 따름정리 1.1을 통해,
비동기 네트워크에서는 Atomic consistency, Availability, Partition tolerance를 동시에 만족하는 것이 불가능하다는 점이 증명되었습니다.

하지만 세 가지를 모두 만족할 수 없다면, 그중 두 가지 조합은 실현 가능할 수 있음을 언급하며, 이를 다음과 같이 세 가지 조합으로 구분하고, 각각 어떤 상황에서 가능한지를 간단한 모델을 통해 설명합니다.

이때 사용되는 “Atomic"은 앞서 정의한 atomic consistency, 즉 선형화 가능한 일관성을 의미합니다.

Atomic + Available

If partition-tolerance is not required, then atomicity and availability are easy to guarantee. … (중략) … This technique only works if the centralized node is always accessible.

요약하면, Partition tolerance를 포기하면 atomic consistency와 availability는 함께 보장할 수 있습니다.

이 조합은 Partition tolerance를 전제하지 않는 경우에 가능합니다.

즉, 네트워크가 항상 안정적이며, 노드 간 통신이 절대 실패하지 않는 환경이라면 atomic consistency와 availability를 동시에 만족하는 시스템을 구현할 수 있습니다.

논문에서는 이러한 조건 아래에서 중앙 집중형 알고리즘을 통해 모든 요청을 직렬화하고, 실패가 없는 한 모든 요청에 응답할 수 있는 구조를 예시로 제시합니다.

다만 Partition tolerance가 없는 분산 시스템은 현실적으로 성립하기 어렵기 때문에, 이 조합은 제한된 환경(예: 단일 데이터센터, LAN 등)에서만 현실적으로 가능하다는 점도 강조하고 있습니다.

Available + Partition Tolerant

It is possible to provide high availability and partition tolerance, if atomic consistency is not required. … (중략) … Web caches are one example of a weakly consistent network.

요약하면, atomic consistency를 포기하면 availability와 partition tolerance는 동시에 만족할 수 있습니다.

이 조합은 시스템이 항상 응답 가능해야 하면서도, 네트워크 분할 상황에서도 멈추지 않고 동작해야 할 때 선택할 수 있습니다. 대신 모든 노드가 동일한 시점의 값을 보장하는 일관성은 포기해야 합니다.

논문에서는 이 조합을 만족시키는 극단적인 예로, 모든 읽기 요청에 초기값 v₀만을 반환하는 시스템을 제시합니다.

이 경우 일관성은 없지만, 어떤 상황에서도 요청은 처리됩니다.

실제로는 이보다는 **약한 일관성(weak consistency)**을 부분적으로 유지하면서, 가능한 한 최신 데이터를 반환하려는 구조들이 현실적인 선택지로 사용됩니다.

• 이러한 접근은 이후 논문에서 다루는 약한 일관성과 지연된 일관성 개념으로 이어집니다.

Atomic + Partition Tolerant

If availability is not required, then it is easy to achieve atomic data and partition tolerance. … (중략) … If there are no failures, then liveness is guaranteed.

요약하면, 가용성을 포기하면 atomic consistency와 partition tolerance는 동시에 만족시킬 수 있습니다.

이 조합은 Availability를 포기한 경우에 가능합니다. 시스템이 일관성과 분할 내성을 만족해야 한다면, 일부 요청에 대해서는 응답하지 않아도 되는 상황을 허용해야 합니다.

논문에서는 중앙 집중형 알고리즘을 예로 들며 이 조합이 어떻게 성립하는지를 설명합니다.

요청을 받은 노드는 중앙 노드에 메시지를 전송하고, 중앙 노드로부터 응답을 받은 뒤에야 클라이언트에 응답합니다. 하지만 네트워크 분할로 인해 중앙 노드와 통신이 불가능한 경우, 클라이언트 요청에 대한 응답은 무한히 지연되거나 아예 실패할 수 있습니다.

이 방식은 모든 메시지가 정상적으로 전달된다면 시스템은 응답 가능하지만, 분할이 발생하는 실행에서는 일관성을 보존하기 위해 가용성을 희생하게 됩니다.

부분 동기 모델에서의 논의

비동기 네트워크에서는 CAP 세 가지를 동시에 만족할 수 없다는 점이 증명되었지만, 현실의 시스템은 대부분 완전히 비동기적이지는 않습니다.

일정 시간 안에 메시지가 도달하거나, 노드가 타임아웃을 기준으로 동작을 조정하는 식의 부분적인 동기성이 존재합니다.

논문에서는 이러한 현실적인 조건을 반영한 **부분 동기 네트워크 모델(partially synchronous model)**을 도입하여, 이 환경에서도 여전히 불가능한 것이 무엇인지 분석합니다.

정리 2: 시계가 있어도 해결되지 않는 모순

Theorem 2: It is impossible in the partially synchronous network model to implement a read/write data object that guarantees the following properties: Availability and Atomic consistency.

요약하면, 부분 동기 모델에서도 Availability와 Atomic consistency는 동시에 만족시킬 수 없습니다.

이 정리는 분산 시스템의 각 노드가 시계를 가지고 있고, 메시지가 일정 시간 내에 도착하거나 유실된다는 조건이 주어진 상황에서도 앞서와 같은 모순이 여전히 발생함을 보여줍니다.

논문에서는 G1에서 쓰기 연산이 완료된 뒤 충분한 시간이 흐른 후, G2에서 읽기 연산이 수행되는 시나리오를 구성합니다.

sequenceDiagram
    participant Client
    participant G1 as 노드 G1
    participant G2 as 노드 G2

    Note over G1, G2: 초기 상태: G1 = v₀, G2 = v₀

    rect rgba(0, 200, 0, 0.05)
    Note over G1: 쓰기 연산 α₁
    Client->>G1: 쓰기 요청 (v₁)
    G1->>G1: v₁ 저장
    G1-->>Client: 쓰기 완료
    end

    G1-xG2: 메시지 손실 (v₁ 미전달)

    rect rgba(255, 255, 0, 0.1)
    Note over G1, G2: α₁ 이후 충분한 시간 간격 (α′₂)
    end

    rect rgba(0, 200, 0, 0.05)
    Note over G2: 읽기 연산 α₂
    Client->>G2: 읽기 요청
    G2-->>Client: v₀ 반환 (최신 값 아님)
    end

1. G1에서 쓰기 연산 α₁이 발생하여 v₁을 저장
2. G1과 G2 사이의 메시지는 손실됨
3. α₁ 이후 충분한 시간 간격(α′₂)이 존재함
4. G2에서 읽기 연산 α₂가 발생하지만, 여전히 v₀을 반환 (최신 값을 알 수 없음)
5. G2는 가용성을 만족하기 위해 응답하지만, 일관성을 위반

이때 메시지가 손실된 경우, 읽기는 여전히 이전 값을 반환할 수밖에 없고, 이는 일관성 위반이 됩니다.

즉, 타임아웃을 통해 메시지 유실 여부를 추론할 수 있다 하더라도 CAP 세 가지를 동시에 만족시키는 것은 여전히 불가능하다는 점을 이 정리를 통해 강조합니다.

네트워크 안정 시 가능해지는 조건적 보장

While it is not possible to implement an atomic read/write register in the partially synchronous model, if availability is required, it is still possible to implement such an object if atomicity is required only in executions in which all messages are delivered.

요약하면, 부분 동기 모델에서도 모든 메시지가 전달되는 실행에 대해서는 atomic consistency를 만족할 수 있습니다.

정리 2에서는 가용성과 일관성을 동시에 보장하는 것이 불가능하다고 했지만, 그 불가능은 모든 실행에 대해 동시에 만족시킬 수 없다는 의미입니다.

만약 시스템이 일관성을 제공해야 하는 상황을 “모든 메시지가 eventually 전달되는 실행"으로 한정한다면,그 범위 안에서는 atomicity를 구현하는 것이 가능합니다.

논문에서는 중앙 집중형 알고리즘을 예로 들어 이 가능성을 설명합니다.

flowchart TD
    Client[클라이언트] --> A[로컬 노드 A]
    A --> C[중앙 노드 C]
    C --> A
    A --> Client
    C --> N1[다른 노드 1]
    C --> N2[다른 노드 2]
    C --> N3[다른 노드 3]

    style C fill:#fdf6b2,stroke:#e0c000,stroke-width:2px
    style A fill:#e0f7fa,stroke:#00acc1,stroke-width:1px
    style Client fill:#eeeeee,stroke:#aaaaaa

요청은 중앙 노드로 전달되고, 중앙 노드가 이를 직렬화하여 처리하는 구조로, 네트워크가 안정적이라면 모든 요청은 eventually 수락되고, 그 결과는 atomic하게 보장될 수 있습니다.

이 조건부 보장은 완전한 불가능을 대체하지는 않지만, 현실적인 시스템 설계에서 atomicity를 제한적으로라도 달성할 수 있는 여지를 제공한다는 점에서 의미가 있습니다.

약한 일관성 조건

앞서 살펴본 바와 같이, 네트워크가 비동기적이거나 분할 상황이 존재한다면 원자적 일관성과 가용성, 분할 내성을 동시에 만족하는 것은 불가능합니다.

이러한 제약을 인정하면서도 시스템이 제공하는 응답의 품질을 통제하기 위해, 논문은 이 섹션에서 일관성을 약화시키되, 그 조건을 형식적으로 정의하는 모델을 제안합니다.

이 모델은 Delayed-t Consistency라고 불리며, 약한 일관성 조건을 시간 기반으로 규정합니다.

완전한 일관성을 항상 보장할 수 없는 상황

While it is useful to guarantee that atomic data will be returned in executions in which all messages are delivered (within some time bound), it is equally important to specify what happens in executions in which some of the messages are lost.

요약하면, 모든 메시지가 도달하는 경우만 고려해서는 충분하지 않으며, 메시지가 유실되는 실행에서는 어떤 값이 반환될 수 있는지도 명시해야 합니다.

앞서 정리 1과 정리 2에서는, 비동기 및 부분 동기 네트워크 모델에서 atomic consistency와 availability를 동시에 만족할 수 없음을 보였습니다.

그렇다고 해서 메시지가 유실되거나 지연되는 상황에서 시스템이 무조건 응답을 중단하거나, 무의미한 값을 반환하도록 내버려 둘 수는 없습니다.

논문은 이 지점에서 **“약한 일관성 조건(weaker consistency conditions)”**이라는 방향을 제시합니다. 즉, 메시지 유실이 존재하는 환경에서도 응답 값이 지켜야 할 최소한의 일관성 조건을 형식적으로 정의하는 방법을 제안하는 것입니다.

Delayed-t Consistency란?

This consistency model ensures that if messages are delivered, then eventually some notion of atomicity is restored.

요약하면, 일정 시간 동안 메시지가 안정적으로 전달된다면, 그 이후에는 atomic consistency가 다시 보장되어야 한다는 모델입니다.

이 일관성 모델은 다음과 같은 전제를 가집니다.

• 네트워크가 일시적으로 분할되거나 메시지가 손실될 수는 있지만,
• 일정 시간 t 이상 메시지 손실이 발생하지 않는 구간이 존재한다면,
• 그 구간 이후부터는 시스템이 다시 원자적(atomic)인 응답을 보장해야함

논문에서는 이를 Delayed-t Consistency라고 정의하고, 그 조건을 만족하는 실행에 대해 어떤 순서 보장과 응답 품질이 필요한지를 형식적으로 정의합니다.

이 모델은 완전한 atomic consistency를 제공하지는 않지만, 네트워크가 회복된 뒤 일정 시간이 지나면 다시 강한 일관성이 회복됨을 보장합니다.

이는 eventually consistent 시스템보다 더 구체적이며, “언젠가 일관성이 회복된다”가 아니라 “정해진 시간 이후에는 반드시 회복된다“는 점에서 의미 있는 차이가 있습니다.

Definition 3: Delayed-t Consistency의 형식적 정의

*Definition 3: A timed execution, α, of a read-write object is Delayed-t Consistent if:

1. P is a partial order that orders all write operations, and orders all read operations with respect to the write operations.
2. The value returned by every read operation is exactly the one written by the previous write operation in P (or the initial value, if there is no such previous write in P).
3. The order in P is consistent with the order of read and write requests submitted at each node.
4. (Atomicity) If all messages in the execution are delivered, and an operation θ completes before an operation φ begins, then φ does not precede θ in the partial order P.
5. (Weakly Consistent) Assume there exists an interval of time longer than t in which no messages are lost. Further, assume an operation, θ, completes before the interval begins, and another operation, φ, begins after the interval ends. Then φ does not precede θ in the partial order P.*

요약하면, Delayed-t Consistency는 메시지 유실이 없는 일정 시간(t) 이후부터는 연산 순서가 atomic consistency에 부합하도록 제한되는 일관성 모델입니다.

각 조건의 의미는 다음과 같습니다.

1. P는 모든 쓰기 연산을 순서화하고, 읽기 연산은 그에 대해 순서화되어야 한다.
→ 전체 실행을 정렬하는 하나의 순서가 있으며, 읽기/쓰기 간 순서 관계를 명확히 정의합니다.

2. 모든 읽기는 순서상 가장 가까운 직전 쓰기 값(또는 초기값)을 반환해야 한다.
→ 읽기가 이전 쓰기를 반드시 반영해야 함을 요구합니다.

3. 각 노드 내의 연산 순서는 부분 순서 P와 일치해야 한다.
→ 단일 노드 기준으로 볼 때, 로컬에서 일어난 순서는 전역 순서와 모순되지 않아야 합니다.

4. (Atomicity 조건)
→ 메시지가 유실되지 않은 실행에서, 어떤 연산 θ가 φ보다 먼저 끝났다면 φ는 절대 θ보다 앞선 순서에 위치할 수 없습니다. (순서가 뒤집히지 않아야 함)

5. (약한 일관성 조건)
→ 메시지 유실이 없는 구간이 t 이상 존재하고, 그 구간 이전에 끝난 연산 θ와 구간 이후 시작된 연산 φ가 있다면 φ는 θ보다 먼저 일어난 것처럼 간주되어서는 안 됩니다. 즉, 네트워크가 안정된 이후에는 순서를 지키라는 조건입니다.

이 정의는 단순히 “eventually consistency”처럼 막연하게 일관성이 회복된다고 말하는 것이 아니라, 일관성 회복의 조건(시간, 순서, 메시지 전파 범위)을 명시적으로 제한하는 점에서 현실적인 구현 기준이 됩니다.

설계 가능성: 중앙 집중형 알고리즘 설명

A variant of the centralized algorithm described in Section 4.3 is Delayed-t consistent. Assume node C is the centralized node. The algorithm behaves as follows: …

요약하면, 논문은 Definition 3을 만족하는 구조로 중앙 집중형 알고리즘의 변형을 제시합니다.

이 알고리즘은 기존의 중앙 집중형 모델을 기반으로 하되, 시간 기반 메시지 처리와 타임아웃에 따른 보조 흐름을 추가한 구조입니다.

sequenceDiagram
participant Client
participant A as 로컬 노드 A
participant C as 중앙 노드 C
participant N1 as 다른 노드

%% 쓰기 요청 처리 흐름
Client->>A: 쓰기 요청 (v₁)
A->>C: 중앙 노드에 전달
C->>C: v₁ 저장, 시퀀스 번호 증가
C->>A: 응답
A->>Client: 쓰기 응답
C->>N1: v₁ 전파

%% 메시지 유실 시 타임아웃 처리
Note over C,N1: 메시지 손실 시 C는 일정 시간 내 재전송 시도

• 쓰기 요청 처리

  1. 노드 A가 중앙 노드 C에 새로운 값을 보냄
  2. C는 시퀀스 번호를 증가시키고 값을 저장
  3. C는 모든 노드에 값을 전파
  4. 메시지 유실이 의심되면 C는 t−2×timeout 시간 안에 재전송을 수행

• 읽기 요청 처리

  1. 노드 A는 C에 현재 값을 요청
  2. 응답이 정상적으로 오면 그 값을 클라이언트에 전달
  3. 응답이 없으면, 로컬에 저장된 가장 최신 값(또는 초기값)을 반환

이 구조는 메시지가 도달하지 않더라도 가용성(응답)을 보장하면서, 네트워크가 안정된 이후에는 atomic consistency로 회복되는 설계입니다.

Theorem 4: 이 알고리즘은 정의를 만족함

Theorem 4: The modified centralized algorithm is Delayed-t consistent.

요약하면, 앞서 설명한 중앙 집중형 알고리즘은 Delayed-t Consistency의 다섯 가지 조건을 모두 만족한다. 입니다.

논문은 Definition 3에서 제시한 일관성 조건들을 하나씩 검토하며, 해당 알고리즘이 그것들을 모두 충족함을 논리적으로 설명합니다.

1. 부분 순서(P) 정의
   • 중앙 노드 C가 모든 쓰기 요청에 시퀀스 번호를 부여하므로, 연산 간 전역 순서가 정해짐
2. 읽기 연산은 이전 쓰기 값을 반환
   • 각 읽기는 로컬 또는 중앙 노드로부터 가장 최근의 쓰기 값을 참조
3. 로컬 순서와 부분 순서의 일치
   • 각 노드는 자신의 연산 순서를 전역 순서와 동일하게 유지
4. 모든 메시지가 전달되는 실행에서 atomic consistency 보장
   • C가 직렬화하고 모든 노드에 전파하므로, 메시지 손실이 없는 경우에는 원자성을 만족
5. 메시지 유실 없는 시간 구간 이후 순서 보장
   • 일정 시간(t) 동안 모든 메시지가 전달되면, 그 이후 연산은 앞선 연산을 순서상 앞서지 않도록 설계

이로써 Delayed-t Consistency는 단순한 이론적 모델이 아니라, 구체적인 알고리즘을 통해 구현 가능하고 증명 가능한 약한 일관성 조건이라는 점이 논리적으로 뒷받침됩니다.

마무리

CAP 정리는 세 가지 특성을 모두 만족할 수 없다는 이야기로 자주 소개되지만, 이 논문을 통해 그 제약이 단순한 경험법칙이 아니라 모델과 조건이 주어졌을 때 논리적으로 증명 가능한 것임을 알 수 있었습니다. 논문에서 논리로만 설명할 줄은 몰랐네요😂

정리에 따르면 비동기나 부분 동기 네트워크에서는 일관성과 가용성을 동시에 만족시키는 것이 원칙적으로 불가능하고, 이런 한계를 어떻게 받아들이고 설계할 것인지는 시스템마다 다를 수밖에 없다는 것을 강조하고 있습니다.

논문에서 제시한 Delayed-t Consistency는 일관성을 완전히 포기하는 대신, 메시지 손실이 없는 구간 이후에는 다시 원자성을 회복할 수 있도록 제한하는 방식이 인상적이었습니다.

정리하면서 CAP에 대해 그동안 놓치고 있었던 부분을 정리할 수 있어 좋았네요, 비슷한 고민을 하신 분께도 조금은 도움이 되었으면 합니다.

끝까지 읽어주셔서 감사합니다.😊