بعد 22 عامًا من الشك: مزج الرسائل يتفوّق على توجيهها

تخيّل شبكة من الكابلات يريد فيها عدة مُرسِلين أن يصل كلٌّ منهم إلى مستقبِله الخاص. النهج الكلاسيكي هو التوجيه (routing): تنتقل كل رسالة كطرد عبر مسار واحد أو أكثر، بل يمكن تقسيم حركة البيانات على مسارات كثيرة بأي نسبة. ويضيف ترميز الشبكة (network coding) حرية أخرى: إذ يمكن للعُقد الوسيطة أن تدمج الرسائل التي تتلقاها — كأن تجمعها مثلًا — بدلًا من الاكتفاء بتمريرها.

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

حدسية تأكّدت حالةً بعد حالة

في عام 2004، افترض لي ولي (Li and Li) أن الترميز في هذا السياق لا يمنح أي أفضلية على التوجيه الكسري؛ وصاغ هارفي وكلاينبرغ وراسالا ليمان (Harvey, Kleinberg and Rasala Lehman) الحدسية نفسها بشكل مستقل. وعلى مدى العقدين التاليين، تأكّدت لفئة من الشبكات تلو الأخرى — جلستان، وبعض الشبكات المستوية، والشبكات التي تضم ست عُقد ترميز على الأكثر، وغير ذلك — لكنها لم تُحسم قط بشكل عام. بل إن نتائج أخرى في نظرية التعقيد، مثل الحدود الدنيا لفرز الأعداد الصحيحة في الذاكرة الخارجية ولدارات الضرب، كانت قد بُرهنت بافتراض صحتها.

كانت النظرية المعروفة قد حدّدت بالفعل حجم الرهان: إذ لا يمكن للترميز أن يتفوّق على التوجيه إلا بعامل لوغاريتمي على الأكثر. وأظهرت نتيجة عام 2017 لبرافرمان وغارغ وشفارتسمان (Braverman, Garg and Schvartzman) أن شبكة واحدة ذات أفضلية ترميز صارمة يمكن تضخيمها إلى فجوة أكبر بكثير. فكان كل شيء يتوقف على إيجاد مثال واحد منتهٍ.

الجمع يكفي

يقدّم الملحق الأداة الأساسية، التي تُبيّن لماذا يمكن أن يفيد المزج. ضع عدة مصادر حول محور v، ومستقبِليها حول محور آخر w، وصِل v وw بكابل واحد. ولكل مصدر أيضًا مسارات جانبية صغيرة نحو المستقبِلين الآخرين. وفي ثلاث جولات، ينقل الكابل الأوسط مجموع كل الرسائل؛ فيتلقى كل مستقبِل هذا المجموع إضافةً إلى الرسائل الأخرى عبر المسارات الجانبية، ويستعيد رسالته بالطرح. ومن دون الكابل الأوسط، يبعد كل مصدر عن مستقبِله خمس قفزات.

هذه الأداة، المأخوذة من أعمال سابقة لهاوبلر وفايتس وزوزيتش (Haeupler, Wajc and Zuzic)، تجعل الترميز أسرع، لكنها لا تجعله وحدها قادرًا على نقل المزيد: إذ يظل بإمكان المسار الطويل تشغيل خط معالجة متتابع (pipeline) عالي المعدل.

دارة تتحوّل إلى شبكة

وجد شينْدان تشانغ (Xindan Zhang) وباوتشون لي (Baochun Li)، من جامعة تورنتو، وزونغبنغ لي (Zongpeng Li)، من جامعة تسينغهوا، الخطوة الناقصة. فهم يحوّلون شيفرة قصيرة إلى حوسبة عكوسة — دارة من عمليات جمع صحيحة قابلة للعكس تحسب، وتنسخ النتيجة، ثم تتراجع عن عملها الوسيط. ثم يبنون شبكة جديدة تكون كابلاتها الفيزيائية هي أسلاك تلك الدارة، ويمنحون كل سجلّ في الحوسبة، بما في ذلك السجلات المؤقتة، طلبه الخاص من مُرسِل إلى مستقبِل.

ويتكفّل حساب دقيق لـ«الزمن» على امتداد الأسلاك بالباقي. فعند الجمع على كل الأسلاك، تطابق الأطوال تمامًا المسافات الدنيا التي يجب أن تقطعها الطلبات. لكن الطلبات المحددة لا يمكنها تجنّب بوابات معيّنة تكلّف وحدتين إضافيتين. لذا يجب أن يقصر التوجيه قصورًا صارمًا عن المعدل الكامل، بينما تستخدم الشيفرة كل كابل مرة واحدة بالضبط، وعند تشغيلها متتابعةً على كتل كثيرة، تقترب من معدل يساوي واحدًا.

ما الذي بُرهن

شبكة متصلة منتهية، كل عقدة فيها مرتبطة بثلاث عقد أخرى على الأكثر وسعة كل كابل وحدة واحدة، تتفوّق فيها شيفرة خطية ثنائية بسيطة على أفضل توجيه كسري ممكن. حدسية 2004 خاطئة.
البناء الصحيح نفسه يصلح في آن واحد على كل حقل منتهٍ وكل زمرة أبيلية منتهية غير تافهة.
وبدمج النسخ مرارًا، يبني المؤلفون عائلات لا نهائية من الشبكات يقترب فيها الترميز من المعدل الكامل بينما يهبط التوجيه كقوة من قوى 1/log n — أي أفضلية متعددة اللوغاريتمات (polylogarithmic).

لا تذكر الورقة عدد العُقد في مثالها المضاد. فلبنة البناء وحدها شيفرة تمتد 13,122 جولة.

تحقّق آلي

صيغ كلٌّ من المثال المضاد المنتهي ومبرهنة العائلات صياغةً رسمية في مساعد البراهين Lean. ووفقًا للمؤلفين، يُظهر تدقيق لـ2,472 تصريحًا و1,755 مبرهنة أن البراهين لا تستخدم سوى بديهيات Lean المعيارية الثلاث، دون أي براهين ناقصة؛ كما نجحت إعادة تحقق مستقلة في بيئة جديدة، وإن كان ذلك بنواة Lean نفسها.

ما يبقى مفتوحًا

يسرد المؤلفون ثلاثة أسئلة: الحجم الحقيقي للأفضلية في مثالهم المنتهي، وما إذا كان السقف اللوغاريتمي المعروف يُبلغ فعلًا، وما إذا كان يوجد مثال مضاد صغير. وتلخّص جملتهم الأخيرة الوضع الراهن: «يتّضح أن الترميز يساعد فعلًا في الشبكات غير الموجّهة؛ أما مقدار ما يمكن أن يساعد به فيبقى رهن ما ستكشفه الأيام».

استخدام مُعلَن للذكاء الاصطناعي. تذكر حاشية أن نموذج GPT-6 Astra من OpenAI ساعد في تطوير البراهين وشيفرة Lean.