Дослідники мереж сформулювали теорію «ідеальної стійкості»

· Наука

Дослідники мереж сформулювали теорію «ідеальної стійкості»

Вчені нарешті визначили математичні умови для створення мереж з «ідеальною стійкістю», здатних автоматично перенаправляти дані при будь-яких збоях з'єднань.

Науковці поставили крапку в багаторічних дискусіях про так звану «ідеальну стійкість» комп’ютерних мереж. Дослідники з Технічного університету Берліна Стефан Шмід та Маттіас Бентерт довели, що існують рівно чотири мінімальні структурні елементи, які унеможливлюють безперебійну роботу мережі в разі виходу з ладу окремих каналів зв'язку. Результати цієї роботи були представлені на Симпозіумі з теорії обчислень у червні 2026 року.

Проблема «ідеальної стійкості» полягає в здатності мережі доставляти дані з точки А в точку Б, здатних перенаправляти дані за будь-якого сценарію збоїв з’єднань, якщо між джерелом і призначенням зберігається шлях, за винятком випадків, коли через масштабний збій між джерелом і пунктом призначення не залишається жодного шляху. У реальних умовах маршрутизатори повинні ухвалювати рішення за частки мілісекунди, маючи доступ лише до локальної інформації про стан сусідніх ліній, а не до повної карти мережі. Без правильних правил маршрутизації дані можуть потрапити в нескінченні цикли — «пастки».

Чотири бар’єри для стабільності

Ще у 2012 році вчені визначили, що ідеальна стійкість можлива не завжди. Використовуючи теорію графів, дослідники моделювали мережі як вузли та лінії зв’язку. Маттіас Бентерт зміг ідентифікувати повний набір «заборонених мінорів» — специфічних структур, наявність яких у мережі гарантує, що жоден набір правил не зможе забезпечити стовідсоткову доставку пакетів.

«Я б зупинився, якби їх було 50 або близько того, але те, що їх лише чотири, стало для мене певною несподіванкою», — зазначив Маттіас Бентерт.

Виявлені правила маршрутизації для мереж без цих «заборонених мінорів» нагадують алгоритм виходу з лабіринту: поворот праворуч на кожному перехресті. Якщо мережа не містить жодної з чотирьох виявлених структур, такий підхід гарантує, що дані завжди досягнуть мети.

Практичне значення для мереж

Відкриття має неоднозначні наслідки для інженерії. Оскільки виявлені «заборонені» структури досить прості, багато сучасних мереж, особливо щільні та високозв’язні, можуть містити їх у своїй архітектурі. Це означає, що ідеальна стійкість у них недосяжна, навіть якщо мережа виглядає надійною. Водночас ці правила не враховують швидкість і перевантаження, тож у деяких мережах стійкість може бути не головним пріоритетом.

«Це дуже елегантний внесок. Досить рідко вдається отримати повне розуміння чого-небудь», — прокоментував Майкл Шапіра, комп’ютерний вчений з Єврейського університету в Єрусалимі, який не брав участі в дослідженні.

Наразі дослідники планують вивчити, чи змінить ситуацію можливість додавання невеликого обсягу інформації до самого пакета даних про вузли, через які він уже пройшов. Це потенційно може розширити можливості стійкої передачі даних для складніших систем, створених людьми або машинами.

За матеріалами Quanta Magazine

Про Що? — новини науки, технологій і світу