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

ما وراء لامبورت، نحو الترتيب العادل الاحتمالي

المعلومات الأساسية

  • معرّف الورقة: 2510.13664
  • العنوان: Beyond Lamport, Towards Probabilistic Fair Ordering
  • المؤلفون: Muhammad Haseeb, Jinkun Geng, Radhika Mittal, Aurojit Panda, Srinivas Narayana, Anirudh Sivaraman
  • التصنيف: cs.NI (شبكات الحاسوب)
  • تاريخ النشر: 15 أكتوبر 2025 (نسخة أولية على arXiv)
  • رابط الورقة: https://arxiv.org/abs/2510.13664v1

الملخص

تتناول هذه الورقة تحديات الترتيب العادل (fair ordering) في الأنظمة الموزعة، وتقترح نهجاً جديداً يتقبل بدلاً من القضاء على تباين الساعات. يقدم المؤلفون نظام Tommy، الذي يتعلم توزيع الانحراف لكل ساعة ويستخدم نماذج إحصائية لإجراء مقارنات احتمالية للطوابع الزمنية المشوشة. الابتكار الأساسي هو تقديم علاقة "likely-happened-before" (→p\xrightarrow{p})، حيث يمثل pp احتمالية حدوث حدث قبل آخر. تتمكن هذه العلاقة من ترتيب الأحداث التي تعتبرها العلاقة التقليدية happened-before (→\rightarrow) متزامنة، لكنها تجلب تحديات جديدة مثل عدم التعدية.

خلفية البحث والدافع

1. تعريف المشكلة

يتطلب الترتيب العادل في الأنظمة الموزعة ضمان معالجة الأحداث التي ينشئها عميل واحد في وقت مبكر قبل الأحداث التي ينشئها عملاء آخرون في وقت متأخر. هذا أمر حاسم في التطبيقات التنافسية مثل البورصات المالية وبورصات الإعلانات، والمعروفة باسم "تطبيقات المزاد" (auction-apps).

2. أهمية المشكلة

  • العدالة المالية: في المعاملات المالية، يؤثر ترتيب معالجة الرسائل بشكل مباشر على نتائج التداول، والترتيب غير العادل قد يؤدي إلى خسائر اقتصادية ضخمة
  • متطلبات الهجرة السحابية: تستخدم البورصات المالية التقليدية بنية تحتية متخصصة لضمان العدالة، لكن الهجرة إلى السحابة العامة تتطلب بدائيات شبكة جديدة
  • توسع نطاق التطبيقات: بالإضافة إلى التداول المالي، تحتاج الأسواق التنافسية وتداول NFT والتسابق على السلع المحدودة إلى ترتيب عادل

3. قيود الطرق الموجودة

  • افتراض مزامنة الساعات المثالية: تفترض الحلول الموجودة مزامنة ساعات قريبة من المثالية، وهو غير عملي في الشبكات غير المتزامنة الفعلية
  • الاعتماد على البنية التحتية الخاصة: تتطلب الحلول التقليدية كابلات متساوية الطول ومفاتيح منخفضة الرجفة وأجهزة متخصصة أخرى
  • الاقتران بالتطبيق: تتشابك بعض الحلول بشكل وثيق مع منطق التطبيق المحدد، مما يصعب تعميمها

4. التحديات الأساسية

القيود الأساسية لمزامنة الساعات: في الشبكات غير المتزامنة أو ذات المزامنة المحدودة، لا يمكن أن تتجاوز دقة مزامنة الساعات لـ nn عملية u(1−1/n)u(1-1/n)، حيث يمثل uu عدم اليقين في تأخير الارتباط.

