NACHRICHTEN MISCHEN SCHLÄGT ROUTEN – NACH 22 JAHREN ZWEIFEL

Man stelle sich ein Kabelnetz vor, in dem mehrere Sender jeweils ihren eigenen Empfänger erreichen wollen. Der klassische Ansatz ist das Routing: Jede Nachricht reist wie ein Paket entlang eines oder mehrerer Pfade, und der Verkehr lässt sich sogar in beliebigen Anteilen auf viele Pfade aufteilen. Die Netzwerkcodierung (network coding) fügt eine weitere Freiheit hinzu: Zwischenknoten dürfen die empfangenen Nachrichten kombinieren – etwa addieren –, statt sie bloß weiterzuleiten.

Die Frage ist, ob diese Freiheit jemals mehr Daten durchlässt. Die Studie konzentriert sich auf ungerichtete Netze, in denen ein Kabel Daten in beide Richtungen transportieren kann, beide Richtungen sich aber eine einzige Kapazität teilen.

Eine Vermutung, Fall um Fall bestätigt

2004 vermuteten Li und Li, dass Codierung in diesem Rahmen keinen Vorteil gegenüber fraktionalem Routing bringt; Harvey, Kleinberg und Rasala Lehman formulierten unabhängig dieselbe Vermutung. In den folgenden zwei Jahrzehnten wurde sie für eine Netzklasse nach der anderen bestätigt – zwei Sitzungen, bestimmte planare Netze, Netze mit höchstens sechs Codierknoten und weitere –, aber nie allgemein entschieden. Andere Ergebnisse der Komplexitätstheorie, etwa untere Schranken für das Sortieren ganzer Zahlen im externen Speicher und für Multiplikationsschaltkreise, waren sogar unter der Annahme bewiesen worden, dass sie stimmt.

Die bekannte Theorie begrenzte bereits den Einsatz: Codierung kann Routing höchstens um einen logarithmischen Faktor übertreffen. Und ein Ergebnis von Braverman, Garg und Schvartzman aus dem Jahr 2017 zeigte, dass sich ein einziges Netz mit einem strikten Codiervorteil zu einem viel größeren Abstand verstärken ließe. Alles lief darauf hinaus, ein endliches Beispiel zu finden.

Addieren genügt

Der Anhang stellt den Grundbaustein vor, der zeigt, warum Mischen helfen kann. Man platziere mehrere Quellen um einen Knotenpunkt v, ihre Empfänger um einen anderen Knotenpunkt w und verbinde v und w durch ein Kabel. Jede Quelle hat außerdem kleine Seitenpfade zu den anderen Empfängern. In drei Runden transportiert das mittlere Kabel die Summe aller Nachrichten; jeder Empfänger bekommt diese Summe plus die übrigen Nachrichten über die Seitenpfade und gewinnt seine eigene durch Subtraktion zurück. Ohne das mittlere Kabel ist jede Quelle fünf Sprünge von ihrem Empfänger entfernt.

Dieser Baustein aus früheren Arbeiten von Haeupler, Wajc und Zuzic macht Codierung schneller, aber für sich genommen nicht fähig, mehr zu transportieren: Ein langer Pfad kann immer noch eine Pipeline mit hoher Rate betreiben.

Ein Schaltkreis, zum Netz gemacht

Xindan Zhang und Baochun Li von der University of Toronto sowie Zongpeng Li von der Tsinghua-Universität fanden den fehlenden Schritt. Sie verwandeln einen kurzen Code in eine umkehrbare Berechnung – einen Schaltkreis aus invertierbaren ganzzahligen Additionen, der rechnet, das Ergebnis kopiert und dann seine Zwischenarbeit rückgängig macht. Dann bauen sie ein neues Netz, dessen physische Kabel die Leitungen dieses Schaltkreises sind, und geben jedem Register der Berechnung, auch den Hilfsregistern, eine eigene Sender-Empfänger-Anforderung.

Eine sorgfältige Buchführung über die „Zeit“ entlang der Leitungen erledigt den Rest. Über alle Leitungen summiert, entsprechen die Längen genau den Mindestabständen, die die Anforderungen überbrücken müssen. Die festgelegten Anforderungen können aber bestimmte Gatter nicht umgehen, die zwei zusätzliche Einheiten kosten. Also muss Routing strikt unter der vollen Rate bleiben, während der Code jedes Kabel genau einmal nutzt und, über viele Blöcke als Pipeline betrieben, sich einer Rate von eins nähert.

Was bewiesen ist

• Ein endliches zusammenhängendes Netz, in dem jeder Knoten mit höchstens drei anderen verbunden ist und jedes Kabel die Kapazität eins hat, auf dem ein einfacher binärer linearer Code das bestmögliche fraktionale Routing schlägt. Die Vermutung von 2004 ist falsch.
• Dieselbe ganzzahlige Konstruktion funktioniert zugleich über jedem endlichen Körper und jeder nichttrivialen endlichen abelschen Gruppe.
• Durch wiederholtes Kombinieren von Kopien bauen die Autoren unendliche Familien von Netzen, in denen Codierung sich der vollen Rate nähert, während Routing wie eine Potenz von 1/log n abfällt – ein polylogarithmischer Vorteil.

Die Studie nennt die Zahl der Knoten ihres Gegenbeispiels nicht. Allein ihr Baustein ist ein Code, der 13.122 Runden dauert.

Maschinell geprüft

Sowohl das endliche Gegenbeispiel als auch der Familiensatz sind im Beweisassistenten Lean formalisiert. Den Autoren zufolge zeigt eine Prüfung von 2.472 Deklarationen und 1.755 Sätzen, dass die Beweise nur die drei Standardaxiome von Lean verwenden und keine unvollständigen Beweise enthalten; eine unabhängige Nachprüfung in einer frischen Umgebung gelang ebenfalls, allerdings mit demselben Lean-Kern.

Was offen bleibt

Die Autoren nennen drei Fragen: die tatsächliche Größe des Vorteils in ihrem endlichen Beispiel, ob die bekannte logarithmische Obergrenze tatsächlich erreicht wird und ob es ein kleines Gegenbeispiel gibt. Ihr letzter Satz fasst den Stand zusammen: „Codierung hilft also tatsächlich in ungerichteten Netzen; wie sehr sie helfen kann, bleibt abzuwarten.“

KI-Nutzung angegeben. Eine Fußnote besagt, dass GPT-6 Astra von OpenAI bei der Entwicklung der Beweise und des Lean-Codes geholfen hat.