2025-11-12T12:19:10.304562

Fair Ordering

Haseeb, Geng, Mittal et al.

A growing class of applications demands \emph{fair ordering/sequencing} of events which ensures that events generated earlier by one client are processed before later events from other clients. However, achieving such sequencing is fundamentally challenging due to the inherent limitations of clock synchronization. We advocate for an approach that embraces, rather than eliminates, clock variability. Instead of attempting to remove error from a timestamp, Tommy, our proposed system, leverages a statistical model to compare two noisy timestamps probabilistically by learning per-clock offset distributions. Our preliminary statistical model computes the probability that one event precedes another w.r.t. the wall-clock time without access to the wall-clock. This serves as a foundation for a new relation: \emph{likely-happened-before} denoted by $\xrightarrow{p}$ where $p$ represents the probability of an event to have happened before another. The $\xrightarrow{p}$ relation provides a basis for ordering multiple events which are otherwise considered \emph{concurrent} by the typical \emph{happened-before} ($\rightarrow$) relation. We highlight various related challenges including intransitivity of $\xrightarrow{p}$ relation as opposed to the transitive $\rightarrow$ relation. We also outline several research directions: online fair sequencing, stochastically fair total ordering, host-level support for fairness and more.

academic

Lamport를 넘어, 확률적 공정 순서화를 향하여

기본 정보

논문 ID: 2510.13664
제목: Beyond Lamport, Towards Probabilistic Fair Ordering
저자: Muhammad Haseeb, Jinkun Geng, Radhika Mittal, Aurojit Panda, Srinivas Narayana, Anirudh Sivaraman
분류: cs.NI (컴퓨터 네트워킹)
발표 시간: 2025년 10월 15일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.13664v1

초록

본 논문은 분산 시스템에서 공정 순서화(fair ordering)의 과제를 다루며, 시계 변동성을 제거하기보다는 수용하는 새로운 접근 방식을 제안합니다. 저자들은 Tommy 시스템을 설계하였으며, 이는 각 시계의 오프셋 분포를 학습하고 통계 모델을 사용하여 노이즈가 있는 타임스탬프를 확률적으로 비교합니다. 핵심 혁신은 "likely-happened-before" 관계( $\xrightarrow{p}$ )를 제안하는 것으로, 여기서 $p$ 는 한 사건이 다른 사건보다 먼저 발생할 확률을 나타냅니다. 이 관계는 전통적인 happened-before 관계( $\rightarrow$ )가 동시적이라고 간주하는 사건들을 순서화할 수 있지만, 비이행성(non-transitivity) 등의 새로운 과제도 야기합니다.

연구 배경 및 동기

1. 문제 정의

분산 시스템의 공정 순서화는 한 클라이언트가 더 일찍 생성한 사건이 다른 클라이언트가 더 늦게 생성한 사건보다 먼저 처리되도록 보장해야 합니다. 이는 금융 거래소, 광고 거래소 등 경쟁적 애플리케이션에서 매우 중요하며, 이러한 애플리케이션들을 통칭하여 "auction-apps"라고 합니다.

2. 문제의 중요성

금융 공정성: 금융 거래에서 메시지 처리 순서는 거래 결과에 직접적인 영향을 미치며, 부공정한 순서화는 막대한 경제적 손실을 초래할 수 있습니다
클라우드 마이그레이션 필요성: 전통적인 금융 거래소는 공정성을 보장하기 위해 전용 인프라를 사용하지만, 공개 클라우드로의 마이그레이션은 새로운 네트워크 원시 연산이 필요합니다
애플리케이션 범위 확대: 금융 거래 외에도 경쟁적 시장, NFT 거래, 한정 상품 구매 등의 시나리오에서 공정 순서화가 필요합니다

3. 기존 방법의 한계

완벽한 시계 동기화 가정: 기존 방안은 거의 완벽한 시계 동기화를 가정하지만, 실제 비동기 네트워크에서는 불가능합니다
특수 인프라 의존성: 전통적 방안은 등길이 케이블, 저지터 스위치 등 전용 하드웨어가 필요합니다
애플리케이션 결합: 일부 방안은 특정 애플리케이션 로직과 밀접하게 결합되어 일반화하기 어렵습니다

4. 근본적 과제

시계 동기화의 기본 제한: 비동기 또는 경계 동기 네트워크에서 $n$ 개 프로세스의 시계 동기화 정확도는 $u(1-1/n)$ 을 초과할 수 없으며, 여기서 $u$ 는 링크 지연의 불확실성을 나타냅니다.

핵심 기여

새로운 관계 정의: likely-happened-before 관계( $\xrightarrow{p}$ )를 제안하여 Lamport의 happened-before 관계를 확장합니다
통계 모델: 시계 오프셋 분포를 기반으로 한 확률적 타임스탬프 비교 방법을 설계합니다
Tommy 시스템: 완벽한 시계 동기화 없이 공정 순서화기의 프로토타입을 구현합니다
이론적 분석: 가우스 분포 하에서 확률 관계의 이행성을 증명합니다
연구 방향: 온라인 공정 순서화, 무작위 공정 전순서 등 여러 연구 방향을 제안합니다