المساهمات الأساسية

  1. تعريف علاقة جديدة: تقديم علاقة likely-happened-before (→p\xrightarrow{p})، وتوسيع علاقة Lamport الكلاسيكية
  2. نموذج إحصائي: تصميم طريقة مقارنة طوابع زمنية احتمالية بناءً على توزيع انحراف الساعة
  3. نظام Tommy: تنفيذ نموذج أولي لمرتب عادل بدون الحاجة إلى مزامنة ساعات مثالية
  4. تحليل نظري: إثبات التعدية للعلاقات الاحتمالية تحت التوزيع الغاوسي
  5. اتجاهات البحث: اقتراح اتجاهات بحثية متعددة مثل الترتيب العادل عبر الإنترنت والترتيب الكامل العادل العشوائي

شرح الطريقة

تعريف المهمة

تعريف الترتيب العادل: يجب أن يكون ترتيب الرسائل الذي يراه الخادم مطابقاً للترتيب الذي يلاحظه مراقب عالم الكل.

الإدخال: تدفق رسائل العميل مع طوابع زمنية محلية الإخراج: دفعات رسائل مرتبة بشكل عادل حسب وقت الإنشاء القيود: لا يمكن الوصول إلى ساعة عالمية، ويمكن فقط استخدام مزامنة ساعات بأفضل جهد

معمارية النموذج

1. نموذج النظام

  • يرسل كل عميل ii رسالة بطابع زمني TiT_i
  • الطابع الزمني الحقيقي: Ti∗=Ti+θiT_i^* = T_i + \theta_i، حيث θi\theta_i هو انحراف الساعة
  • يتبع الانحراف θi\theta_i توزيع احتمالي fθif_{\theta_i}

2. الحساب الاحتمالي

احتمالية تسلسل حدثين: P(Ti∗<Tj∗∣Ti,Tj)=P(θj−θi>Ti−Tj)P(T_i^* < T_j^* | T_i, T_j) = P(\theta_j - \theta_i > T_i - T_j)

تعريف Δθ=θj−θi∼fΔθ\Delta\theta = \theta_j - \theta_i \sim f_{\Delta\theta}، إذن: P(Ti∗<Tj∗∣Ti,Tj)=∫Ti−Tj∞fΔθdΔP(T_i^* < T_j^* | T_i, T_j) = \int_{T_i-T_j}^{\infty} f_{\Delta\theta}d\Delta

3. الحل المغلق للحالة الغاوسية

للأخطاء الموزعة بشكل غاوسي مستقل: P(Ti∗<Tj∗∣Ti,Tj)=Φ(Tj−Ti+(μi−μj)σi2+σj2)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)

حيث Φ(x)\Phi(x) هي دالة التوزيع التراكمي للتوزيع الطبيعي المعياري.

4. معالجة التوزيعات العشوائية

  • تعلم العميل: يتعلم كل عميل توزيع انحرافه الخاص fθif_{\theta_i}
  • حساب الالتفاف: يحسب المرتب fΔθf_{\Delta\theta} من خلال الالتفاف
  • تحسين FFT: استخدام تحويل فورييه السريع لتحسين حساب الالتفاف

نقاط الابتكار التقني

1. بناء العلاقة الاحتمالية

نمذجة الرسائل كعقد في رسم بياني، مع علاقات →p\xrightarrow{p} كحواف موجهة مرجحة بـ pp. للحفاظ على الحافة ذات الوزن الأعلى لكل زوج عقد.

2. خوارزمية الترتيب العادل

  • حالة التعدية: يشكل الرسم البياني بطولة انتقالية، مع وجود ترتيب طوبولوجي فريد
  • حالة عدم التعدية: قد توجد حلقات، تتطلب حذف الحواف أو تعديل احتمالي

3. تشكيل الدفعات

إنشاء حدود الدفعات وفقاً لحد عتبة thresholdthreshold:

  • إذا كان i→pji \xrightarrow{p} j و p>thresholdp > threshold، ثم إنشاء حد دفعة بين ii و jj
  • تُدرج الرسائل التي لا يمكن ترتيبها بثقة في نفس الدفعة

4. الترتيب عبر الإنترنت

  • ضمان الاكتمال: انتظار جميع العملاء لإرسال طوابع زمنية أكبر من tt
  • الإطلاق الآمن: حساب الوقت المستقبلي TiBT_i^B بحيث P(Ti∗<TiB)>psafeP(T_i^* < T_i^B) > p_{safe}

