پس از ۲۲ سال تردید: درآمیختن پیام‌ها بر مسیریابی آن‌ها پیروز می‌شود
شبکه‌ای از کابل‌ها را تصور کنید که در آن چند فرستنده هر کدام می‌خواهند به گیرندهٔ خودشان برسند. رویکرد کلاسیک مسیریابی (routing) است: هر پیام مانند یک بستهٔ پستی در امتداد یک یا چند مسیر حرکت می‌کند، و ترافیک حتی می‌تواند با هر نسبتی میان مسیرهای بسیار تقسیم شود. کدگذاری شبکه (network coding) آزادی دیگری می‌افزاید: گره‌های میانی می‌توانند پیام‌هایی را که دریافت می‌کنند به جای این‌که صرفاً بازفرستند، ترکیب کنند — برای نمونه با جمع کردن آن‌ها.
پرسش این است که آیا این آزادی هرگز اجازه می‌دهد دادهٔ بیشتری عبور کند. مقاله بر شبکه‌های بی‌جهت تمرکز دارد، که در آن‌ها یک کابل می‌تواند داده را در هر دو جهت حمل کند اما دو جهت در یک ظرفیت واحد شریک‌اند.
حدسی که مورد به مورد تأیید شد
در ۲۰۰۴، لی و لی حدس زدند که در این وضعیت، کدگذاری هیچ برتری‌ای بر مسیریابی کسری ندارد؛ هاروی، کلاینبرگ و راسالا لمن نیز همین حدس را مستقلاً صورت‌بندی کردند. در دو دههٔ بعد، این حدس برای یک ردهٔ شبکه پس از دیگری تأیید شد — دو جلسه، برخی شبکه‌های مسطح، شبکه‌هایی با حداکثر شش گرهٔ کدگذار، و بیشتر — اما هرگز به‌طور کلی حل نشد. برخی نتایج دیگر در نظریهٔ پیچیدگی، مانند کران‌های پایین برای مرتب‌سازی اعداد صحیح در حافظهٔ خارجی و برای مدارهای ضرب، حتی با فرض درستی آن اثبات شده بودند.
نظریهٔ شناخته‌شده از پیش دامنهٔ ماجرا را محدود می‌کرد: کدگذاری حداکثر با یک ضریب لگاریتمی می‌تواند از مسیریابی بهتر باشد. و نتیجه‌ای در ۲۰۱۷ از براورمن، گارگ و شوارتسمن نشان داد که یک شبکهٔ منفرد با برتری اکید کدگذاری را می‌توان به شکافی بسیار بزرگ‌تر تقویت کرد. همه چیز به یافتن یک نمونهٔ متناهی بستگی داشت.
جمع کردن کافی است
پیوست، سازوکار پایه‌ای را ارائه می‌دهد که نشان می‌دهد چرا درآمیختن می‌تواند کمک کند. چند منبع را دور یک قطب v و گیرنده‌هایشان را دور قطب دیگری w قرار دهید، و v و w را با یک کابل به هم وصل کنید. هر منبع همچنین مسیرهای فرعی کوچکی به گیرنده‌های دیگر دارد. در سه دور، کابل میانی مجموع همهٔ پیام‌ها را حمل می‌کند؛ هر گیرنده این مجموع را به‌اضافهٔ پیام‌های دیگر از مسیرهای فرعی دریافت می‌کند و پیام خود را با تفریق بازیابی می‌کند. بدون کابل میانی، هر منبع پنج گام با گیرنده‌اش فاصله دارد.
این سازوکار، برگرفته از کار پیشین هاپلر، وایتس و زوزیچ، کدگذاری را سریع‌تر می‌کند، اما به‌تنهایی قادر نمی‌سازد که بیشتر حمل کند: یک مسیر بلند همچنان می‌تواند یک خط لولهٔ پرسرعت را اجرا کند.
مداری که به شبکه تبدیل شد
شین‌دان ژانگ و بائوچون لی، از دانشگاه تورنتو، و زونگ‌پنگ لی، از دانشگاه تسینگهوا، گام گمشده را یافتند. آن‌ها یک کد کوتاه را به یک محاسبهٔ برگشت‌پذیر تبدیل می‌کنند — مداری از جمع‌های وارون‌پذیر اعداد صحیح که محاسبه می‌کند، نتیجه را رونوشت می‌کند و سپس کار میانی خود را بازمی‌گرداند. سپس شبکه‌ای نو می‌سازند که کابل‌های فیزیکی‌اش همان سیم‌های آن مدارند، و به هر ثبات محاسبه، از جمله ثبات‌های موقت، تقاضای فرستنده–گیرندهٔ خاص خودش را می‌دهند.
حساب‌وکتابی دقیق از «زمان» در امتداد سیم‌ها بقیهٔ کار را انجام می‌دهد. وقتی روی همهٔ سیم‌ها جمع زده شود، طول‌ها دقیقاً با کمترین فاصله‌هایی که تقاضاها باید طی کنند برابر می‌شوند. اما تقاضاهای تعیین‌شده نمی‌توانند از برخی دروازه‌ها که دو واحد اضافه هزینه دارند پرهیز کنند. پس مسیریابی ناگزیر به‌طور اکید از نرخ کامل عقب می‌ماند، در حالی که کد هر کابل را دقیقاً یک بار به کار می‌برد و با خط لوله‌سازی روی بلوک‌های بسیار، به نرخ یک نزدیک می‌شود.
آنچه اثبات شده است
- یک شبکهٔ همبند متناهی، که در آن هر گره به حداکثر سه گرهٔ دیگر وصل است و هر کابل ظرفیت واحد دارد، و روی آن یک کد خطی دودویی ساده بر بهترین مسیریابی کسری ممکن پیروز می‌شود. حدس ۲۰۰۴ نادرست است.
- همین ساختار عدد صحیحی هم‌زمان روی هر میدان متناهی و هر گروه آبلی متناهی نابدیهی کار می‌کند.
- نویسندگان با ترکیب پیاپی رونوشت‌ها، خانواده‌هایی نامتناهی از شبکه‌ها می‌سازند که در آن‌ها کدگذاری به نرخ کامل نزدیک می‌شود در حالی که مسیریابی مانند توانی از ۱/log n افت می‌کند — یک برتری چندلگاریتمی.
مقاله شمار گره‌های مثال نقض خود را ذکر نمی‌کند. بلوک سازندهٔ آن به‌تنهایی کدی است که ۱۳٬۱۲۲ دور طول می‌کشد.
وارسی‌شده با ماشین
هم مثال نقض متناهی و هم قضیهٔ خانواده در دستیار اثبات Lean صوری‌سازی شده‌اند. به گفتهٔ نویسندگان، ممیزی ۲٬۴۷۲ اعلان و ۱٬۷۵۵ قضیه نشان می‌دهد که اثبات‌ها تنها از سه اصل موضوع استاندارد Lean استفاده می‌کنند و هیچ اثبات ناقصی ندارند؛ یک وارسی مجدد مستقل در محیطی تازه نیز موفق بود، هرچند با همان هستهٔ Lean.
آنچه باز می‌ماند
نویسندگان سه پرسش را برمی‌شمارند: اندازهٔ واقعی برتری در نمونهٔ متناهی‌شان، این‌که آیا سقف لگاریتمی شناخته‌شده واقعاً دست‌یافتنی است، و این‌که آیا یک مثال نقض کوچک وجود دارد. جملهٔ پایانی آن‌ها وضعیت را خلاصه می‌کند: «معلوم شد کدگذاری در شبکه‌های بی‌جهت واقعاً کمک می‌کند؛ این‌که تا چه اندازه می‌تواند کمک کند، هنوز باید دید.»
اعلام استفاده از هوش مصنوعی. یک پانوشت بیان می‌کند که GPT-6 Astra از OpenAI در توسعهٔ اثبات‌ها و کد Lean کمک کرده است.