22 ஆண்டுச் சந்தேகத்துக்குப் பின்: செய்திகளைக் கலப்பது வழிச்செலுத்தலை வெல்கிறது

பல அனுப்புநர்கள் ஒவ்வொருவரும் தங்கள் சொந்தப் பெறுநரை அடைய விரும்பும் கேபிள்களின் வலைப்பின்னல் ஒன்றைக் கற்பனை செய்யுங்கள். பாரம்பரிய அணுகுமுறை வழிச்செலுத்தல் (routing): ஒவ்வொரு செய்தியும் ஒரு பார்சல் போல ஒன்று அல்லது அதற்கு மேற்பட்ட பாதைகளில் பயணிக்கிறது; போக்குவரத்தை எந்த விகிதத்திலும் பல பாதைகளுக்குப் பிரிக்கவும் முடியும். வலைப்பின்னல் குறியாக்கம் (network coding) இன்னொரு சுதந்திரத்தைச் சேர்க்கிறது: இடைநிலைக் கணுக்கள் தாம் பெறும் செய்திகளை வெறுமனே முன்னனுப்புவதற்குப் பதிலாக இணைக்கலாம் — எடுத்துக்காட்டாக, அவற்றைக் கூட்டுவதன் மூலம்.

அந்தச் சுதந்திரம் எப்போதாவது அதிகத் தரவு செல்ல அனுமதிக்கிறதா என்பதுதான் கேள்வி. ஒரு கேபிள் தரவை இரு திசைகளிலும் கொண்டுசெல்லக்கூடிய, ஆனால் இரு திசைகளும் ஒரே கொள்ளளவைப் பகிர்ந்துகொள்ளும் திசையற்ற வலைப்பின்னல்களில் கட்டுரை கவனம் செலுத்துகிறது.

நேர்வுக்கு நேர்வு உறுதிசெய்யப்பட்ட ஊகம்

2004இல், இந்தச் சூழலில் பின்ன வழிச்செலுத்தலை விடக் குறியாக்கம் எந்த அனுகூலமும் தருவதில்லை என்று லீயும் லீயும் ஊகித்தனர்; ஹார்வி, கிளைன்பெர்க், ரசாலா லேமன் ஆகியோரும் அதே ஊகத்தைத் தனித்தனியாக வடிவமைத்தனர். அடுத்த இருபது ஆண்டுகளில், அது ஒரு வலைப்பின்னல் வகைக்குப் பின் மற்றொன்றுக்கு உறுதிசெய்யப்பட்டது — இரண்டு அமர்வுகள், சில தளவலைப்பின்னல்கள், அதிகபட்சம் ஆறு குறியாக்கக் கணுக்கள் கொண்ட வலைப்பின்னல்கள், இன்னும் பல — ஆனால் பொதுவாக ஒருபோதும் தீர்க்கப்படவில்லை. வெளிநினைவகத்தில் முழு எண்களை வரிசைப்படுத்துவதற்கும் பெருக்கல் சுற்றுகளுக்குமான கீழ் வரம்புகள் போன்ற சிக்கல்தன்மைக் கோட்பாட்டின் பிற முடிவுகள், அதை அனுமானித்தே நிரூபிக்கப்பட்டிருந்தன.

அறியப்பட்ட கோட்பாடு ஏற்கனவே பணயத்தை வரம்பிட்டிருந்தது: குறியாக்கம் வழிச்செலுத்தலை அதிகபட்சம் ஒரு மடக்கைக் காரணியால் மட்டுமே மிஞ்ச முடியும். பிரேவர்மன், கார்க், ஷ்வார்ட்ஸ்மன் ஆகியோரின் 2017 முடிவு, கண்டிப்பான குறியாக்க அனுகூலம் கொண்ட ஒரே ஒரு வலைப்பின்னலை மிகப் பெரிய இடைவெளியாகப் பெருக்க முடியும் என்று காட்டியது. எல்லாம் ஒரு முடிவுள்ள எடுத்துக்காட்டைக் கண்டுபிடிப்பதில் வந்து நின்றது.