إعداد التجارب

مجموعة البيانات

  • البيئة المحاكاة: 500 عميل، لكل منها توزيع انحراف ساعة غاوسي مخصص N(μ,σ2)\mathcal{N}(\mu, \sigma^2)
  • توليد الطوابع الزمنية: يقرأ العميل ساعة الحائط tt، ويأخذ عينة من الضوضاء ϵ\epsilon، ويضع علامة على الرسالة بـ T=t+ϵT = t + \epsilon
  • جمع الحقيقة الأرضية: جمع طوابع زمنية حقيقية للتقييم

مقاييس التقييم

درجة اتساق الترتيب (RAS):

  • أزواج الرسائل المرتبة بشكل صحيح: +1 نقطة
  • أزواج الرسائل المرتبة بشكل غير صحيح: -1 نقطة
  • أزواج غير محددة (في نفس الدفعة): 0 نقطة

طرق المقارنة

خط أساس TrueTime: محاكاة TrueTime من Spanner، حيث يتم تخصيص فترة عدم يقين [T−3σ,T+3σ][T-3\sigma, T+3\sigma] لكل رسالة، مع تخصيص نفس الترتيب للفترات المتداخلة.

تفاصيل التنفيذ

  • إعداد الحد: threshold=0.75threshold = 0.75
  • وضع التقييم: الترتيب غير المتصل (ترتيب بعد وصول جميع الرسائل)
  • التحكم في المتغيرات: انحراف الساعة المعياري، الفاصل الزمني بين الرسائل

نتائج التجارب

النتائج الرئيسية

يوضح الشكل 5 أداء Tommy مقابل TrueTime:

  • انحراف ساعة منخفض: أداء النظامين متشابهة
  • انحراف ساعة عالي أو فاصل زمني صغير بين الرسائل: يتفوق Tommy بشكل كبير على TrueTime
  • عدم يقين عالي جداً: قد تؤدي الطبيعة الاحتمالية لـ Tommy إلى RAS سالب، بينما يحافظ TrueTime على 0 محافظ

النتائج الرئيسية

  1. ميزة التكيف: يؤدي Tommy بشكل أفضل عندما تكون جودة مزامنة الساعة أسوأ
  2. تكلفة الاحتمالية: قد يؤدي عدم اليقين العالي إلى ترتيب خاطئ
  3. مقايضة الحد: يؤثر اختيار الحد على حجم الدفعة وثقة العدالة

الأعمال ذات الصلة

البورصات السحابية

  • Onyx: مرتب WFO يفترض أن خطأ مزامنة الساعة مهمل
  • CloudEx و DBO: بورصات مالية للبيئات السحابية، لكنها تعتمد على افتراضات قوية

البورصات التقليدية

استخدام حلول هندسية مع كابلات متساوية الطول ومفاتيح منخفضة الرجفة، حيث يعادل معالجة ترتيب الوصول ترتيب وقت الإنشاء.

التسامح مع الأخطاء البيزنطية

Pompe: آلية إجماع تحد من تأثير العقد البيزنطية على ترتيب الأحداث، لكنها لا تفرض الترتيب العادل.

التحليل النظري

إثبات التعدية

الاقتراح 1: لمتغيرات عشوائية طبيعية مستقلة X∼N(μX,σX2)X \sim \mathcal{N}(\mu_X, \sigma_X^2)، Y∼N(μY,σY2)Y \sim \mathcal{N}(\mu_Y, \sigma_Y^2)، Z∼N(μZ,σZ2)Z \sim \mathcal{N}(\mu_Z, \sigma_Z^2)، تعريف علاقة التفضيل X≻Y⇔Pr⁡[X>Y]>12X \succ Y \Leftrightarrow \Pr[X > Y] > \frac{1}{2}، فإن ≻\succ متعدية.

نقاط الإثبات: Pr⁡[A>B]>12⇔μA>μB\Pr[A > B] > \frac{1}{2} \Leftrightarrow \mu_A > \mu_B

