TRỘN THÔNG ĐIỆP THẮNG ĐỊNH TUYẾN CHÚNG, SAU 22 NĂM HOÀI NGHI

Hãy hình dung một mạng cáp trong đó nhiều bên gửi, mỗi bên đều muốn tới được bên nhận của riêng mình. Cách tiếp cận kinh điển là định tuyến (routing): mỗi thông điệp đi như một bưu kiện dọc theo một hoặc nhiều đường, và lưu lượng thậm chí có thể được chia ra nhiều đường theo bất kỳ tỉ lệ nào. Mã hóa mạng (network coding) bổ sung thêm một sự tự do: các nút trung gian có thể kết hợp những thông điệp chúng nhận được — chẳng hạn bằng cách cộng lại — thay vì chỉ chuyển tiếp.

Câu hỏi là liệu sự tự do đó có bao giờ cho phép nhiều dữ liệu đi qua hơn không. Bài báo tập trung vào các mạng vô hướng, nơi một sợi cáp có thể chở dữ liệu theo cả hai chiều nhưng hai chiều dùng chung một dung lượng duy nhất.

Một giả thuyết được xác nhận hết trường hợp này đến trường hợp khác

Năm 2004, Li và Li đưa ra giả thuyết rằng trong bối cảnh này, mã hóa không mang lại lợi thế nào so với định tuyến phân đoạn (fractional routing); Harvey, Kleinberg và Rasala Lehman cũng độc lập phát biểu cùng giả thuyết đó. Trong hai thập kỷ tiếp theo, nó được xác nhận cho hết lớp mạng này đến lớp mạng khác — hai phiên, một số mạng phẳng, các mạng có tối đa sáu nút mã hóa, và nhiều hơn nữa — nhưng chưa bao giờ được giải quyết trong trường hợp tổng quát. Một số kết quả khác trong lý thuyết độ phức tạp, như các cận dưới cho việc sắp xếp số nguyên trong bộ nhớ ngoài và cho các mạch nhân, thậm chí đã được chứng minh dựa trên giả định nó đúng.

Lý thuyết đã biết vốn đã giới hạn mức độ được mất: mã hóa chỉ có thể vượt định tuyến nhiều nhất một thừa số logarit. Và một kết quả năm 2017 của Braverman, Garg và Schvartzman cho thấy rằng chỉ cần một mạng có lợi thế mã hóa nghiêm ngặt là có thể khuếch đại thành một khoảng cách lớn hơn nhiều. Mọi thứ quy về việc tìm ra một ví dụ hữu hạn.

Phép cộng là đủ

Phần phụ lục đưa ra cơ cấu cơ bản, cho thấy vì sao việc trộn có thể giúp ích. Đặt nhiều nguồn quanh một nút trung tâm v, các bên nhận của chúng quanh một nút trung tâm khác w, và nối v với w bằng một sợi cáp. Mỗi nguồn cũng có những đường phụ nhỏ dẫn tới các bên nhận khác. Trong ba vòng, sợi cáp ở giữa chở tổng của mọi thông điệp; mỗi bên nhận có được tổng đó cùng các thông điệp khác từ đường phụ, và lấy lại thông điệp của mình bằng phép trừ. Không có sợi cáp giữa, mỗi nguồn cách bên nhận của nó năm bước nhảy.

Cơ cấu đó, từ công trình trước của Haeupler, Wajc và Zuzic, làm cho mã hóa nhanh hơn, nhưng tự nó không giúp chở được nhiều hơn: một đường dài vẫn có thể vận hành một đường ống (pipeline) tốc độ cao.

Một mạch được biến thành mạng

Xindan Zhang và Baochun Li, ở Đại học Toronto, cùng Zongpeng Li, ở Đại học Thanh Hoa, đã tìm ra bước còn thiếu. Họ biến một mã ngắn thành một phép tính khả nghịch — một mạch gồm các phép cộng số nguyên có thể đảo ngược, tính toán, sao chép kết quả, rồi hoàn tác các bước trung gian. Sau đó họ dựng một mạng mới mà các sợi cáp vật lý của nó chính là các dây của mạch ấy, và gán cho mỗi thanh ghi của phép tính, kể cả các thanh ghi nháp, một yêu cầu gửi–nhận riêng.

Một phép tính toán cẩn thận về “thời gian” dọc các dây làm nốt phần còn lại. Cộng trên mọi dây, tổng độ dài khớp chính xác với các khoảng cách tối thiểu mà các yêu cầu phải vượt qua. Nhưng các yêu cầu được chỉ định không thể tránh một số cổng tốn thêm hai đơn vị. Vì vậy định tuyến buộc phải hụt so với tốc độ đầy đủ, trong khi mã dùng mỗi sợi cáp đúng một lần và, khi được xếp đường ống qua nhiều khối, tiến gần tới tốc độ bằng một.

Những gì đã được chứng minh

• Một mạng liên thông hữu hạn, mỗi nút nối với tối đa ba nút khác và mỗi sợi cáp có dung lượng đơn vị, trên đó một mã tuyến tính nhị phân đơn giản vượt qua phương án định tuyến phân đoạn tốt nhất có thể. Giả thuyết năm 2004 là sai.
• Cùng một cấu trúc số nguyên hoạt động đồng thời trên mọi trường hữu hạn và mọi nhóm abel hữu hạn không tầm thường.
• Bằng cách kết hợp lặp lại các bản sao, các tác giả dựng được những họ mạng vô hạn trong đó mã hóa tiến gần tới tốc độ đầy đủ còn định tuyến giảm như một lũy thừa của 1/log n — một lợi thế đa logarit.

Bài báo không cho biết số nút trong phản ví dụ. Riêng khối cơ sở của nó đã là một mã kéo dài 13.122 vòng.

Được máy kiểm tra

Cả phản ví dụ hữu hạn lẫn định lý về họ mạng đều được hình thức hóa trong trợ lý chứng minh Lean. Theo các tác giả, một đợt rà soát 2.472 khai báo và 1.755 định lý cho thấy các chứng minh chỉ dùng ba tiên đề chuẩn của Lean, không có chứng minh nào dang dở; một lần kiểm tra lại độc lập trong môi trường mới cũng thành công, dù vẫn với cùng nhân (kernel) Lean.

Những gì còn bỏ ngỏ

Các tác giả liệt kê ba câu hỏi: kích thước thực sự của lợi thế trên ví dụ hữu hạn của họ, liệu trần logarit đã biết có thực sự đạt được không, và liệu có tồn tại một phản ví dụ nhỏ hay không. Câu cuối cùng của họ tóm tắt hiện trạng: “Hóa ra mã hóa thực sự có ích trong mạng vô hướng; nó có thể giúp được bao nhiêu thì vẫn còn phải chờ xem.”

Khai báo sử dụng AI. Một chú thích cho biết GPT-6 Astra của OpenAI đã hỗ trợ phát triển các chứng minh và mã Lean.