கூட்டுவதே போதும்

கலத்தல் ஏன் உதவக்கூடும் என்பதைக் காட்டும் அடிப்படைச் சாதனத்தைப் பின்னிணைப்பு தருகிறது. பல மூலங்களை ஒரு மையம் vஐச் சுற்றியும், அவற்றின் பெறுநர்களை மற்றொரு மையம் wஐச் சுற்றியும் வைத்து, vஐயும் wஐயும் ஒரு கேபிளால் இணையுங்கள். ஒவ்வொரு மூலத்துக்கும் மற்ற பெறுநர்களுக்குச் சிறிய பக்கப் பாதைகளும் உள்ளன. மூன்று சுற்றுகளில், நடுக் கேபிள் எல்லாச் செய்திகளின் கூட்டுத்தொகையைக் கொண்டுசெல்கிறது; ஒவ்வொரு பெறுநரும் அந்தக் கூட்டுத்தொகையையும் பக்கப் பாதைகளிலிருந்து பிற செய்திகளையும் பெற்று, கழித்தல் மூலம் தன் செய்தியை மீட்கிறது. நடுக் கேபிள் இல்லாவிட்டால், ஒவ்வொரு மூலமும் அதன் பெறுநரிடமிருந்து ஐந்து தாவல்கள் தொலைவில் உள்ளது.

ஹாப்லர், வாய்க், சூசிச் ஆகியோரின் முந்தைய ஆய்விலிருந்து வரும் அந்தச் சாதனம் குறியாக்கத்தை வேகமாக்குகிறது, ஆனால் அதுவாகவே அதிகம் கொண்டுசெல்லும் திறனைத் தருவதில்லை: ஒரு நீண்ட பாதை இன்னும் அதிவேகக் குழாய்வழியை இயக்க முடியும்.

வலைப்பின்னலாக மாற்றப்பட்ட சுற்று

டொராண்டோ பல்கலைக்கழகத்தைச் சேர்ந்த ஷிண்டான் ஜாங், பாவ்சுன் லீ, சிங்குவா பல்கலைக்கழகத்தைச் சேர்ந்த சோங்பெங் லீ ஆகியோர் விடுபட்ட படியைக் கண்டுபிடித்தனர். அவர்கள் ஒரு குறுகிய குறியீட்டை ஒரு மீளக்கூடிய கணிப்பாக மாற்றுகின்றனர் — கணக்கிட்டு, முடிவை நகலெடுத்து, பின் தன் இடைநிலை வேலையைத் திரும்பச் செய்யும், தலைகீழாக்கக்கூடிய முழு எண் கூட்டல்களின் சுற்று. பிறகு, அதன் பௌதிகக் கேபிள்களே அந்தச் சுற்றின் கம்பிகளாக உள்ள ஒரு புதிய வலைப்பின்னலை உருவாக்கி, கணிப்பின் ஒவ்வொரு பதிவேட்டுக்கும், தற்காலிகப் பதிவேடுகள் உட்பட, அதன் சொந்த அனுப்புநர்–பெறுநர் கோரிக்கையை வழங்குகின்றனர்.

கம்பிகள் நெடுகிலும் “நேரத்தின்” கவனமான கணக்கீடு மீதியைச் செய்கிறது. எல்லாக் கம்பிகளின் மீதும் கூட்டப்படும்போது, நீளங்கள் கோரிக்கைகள் கடக்க வேண்டிய குறைந்தபட்சத் தொலைவுகளுடன் சரியாகப் பொருந்துகின்றன. ஆனால் நியமிக்கப்பட்ட கோரிக்கைகள், இரண்டு கூடுதல் அலகுகள் செலவாகும் சில வாயில்களைத் தவிர்க்க முடியாது. எனவே வழிச்செலுத்தல் முழு வீதத்தை விடக் கண்டிப்பாகக் குறைவாகவே இருக்க வேண்டும்; குறியீடோ ஒவ்வொரு கேபிளையும் சரியாக ஒருமுறை பயன்படுத்தி, பல தொகுதிகளில் குழாய்வழிப்படுத்தப்படும்போது ஒன்று என்ற வீதத்தை நெருங்குகிறது.

