Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Теперь допустим, что в одном из каналов связи возникли помехи и передать по нему в данный момент ничего нельзя. Мы изобразили эту ситуацию на рис. 4.2. Сразу видно, что наш мини-интернет не распался. Несмотря на то что прямая связь между компьютерами 1 и 2 утеряна, они по-прежнему могут передавать друг другу информацию через компьютер 3. Заметит ли пользователь неполадку в канале? Скорее всего, нет. Поскольку сигнал идет со скоростью света, нет никакой разницы в скорости доставки информации – пойдет ли сигнал напрямую из Москвы в Нижний Новгород или даст кругаля через Сидней или Нью-Йорк.

Рис. 4.2. Мини-интернет из трех компьютеров. Хотя канал связи между компьютерами 1 и 2 недоступен, они по-прежнему могут обмениваться информацией через компьютер 3

Чтобы развалить нашу маленькую сеть, нужно вывести из строя как минимум два, а то и все три канала связи, как показано на рис. 4.3.

Рис. 4.3. Мини-интернет из трех компьютеров. Сверху: вышли из строя два канала связи, компьютер 1 оказался отрезанным от сети. Снизу: вышли из строя все три канала связи, связь между компьютерами полностью прервана

Насколько устойчива наша мини-сеть? Сосчитать это совсем нетрудно. Допустим, помехи в отдельных каналах связи возникают независимо друг от друга с какой-то вероятностью, скажем 40 %. На практике это означает, что в среднем в четырех из десяти случаев канал оказывается недоступным. Сорок процентов – многовато для реального интернета, но для примера подойдет.

Компьютер 1 может оказаться отрезанным от сети, как на рис. 4.3 сверху с вероятностью 0,4 × 0,4 × 0,6 = 0,096(×100 %) = 9,6 %. В аналогичную ситуацию могут попасть компьютеры 2 и 3 с той же долей вероятности. Наконец, надо добавить вероятность самой плохой ситуации, как на рис. 4.3 снизу, которая равна 0,4 × 0,4 × 0,4 = 0,064(×100 %) = 6,4 %. В результате получается, что наша сеть «развалится» с вероятностью 3 × 9,6 % + 6,4 % = 35,2 %.

Конечно, 35,2 % – довольно много, но мы взяли нереально большую вероятность помех. Самое интересное, что вероятность потери связи в сети меньше, чем вероятность потери связи в одном канале: 35,2 % меньше, чем 40 %. Сеть более устойчива, чем отдельно взятый канал!

Даже из нашего мини-примера понятно, откуда берется устойчивость сети. В сети компьютеры могут связаться друг с другом не одним, а несколькими способами, через другие компьютеры. Если один канал недоступен, можно найти альтернативный маршрут. Более того, этот эффект заметно усиливается при меньшей вероятности помех. Для примера мы приводим несколько результатов в табл. 4.1[8].

Таблица 4.1. Вероятности потери связи в мини-сети (правая колонка) при заданной вероятности потери связи в одном канале (левая колонка)

Мы видим, что значения в правой колонке убывают гораздо быстрее, чем в левой. Если вероятность недоступности канала 1 % – величина вполне реальная на практике, – то наша скромная мини-сеть в 33 раза устойчивее, чем отдельный канал связи!

Конечно, наш мини-интернет очень далек от реальности. Что, если у нас не три компьютера, а целая сеть из десятков, сотен, тысяч машин? Скорость света по-прежнему позволит передавать информацию не напрямую, а по длинным цепочкам. Однако подсчет вероятностей значительно затруднится.

И вот тут опять понадобится математика! Задачи об устойчивости больших сетей требуют глубоких концепций и новых моделей на стыке комбинаторики и теории вероятностей. К счастью, необязательно вникать в длинные доказательства, чтобы понять основные идеи. О некоторых таких фундаментальных идеях, проникающих в самую суть устройства сетей и уже ставших классикой, мы расскажем в следующих разделах.

Случайные графы

Математическая теория, которая, в частности, позволяет ответить на вопрос об устойчивости больших сетей, возникла на рубеже 50–60-х годов XX века. Ее авторами стали два замечательных венгерских математика Пол Эрдеш и Альфред Реньи{9}{10}.

Эрдеш – настоящий классик современной комбинаторики, теории чисел, теории вероятностей. Он написал более полутора тысяч статей, решил множество проблем и еще больше поставил задач, которые определили пути развития науки на долгие годы. Реньи – выдающийся венгерский специалист по теории вероятностей. Его именем назван математический институт в Будапеште, подобно тому как математический институт в Москве носит имя Владимира Андреевича Стеклова.