방법론 상세 설명

작업 정의

공정 순서화 정의: 서버가 메시지를 보는 순서는 전지적 관찰자가 관찰한 순서와 동일해야 합니다.

입력: 로컬 타임스탬프가 있는 클라이언트 메시지 스트림 출력: 생성 시간에 따라 공정하게 순서화된 메시지 배치 제약: 전역 시계에 접근할 수 없으며, 최선의 노력 시계 동기화만 사용 가능합니다

모델 아키텍처

1. 시스템 모델

각 클라이언트 $i$ 는 타임스탐프 $T_i$ 가 있는 메시지를 전송합니다
실제 타임스탬프: $T_i^* = T_i + \theta_i$ , 여기서 $\theta_i$ 는 시계 오프셋입니다
오프셋 $\theta_i$ 는 확률 분포 $f_{\theta_i}$ 를 따릅니다

2. 확률 계산

두 사건의 선후 확률: $P(T_i^* < T_j^* | T_i, T_j) = P(\theta_j - \theta_i > T_i - T_j)$

$\Delta\theta = \theta_j - \theta_i \sim f_{\Delta\theta}$ 를 정의하면: $P(T_i^* < T_j^* | T_i, T_j) = \int_{T_i-T_j}^{\infty} f_{\Delta\theta}d\Delta$

3. 가우스 경우의 폐형식 해

독립적인 가우스 분포 오류의 경우: $P(T_i^* < T_j^* | T_i, T_j) = \Phi\left(\frac{T_j-T_i+(\mu_i-\mu_j)}{\sqrt{\sigma_i^2+\sigma_j^2}}\right)$

여기서 $\Phi(x)$ 는 표준 정규 분포의 누적분포함수(CDF)입니다.

4. 임의 분포 처리

클라이언트 학습: 각 클라이언트는 자신의 오프셋 분포 $f_{\theta_i}$ 를 학습합니다
합성곱 계산: 순서화기는 합성곱을 통해 $f_{\Delta\theta}$ 를 계산합니다
FFT 최적화: 고속 푸리에 변환을 사용하여 합성곱 계산을 최적화합니다

기술적 혁신점

1. 확률 관계 구성

메시지를 그래프의 노드로 모델링하고, $\xrightarrow{p}$ 관계를 가중치 $p$ 가 있는 방향 간선으로 표현합니다. 각 노드 쌍에 대해 가중치가 더 높은 간선을 유지합니다.

2. 공정 순서화 알고리즘

이행성 경우: 그래프가 이행적 토너먼트를 형성하여 고유한 위상 정렬이 존재합니다
비이행성 경우: 사이클이 존재할 수 있으므로 간선 삭제 또는 확률 조정이 필요합니다

3. 배치 형성

임계값 $threshold$ 에 따라 배치 경계를 생성합니다:

$i \xrightarrow{p} j$ 이고 $p > threshold$ 인 경우, $i$ 와 $j$ 사이에 배치 경계를 생성합니다
순서를 확신할 수 없는 메시지는 동일 배치에 포함됩니다

4. 온라인 순서화

완전성 보장: 모든 클라이언트가 $t$ 보다 큰 타임스탬프를 가진 메시지를 전송할 때까지 대기합니다
안전 발송: 미래 시간 $T_i^B$ 를 계산하여 $P(T_i^* < T_i^B) > p_{safe}$ 를 만족하도록 합니다

실험 설정

데이터셋

시뮬레이션 환경: 500개 클라이언트, 각각 가우스 시계 오프셋 분포 $\mathcal{N}(\mu, \sigma^2)$ 할당
타임스탬프 생성: 클라이언트는 벽시계 $t$ 를 읽고, 노이즈 $\epsilon$ 을 샘플링하여 메시지를 $T = t + \epsilon$ 으로 표시합니다
기준값 수집: 평가를 위해 기준값 타임스탬프를 수집합니다

평가 지표

순위 일관성 점수(RAS):

올바르게 순서화된 메시지 쌍: +1점
잘못 순서화된 메시지 쌍: -1점
무차별(동일 배치)인 메시지 쌍: 0점

비교 방법

TrueTime 기준선: Spanner TrueTime을 시뮬레이션하여 각 메시지에 불확실성 구간 $[T-3\sigma, T+3\sigma]$ 를 할당하고, 겹치는 구간에 동일 순위를 할당합니다.

구현 세부사항

임계값 설정: $threshold = 0.75$
평가 모드: 오프라인 순서화(모든 메시지 도착 후 순서화)
변수 제어: 시계 오류 표준편차, 메시지 간격

실험 결과

주요 결과

그림 5는 Tommy의 TrueTime 대비 성능을 보여줍니다:

낮은 시계 오류: 두 시스템의 성능이 유사합니다
높은 시계 오류 또는 작은 메시지 간격: Tommy가 TrueTime을 크게 능가합니다
극도로 높은 불확실성: Tommy의 확률적 특성으로 인해 음수 RAS가 발생할 수 있으며, TrueTime은 보수적인 0점을 유지합니다

주요 발견

적응성 우위: Tommy는 시계 동기화 품질이 낮을 때 더 나은 성능을 보입니다
확률성 비용: 높은 불확실성 하에서 잘못된 순서화가 발생할 수 있습니다
임계값 트레이드오프: 임계값 선택은 배치 크기와 공정성 신뢰도에 영향을 미칩니다

이론적 분석

이행성 증명

명제 1: 독립적인 정규 확률변수 $X \sim \mathcal{N}(\mu_X, \sigma_X^2)$ , $Y \sim \mathcal{N}(\mu_Y, \sigma_Y^2)$ , $Z \sim \mathcal{N}(\mu_Z, \sigma_Z^2)$ 에 대해, 선호 관계 $X \succ Y \Leftrightarrow \Pr[X > Y] > \frac{1}{2}$ 를 정의하면, $\succ$ 는 이행적입니다.

증명 요점: $\Pr[A > B] > \frac{1}{2} \Leftrightarrow \mu_A > \mu_B$

평균의 이행성으로 인해 확률 관계도 이행성을 갖습니다.

비이행성 과제

임의 분포의 경우, 이행성이 반드시 성립하지 않으며, $A \succ B$ , $B \succ C$ , $C \succ A$ 의 순환이 발생할 수 있으며, 이는 "보, 바위, 보" 현상과 유사합니다.

향후 연구 방향

1. 관계 특성화

$\xrightarrow{p}$ 관계를 이행적으로 만드는 분포 조건 연구
비이행성을 처리하는 변환 방법 개발

2. 호스트 네트워크 변동성

호스트 데이터 경로 지터가 시계 접근 및 메시지 전송 지연에 미치는 영향 연구

3. 공정 전순서 확장

공정 부분순서를 공정 전순서로 확장하고, 무작위 공정성 메커니즘 연구

4. 시계 오프셋 학습

온도 급변 등 이상 조건을 처리하는 견고한 시계 오프셋 분포 학습 메커니즘 개발

5. 비잔틴 클라이언트

비잔틴 결함 하에서의 공정성 보장 연구 및 타임스탬프 조작 공격 방지

결론 및 토론

주요 결론

개념적 혁신: likely-happened-before 관계는 동시 사건 순서화를 위한 새로운 사고방식을 제공합니다
실용적 가치: Tommy는 실제 시계 동기화 조건에서 전통적 방법보다 우수합니다
이론적 기초: 가우스 분포 하의 이행성은 방법에 이론적 지원을 제공합니다

한계

이행성 가정: 현재 설계는 이행성을 가정하며, 비이행성 경우는 추가 연구가 필요합니다
오프라인 평가: 실험은 오프라인 순서화만 평가하며, 온라인 성능은 검증 필요합니다
분포 가정: 가우스 분포 가정이 모든 실제 시나리오에 적용되지 않을 수 있습니다
비잔틴 결함 허용: 악의적 클라이언트에 대한 방어 메커니즘이 부족합니다

영향력 평가

장점

이론적 기여: 고전적 happened-before 관계를 확장합니다
실용 지향: 클라우드 마이그레이션의 실제 문제를 해결합니다
일반적 프레임워크: 임의의 시계 오프셋 분포를 지원합니다
성능 우위: 실제 조건에서 기존 방법보다 우수합니다

부족한 점

완전성 결여: 비이행성 처리 방안이 충분하지 않습니다
보안 분석 부족: 심층적인 보안 위협 분석이 부족합니다
실험 한계: 시뮬레이션만 있으며 실제 시스템 검증이 부족합니다

적용 시나리오

다중 데이터센터 배포 금융 거래 시스템
공정성에 대한 엄격한 요구사항이 있는 경매 시스템
범용 네트워크 인프라에서 공정 순서화를 구현해야 하는 애플리케이션

연구 가치

본 논문은 확률적 공정 순서화의 개념을 개척적으로 제시하며, 분산 시스템의 공정성 문제에 새로운 해결 방향을 제공합니다. 일부 이론적 및 구현상의 과제가 있지만, 그 핵심 아이디어는 중요한 학술적 가치와 실용적 잠재력을 가지고 있으며, 후속 연구의 기초를 마련합니다.

참고문헌

주요 참고문헌:

Lamport, L. "Time, clocks, and the ordering of events in a distributed system" (고전적 happened-before 관계)
Corbett, J.C. et al. "Spanner: Google's globally distributed database" (TrueTime 메커니즘)
Ghalayini, A. et al. "Cloudex: A fair-access financial exchange in the cloud" (클라우드 거래소 관련 연구)