நிரூபிக்கப்பட்டவை

• ஒவ்வொரு கணுவும் அதிகபட்சம் மூன்று பிற கணுக்களுடன் இணைக்கப்பட்டு, ஒவ்வொரு கேபிளும் அலகுக் கொள்ளளவு கொண்ட முடிவுள்ள இணைந்த வலைப்பின்னல் ஒன்று; அதில் ஓர் எளிய இரும நேரியல் குறியீடு, சாத்தியமான சிறந்த பின்ன வழிச்செலுத்தலை வெல்கிறது. 2004 ஊகம் தவறு.
• அதே முழு எண் கட்டமைப்பு ஒவ்வொரு முடிவுள்ள புலத்திலும், ஒவ்வொரு அற்பமற்ற முடிவுள்ள ஏபெல் குலத்திலும் ஒரே நேரத்தில் செயல்படுகிறது.
• நகல்களைத் திரும்பத் திரும்ப இணைப்பதன் மூலம், குறியாக்கம் முழு வீதத்தை நெருங்கும் அதே வேளையில் வழிச்செலுத்தல் 1/log nஇன் ஒரு அடுக்கு போலக் குறையும் முடிவற்ற வலைப்பின்னல் குடும்பங்களை ஆசிரியர்கள் உருவாக்குகின்றனர் — ஒரு பல்மடக்கை அனுகூலம்.

கட்டுரை தன் எதிர் எடுத்துக்காட்டில் உள்ள கணுக்களின் எண்ணிக்கையைத் தரவில்லை. அதன் கட்டுமானத் தொகுதியே 13,122 சுற்றுகள் நீடிக்கும் ஒரு குறியீடு.

இயந்திரத்தால் சரிபார்க்கப்பட்டது

முடிவுள்ள எதிர் எடுத்துக்காட்டும் குடும்பத் தேற்றமும் Lean நிரூபண உதவியாளரில் முறைப்படுத்தப்பட்டுள்ளன. ஆசிரியர்களின் கூற்றுப்படி, 2,472 அறிவிப்புகள், 1,755 தேற்றங்களின் தணிக்கை, நிரூபணங்கள் Lean இன் மூன்று நிலையான அடிக்கோள்களை மட்டுமே பயன்படுத்துகின்றன என்றும், முழுமையற்ற நிரூபணங்கள் இல்லை என்றும் காட்டுகிறது; புதிய சூழலில் செய்யப்பட்ட ஒரு சுயாதீன மறுசரிபார்ப்பும் வெற்றி பெற்றது, ஆனால் அதே Lean கருவுடன்.

திறந்தே இருப்பவை

ஆசிரியர்கள் மூன்று கேள்விகளைப் பட்டியலிடுகின்றனர்: அவர்களின் முடிவுள்ள எடுத்துக்காட்டில் அனுகூலத்தின் உண்மையான அளவு, அறியப்பட்ட மடக்கை உச்சவரம்பு உண்மையில் எட்டப்படுகிறதா, ஒரு சிறிய எதிர் எடுத்துக்காட்டு உள்ளதா. அவர்களின் கடைசி வாக்கியம் நிலைமையைச் சுருக்குகிறது: “குறியாக்கம், திசையற்ற வலைப்பின்னல்களில் உண்மையிலேயே உதவுகிறது என்று தெரியவருகிறது; அது எவ்வளவு உதவ முடியும் என்பது இனிதான் தெரிய வேண்டும்.”

செயற்கை நுண்ணறிவுப் பயன்பாடு அறிவிக்கப்பட்டது. நிரூபணங்களையும் Lean குறியீட்டையும் உருவாக்க OpenAI நிறுவனத்தின் GPT-6 Astra உதவியதாக ஓர் அடிக்குறிப்பு கூறுகிறது.