# 2023: Комп'ютерні системи і мережі. 4. Відкриті проблеми [TOC] # Відкриті проблеми в мережевих системах ## 1. Синхронізація годинників ![](https://i.imgur.com/aRXL9ng.png) Синхронізація годинника є одним із основних будівельних блоків для багатьох застосувань у інформатиці та техніці. Метою синхронізації годинника є забезпечення складових частин розподіленої системи єдиним значенням часу. Хоча проблема синхронізації годинників у розподілених системах вже привернула значну увагу як дослідників, так і практиків, ми вважаємо, що існує багато цікавих проблем, які залишаються невирішеними. У завданнях синхронізації годинника нам надається мережа вузлів, які хочуть підтримувати загальне значення часу. Наявність такого значення часу важлива для багатьох програм, як в Інтернеті, так і, наприклад, у бездротових сенсорних мережах. Кожен вузол може мати власний апаратний годинник, який не є абсолютно точним, тобто він відчуває певний змінний дрейф годинника. Для того, щоб переконатися, що вузли більш-менш узгоджені щодо поточного часу, вузли повинні синхронізувати свої дрейфові апаратні годинники шляхом постійного обміну повідомленнями, що містять інформацію про їхній поточний стан. Легко побачити, що ідеально синхронізувати годинники неможливо, оскільки вузли ніколи не мають поточної інформації про значення годинника інших вузлів через те, що всі повідомлення надходять після невідомої та змінної затримки. Навіть якщо затримки повідомлень завжди були однаковими і вузли точно знали це значення, вони все одно не могли ідеально синхронізувати годинники через змінні апаратні дрейфи годинника, тобто вузол не може точно визначити, скільки інший годинник просунувся з часу отримання останнього повідомлення. Це породжує природне запитання, яке є фундаментальним для багатьох областей додатків: "Наскільки добре вузли можуть синхронізувати свої годинники, враховуючи, що годинники мають змінний, але обмежений дрейф, і враховуючи, що повідомлення мають змінну, але обмежену затримку?" ![](https://media.newyorker.com/photos/6334bceb11f4b55ac7d6f040/4:3/w_2362,h_1771,c_limit/Hopper_final_02.jpg) - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов # Ресурси 1. [The Thorny Problem of Keeping the Internet’s Time]( https://www.newyorker.com/tech/annals-of-technology/the-thorny-problem-of-keeping-the-internets-time) 2. [Clock Synchronization: Open Problems in Theory and Practice](https://people.mpi-inf.mpg.de/~clenzen/pubs/LLSW10clock.pdf) 4. [Fundamental limits on synchronization of affine clocks in networks](https://www.researchgate.net/publication/224303401_Fundamental_limits_on_synchronization_of_affine_clocks_in_networks) 5. [Fundamental Limits on Synchronizing Clocks Over Networks](https://www.researchgate.net/publication/224183858_Fundamental_Limits_on_Synchronizing_Clocks_Over_Networks) 6. [Clock Synchronization in DistributedEnvironment](https://www.academia.edu/13860257/Clock_Synchronization_in_Distributed_Environment) 7. [Delay Asymmetry Correction Model](https://curve.carleton.ca/system/files/etd/74f0b075-d19e-4255-bcc3-b297e876783e/etd_pdf/561dc5d8c3aa529b23a94b5e40fa9845/rahman-delayasymmetrycorrectionmodelforieee1588synchronization.pdf) 8. [Robust Clock Skew and Offset Estimation for IEEE 1588 in the Presence of Unexpected Deterministic Path Delay Asymmetries](https://arxiv.org/pdf/2002.10858.pdf) ## 2. Неявна маршрутизація в мережах. ![](https://mrksr.de/publication/minimum-bisection/featured_hu7c41774f465df957aba6de39ca4479a0_363260_720x0_resize_lanczos_3.png) Ефективні протоколи маршрутизації для неструктурованих мережевих топологій стають все більш важливими в останні роки через різке зростання Інтернету та зростаючу популярність, напр., ad-hoc мережі та мережі робочих станцій. Методи маршрутизації для таких мереж мають бути простими, щоб забезпечити можливість швидкого прийняття рішень щодо маршрутизації. Алгоритм маршрутизації повинен бути розподіленим, щоб ефективно працювати у великих мережах, і він повинен бути онлайн-алгоритмом, щоб мати справу з різними моделями трафіку. Проблема зосереджена на онлайн-маршрутизації віртуального каналу, у якому запити маршрутизації, що складаються з джерела та цільового вузла, надходять у режимі онлайн, а алгоритм маршрутизації має вибрати шлях у мережі, який з’єднує джерело та цільовий вузол для кожного запиту. Мета полягає в тому, щоб мінімізувати перевантаження, тобто максимальне навантаження на мережеве з’єднання, де завантаження з’єднання — це кількість даних, переданих за з’єднанням, поділена на пропускну здатність з’єднання. Одним із підходів до онлайн-маршрутизації в мережах є неявна маршрутизація, тобто без будь-яких знань про поточний стан мережі. Для неявного методу шлях, обраний для запиту, може залежати лише від вихідного вузла, цільового вузла та деяких випадкових вхідних даних, якщо рандомізація дозволена. Таким чином, неявний алгоритм має відповідати всім критеріям, описаним вище. Це не завжди просто, оскільки шляхи маршрутизації можуть бути реалізовані за допомогою пошуку в таблиці маршрутизації. ![](https://i.imgur.com/uQR5bQ7.png) Алгоритм має бути розподіленим, оскільки всі рішення щодо маршрутизації можуть прийматися локально. Він має бути онлайн-алгоритмом, оскільки не може требувати попередньої обробки. - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов # Ресурси 1. [Oblivious Network Routing: Algorithms and Applications](https://direct.mit.edu/books/book/4050/Oblivious-Network-RoutingAlgorithms-and) 2. [Oblivious Network Design](https://math.mit.edu/~hajiagha/oblivious_network_design.pdf) 3. [A Practical Algorithm for Constructing Oblivious Routing Schemes](http://www.cs.cmu.edu/~harry/pdf/constructing_hierarchy.pdf) 4. [Oblivious Routing and Minimum Bisection](https://mrksr.de/publication/minimum-bisection/) 5. [Compact Oblivious Routing in Weighted Graphs](https://drops.dagstuhl.de/opus/volltexte/2020/12902/pdf/LIPIcs-ESA-2020-36.pdf) ## 3. Стабільність контролю, стану та безперервного консенсусу в мережах. ![](https://i.imgur.com/rUcsx0j.png) Консенсус є фундаментальним завданням у розподілених обчисленнях, він дозволяє звести розподілене завдання до централізованого шляхом узгодження стану системи, вхідних даних і (отже) спільного переходу в новий стан. Одноразовий консенсус не може самостабілізуватися, оскільки він може завершитися розбіжними результатами. З іншого боку, поточний консенсус може стабілізуватися, і таким чином, зрештою гарантувати, що при стабілізаціі нових екземплярів консенсусу властивість безпеки для виводу нового стану системи є правильною. У рамках поточного (самостабілізуючого) консенсусного завдання можна розглянути послідовність входів і виходів екземплярів і вимагати стабільності виходів, доки входи дозволяють таку стабільність. Наприклад, якщо вихід одного консенсусного екземпляра був 1, а наступний екземпляр має можливе вихідне значення 1 (разом з 0), тоді слід віддати перевагу 1. Задачу можно поставити таким чином -- треба мінімізувати кількість змін вихідних станів роботи системи. Відкритою проблемою є визначення найбільш стабільної (консенсусної) функції для використання, враховуючи гнучкість у прийнятті рішень щодо виходу системи. А саме, враховуючи певну послідовність змін вхідних даних, треба вибрати функцію, яка якомога менше змінює вихідні дані, припускаючи, що функція від входів до загального виходу обмежена лише для того, щоб гарантувати, що вихідний стан розподіленої системи має значення, що визначаться принаймні t + 1 входами системи (де параметр t відповідає охвату консенсусу). Наприклад, якщо система може записати (в пам’яті) останній вихід (він може бути штучний входом до системи), система може стабілізувати вихідні дані стільки, скільки відповідає задачам функціонування системи: Наприклад, якщо система включає п'ять процесорів, максимум два з яких можуть бути несправними, тобто t = 2. Якщо вхідні дані 1, 1, 1, 1, 1,- система повинна вивести 1. І тоді, якщо вхідні дані багаторазово змінюються на 1, 1, 1, 1, 0, а потім, скажімо, на 1, 1, 0, 1, 0,- система може залишатися зі стабільним виходом 1, але, як тільки вхідні дані змінюються на, скажімо, 1, 0, 0, 1, 0,- вихід системи повинен бути змінений на 0. ![](https://i.imgur.com/WLRGFtS.png) - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов # Ресурси 1. [Stability of continuous-time consensus algorithms for switching networkswith bidirectional interaction.](https://www.researchgate.net/publication/261020871_Stability_of_continuous-time_consensus_algorithms_for_switching_networks_with_bidirectional_interaction) 2. [Consensus Algorithms in Distributed Systems](https://www.baeldung.com/cs/consensus-algorithms-distributed-systems) 3. [Stability of synchronization in simplicial complexes](https://www.nature.com/articles/s41467-021-21486-9) 4. [Higher-order simplicial synchronization of coupled topological signals](https://www.nature.com/articles/s42005-021-00605-4) 5. [Networked Control Systems Stability](https://www.researchgate.net/publication/3206709_Stability_of_networked_control_systems_IEEE_Control_Syst_Mag_21_84-99) ## 4. Складність реалізації атомарних знімків. - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов ## 5. Чиста рівновага Неша в егоїстичній маршрутизаціі. - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов ## 6. Кооперативні обчислення у несприятливому середовищи. - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов ## 7. Розподілені наближення. - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов ## 8. Сенсорні мережі: локальність для геометричних графів - [ ] Доповідач – здобувач 4 курсу ..... Науковий керівник – ст. викладач А.Л. Максимов ## 9. Консенсус без очікування. - [ ] Доповідач – магістр 1 року навчання ..... 👨🏻‍🎓👨🏻‍🎓 # Ресурси 1. [EIGHT OPEN PROBLEMS IN DISTRIBUTED COMPUTING]([file:///home/arthmax/%D0%97%D0%B0%D0%B3%D1%80%D1%83%D0%B7%D0%BA%D0%B8/Eight_open_problems_in_distributed_computing.pdf](https://www.researchgate.net/publication/264914474_Eight_open_problems_in_distributed_computing)) 2. [Major unsolved problems in distributed systems](https://cstheory.stackexchange.com/questions/10045/major-unsolved-problems-in-distributed-systems) 3. [Is there a list of canonical problems in distributed systems?](https://cstheory.stackexchange.com/questions/17132/is-there-a-list-of-canonical-problems-in-distributed-systems?rq=1) 4. [Concurrent data structures vs. Distributed data structures](https://cstheory.stackexchange.com/questions/25183/concurrent-data-structures-vs-distributed-data-structures?rq=1)