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

Beyond Lamport, Towards Probabilistic Fair Ordering

基本信息

论文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$ )认为是并发的事件进行排序，但也带来了非传递性等新挑战。

研究背景与动机

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$

由于均值的传递性，概率关系也具有传递性。

研究使 $\xrightarrow{p}$ 关系传递的分布条件
开发处理非传递性的变换方法

概念创新：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" (云交易所相关工作)