Оцінювання складності алгоритмів виходячи тільки з можливості найгіршого варіанту вхідних даних є часто не виправданим. Розробка алгоритмів, які б очікувано швидко працювали на всіх можливих входах має практичне значення. Якщо для задачі існує розумна можливість змоделювати розподіли вхідних величин, то можна скористатися ймовірнісним аналізом як методом розробки ефективних алгоритмів. Коли ж інформації про розподіли вхідних величин недостатньо для їх чисельного моделювання, розробляють алгоритми шляхом надання випадкового характеру частині самого алгоритму – рандомізовані алгоритми. Застосування рандомізації забезпечує функціонування алгоритму при мінімальних потребах у зберіганні внутрішніх станів та подій у минулому, причому самі алгоритми виглядають компактно. В роботі вивчаються задачі, для яких існують відносно ефективні детерміновані алгоритми розв’язання. Але, як буде показано, побудова відповідних рандомізованих алгоритмів призводить до ефектних та ефективних схем паралельних обчислень з лінійною складністю в середньому. Переваги рандомізації особливо проявляються у випадку великих комп’ютерних систем та комунікаційних мереж, які функціонують без координації та централізації. Прикладами таких розподілених систем є, зокрема, мережі популярних нині криптовалют. Застосування рандомізованих евристик дозволяє системі адаптуватися до змінних умов експлуатації та мінімізує ймовірність конфліктів між процесами. В роботі показано переваги застосування рандомізованого алгоритму перед детермінованими алгоритмами для задачі маршрутизації в мережі з топологією гіперкуба. Доведено теорему про оцінку очікуваного числа кроків, необхідних рандомізованому алгоритму Валіанта для доставки всіх повідомлень за адресою. Очікувана лінійна складність алгоритму Валіанта є прямим наслідком доведеної теореми.