بسبب تعدية المتوسطات، تكون العلاقة الاحتمالية أيضاً متعدية.

تحديات عدم التعدية

بالنسبة للتوزيعات العشوائية، لا تضمن التعدية، وقد تظهر حلقات مثل A≻BA \succ B، B≻CB \succ C، C≻AC \succ A، مشابهة لظاهرة "الحجر والورقة والمقص".

اتجاهات البحث المستقبلية

1. توصيف العلاقات

  • دراسة شروط التوزيع التي تجعل علاقة →p\xrightarrow{p} متعدية
  • تطوير طرق تحويل للتعامل مع عدم التعدية

2. تباين شبكة المضيف

دراسة تأثير الرجفة في مسار البيانات للمضيف على تأخير الوصول إلى الساعة وتأخير إرسال الرسائل.

3. توسيع الترتيب الكامل العادل

توسيع الترتيب الجزئي العادل إلى ترتيب كامل عادل، ودراسة آليات العدالة العشوائية.

4. تعلم انحراف الساعة

تطوير آليات قوية لتعلم توزيع انحراف الساعة، والتعامل مع الظروف الشاذة مثل القفزات المفاجئة في درجة الحرارة.

5. العملاء البيزنطيين

دراسة ضمانات العدالة تحت الأخطاء البيزنطية، ومنع هجمات معالجة الطوابع الزمنية.

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. الابتكار المفاهيمي: توفر علاقة likely-happened-before منظوراً جديداً لترتيب الأحداث المتزامنة
  2. القيمة العملية: يتفوق Tommy على الطرق التقليدية في ظروف مزامنة الساعات الفعلية
  3. الأساس النظري: توفر التعدية تحت التوزيع الغاوسي دعماً نظرياً للطريقة

القيود

  1. افتراض التعدية: يفترض التصميم الحالي التعدية، وتتطلب الحالات غير المتعدية بحثاً إضافياً
  2. التقييم غير المتصل: تقيّم التجارب فقط الترتيب غير المتصل، والأداء عبر الإنترنت قيد الانتظار
  3. افتراض التوزيع: قد لا ينطبق افتراض التوزيع الغاوسي على جميع السيناريوهات العملية
  4. التسامح مع الأخطاء البيزنطية: تفتقر إلى آليات الحماية ضد العملاء الخبيثين

تقييم التأثير

المزايا

  1. المساهمة النظرية: توسيع علاقة happened-before الكلاسيكية
  2. التوجه العملي: حل المشاكل الفعلية في الهجرة السحابية
  3. إطار عام: يدعم توزيعات انحراف ساعة عشوائية
  4. ميزة الأداء: يتفوق على الطرق الموجودة في الظروف الواقعية

أوجه القصور

  1. نقص الاكتمال: حل معالجة عدم التعدية غير مكتمل بما فيه الكفاية
  2. تحليل الأمان: يفتقر إلى تحليل عميق للتهديدات الأمنية
  3. قيود التجارب: تجارب محاكاة فقط، تفتقر إلى التحقق من النظام الحقيقي

السيناريوهات المعمول بها

  • أنظمة التداول المالي المنتشرة في عدة مراكز بيانات
  • أنظمة المزاد التي لها متطلبات صارمة للعدالة
  • التطبيقات التي تحتاج إلى تنفيذ الترتيب العادل على بنية تحتية شبكية عامة

القيمة البحثية

تقدم هذه الورقة بشكل رائد فكرة الترتيب العادل الاحتمالي، وتوفر اتجاهاً حلاً جديداً لمشكلة العدالة في الأنظمة الموزعة. على الرغم من وجود بعض التحديات النظرية والتنفيذية، فإن الفكرة الأساسية لها قيمة أكاديمية وإمكانات عملية مهمة، وتضع الأساس للأبحاث اللاحقة.

المراجع

تشمل المراجع الرئيسية:

  • 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" (الأعمال ذات الصلة ببورصات السحابة)