22 YILLIK ŞÜPHENİN ARDINDAN: MESAJLARI KARIŞTIRMAK, YÖNLENDİRMEYİ YENİYOR

Birkaç göndericinin her birinin kendi alıcısına ulaşmak istediği bir kablo ağı düşünün. Klasik yaklaşım yönlendirmedir (routing): her mesaj bir koli gibi bir ya da birkaç yol boyunca ilerler ve trafik herhangi bir oranda birçok yola bile bölünebilir. Ağ kodlaması (network coding) bir özgürlük daha ekler: ara düğümler aldıkları mesajları yalnızca iletmek yerine birleştirebilir — örneğin toplayarak.

Soru, bu özgürlüğün hiç daha fazla verinin geçmesine izin verip vermediği. Makale, bir kablonun veriyi her iki yönde de taşıyabildiği ama iki yönün tek bir kapasiteyi paylaştığı yönsüz ağlara odaklanıyor.

Durum durum doğrulanan bir sanı

2004’te Li ve Li, bu ortamda kodlamanın kesirli yönlendirmeye göre hiçbir üstünlük sağlamadığını öne sürdü; Harvey, Kleinberg ve Rasala Lehman da aynı sanıyı bağımsız olarak formüle etti. Sonraki yirmi yıl boyunca sanı bir ağ sınıfından ötekine doğrulandı — iki oturum, belirli düzlemsel ağlar, en fazla altı kodlama düğümüne sahip ağlar ve daha fazlası — ama genel olarak hiç çözülemedi. Karmaşıklık kuramındaki başka sonuçlar, örneğin harici bellekte tam sayı sıralama ve çarpma devreleri için alt sınırlar, bu sanı varsayılarak kanıtlanmıştı bile.

Bilinen kuram zaten riskin boyutunu sınırlıyordu: kodlama yönlendirmeyi en fazla logaritmik bir çarpanla geçebilir. Braverman, Garg ve Schvartzman’ın 2017 tarihli bir sonucu da kesin bir kodlama üstünlüğüne sahip tek bir ağın çok daha büyük bir farka büyütülebileceğini göstermişti. Her şey tek bir sonlu örnek bulmaya bağlıydı.

Toplamak yeterli

Ek bölüm, harmanlamanın neden yardımcı olabileceğini gösteren temel düzeneği veriyor. Birkaç kaynağı bir v merkezinin çevresine, alıcılarını başka bir w merkezinin çevresine yerleştirin ve v ile w’yi tek bir kabloyla bağlayın. Her kaynağın diğer alıcılara giden küçük yan yolları da var. Üç turda ortadaki kablo tüm mesajların toplamını taşıyor; her alıcı bu toplamı ve yan yollardan gelen diğer mesajları alıyor, kendi mesajını da çıkarma yaparak elde ediyor. Ortadaki kablo olmadan her kaynak alıcısından beş atlama uzakta.

Haeupler, Wajc ve Zuzic’in önceki çalışmasından gelen bu düzenek kodlamayı daha hızlı kılıyor, ama tek başına daha fazlasını taşıyabilir kılmıyor: uzun bir yol yine de yüksek hızlı bir boru hattı çalıştırabilir.

Ağa dönüştürülmüş bir devre

Toronto Üniversitesi’nden Xindan Zhang ve Baochun Li ile Tsinghua Üniversitesi’nden Zongpeng Li eksik adımı buldu. Kısa bir kodu tersinir bir hesaplamaya dönüştürüyorlar — hesaplayan, sonucu kopyalayan, ardından ara işlerini geri alan, tersinir tam sayı toplamalarından oluşan bir devre. Sonra fiziksel kabloları o devrenin telleri olan yeni bir ağ kuruyorlar ve ara bellek yazmaçları dahil hesaplamanın her yazmacına kendi gönderici–alıcı talebini veriyorlar.

Teller boyunca “zamanın” dikkatli bir muhasebesi gerisini hallediyor. Tüm teller üzerinden toplandığında uzunluklar, taleplerin kat etmesi gereken en kısa mesafelerle tam olarak eşleşiyor. Ama belirlenen talepler, iki ek birime mal olan belirli kapılardan kaçınamıyor. Böylece yönlendirme tam hızın kesin olarak altında kalmak zorunda; kod ise her kabloyu tam olarak bir kez kullanıyor ve birçok blok üzerinden boru hattına alındığında bire yaklaşan bir hıza ulaşıyor.

Kanıtlananlar

Her düğümün en fazla üç diğer düğüme bağlı olduğu ve her kablonun birim kapasiteye sahip olduğu sonlu bağlantılı bir ağ; bu ağda basit bir ikili doğrusal kod, mümkün olan en iyi kesirli yönlendirmeyi geçiyor. 2004 sanısı yanlış.
Aynı tam sayı yapısı her sonlu cisim ve her aşikâr olmayan sonlu değişmeli grup üzerinde aynı anda çalışıyor.
Yazarlar kopyaları tekrar tekrar birleştirerek, kodlamanın tam hıza yaklaştığı, yönlendirmenin ise 1/log n’nin bir kuvveti gibi düştüğü sonsuz ağ aileleri kuruyor — polilogaritmik bir üstünlük.

Makale, karşı örneğindeki düğüm sayısını vermiyor. Yalnızca yapı taşı bile 13.122 tur süren bir kod.

Makineyle denetlendi

Hem sonlu karşı örnek hem de aile teoremi Lean kanıt asistanında biçimselleştirildi. Yazarlara göre 2.472 bildirim ve 1.755 teoremin denetimi, kanıtların yalnızca Lean’in üç standart aksiyomunu kullandığını ve eksik kanıt bulunmadığını gösteriyor; temiz bir ortamda yapılan bağımsız bir yeniden denetim de başarılı oldu, ancak aynı Lean çekirdeğiyle.

Açık kalanlar

Yazarlar üç soru sıralıyor: sonlu örneklerindeki üstünlüğün gerçek boyutu, bilinen logaritmik tavana gerçekten ulaşılıp ulaşılmadığı ve küçük bir karşı örneğin var olup olmadığı. Son cümleleri durumu özetliyor: “Coding, it turns out, does help in undirected networks; how much it can help remains to be seen.” (Görünen o ki kodlama yönsüz ağlarda gerçekten yardımcı oluyor; ne kadar yardımcı olabileceği ise henüz belli değil.)

Yapay zekâ kullanımı beyan edildi. Bir dipnot, OpenAI’ın GPT-6 Astra’sının kanıtların ve Lean kodunun geliştirilmesine yardım ettiğini belirtiyor.