Рандомізовані алгоритми в системах без координації та централізації
Вантажиться...
Дата
2024
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Institute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
Анотація
Оцінювання складності алгоритмів виходячи тільки з можливості найгіршого варіанту вхідних даних є часто не виправданим. Розробка алгоритмів, які б очікувано швидко працювали на всіх можливих входах має практичне значення. Якщо для задачі існує розумна можливість змоделювати розподіли вхідних величин, то можна скористатися ймовірнісним аналізом як методом розробки ефективних алгоритмів. Коли ж інформації про розподіли вхідних величин недостатньо для їх чисельного моделювання, розробляють алгоритми шляхом надання випадкового характеру частині самого алгоритму – рандомізовані алгоритми. Застосування рандомізації забезпечує функціонування алгоритму при мінімальних потребах у зберіганні внутрішніх станів та подій у минулому, причому самі алгоритми виглядають компактно. В роботі вивчаються задачі, для яких існують відносно ефективні детерміновані алгоритми розв’язання. Але, як буде показано, побудова відповідних рандомізованих алгоритмів призводить до ефектних та ефективних схем паралельних обчислень з лінійною складністю в середньому. Переваги рандомізації особливо проявляються у випадку великих комп’ютерних систем та комунікаційних мереж, які функціонують без координації та централізації. Прикладами таких розподілених систем є, зокрема, мережі популярних нині криптовалют. Застосування рандомізованих евристик дозволяє системі адаптуватися до змінних умов експлуатації та мінімізує ймовірність конфліктів між процесами. В роботі показано переваги застосування рандомізованого алгоритму перед детермінованими алгоритмами для задачі маршрутизації в мережі з топологією гіперкуба. Доведено теорему про оцінку очікуваного числа кроків, необхідних рандомізованому алгоритму Валіанта для доставки всіх повідомлень за адресою. Очікувана лінійна складність алгоритму Валіанта є прямим наслідком доведеної теореми.
Опис
Ключові слова
рандомізований алгоритм, паралельні обчислення, ймовірнісний аналіз, складність в середньому, нерівності Чернова-Хеффдінга, нерівність Маркова, маршрутизація в гіперкубі, randomized algorithm, parallel computing, probabilistic analysis, average complexity, Chernov-Heffding inequalities, Markov inequality, hypercube routing
Бібліографічний опис
Кубайчук, О. Рандомізовані алгоритми в системах без координації та централізації / Оксана Кубайчук, Денис Сай // Information Technology and Security. – 2024. – Vol. 12, Iss. 1 (22). – Pp. 80-90. – Bibliogr.: 21 ref.