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

В главе 7 мы вернемся к графам, когда будем обсуждать социальную сеть. В этом случае узлы – это люди, а линии между ними – «дружба» в социальной сети. Мы изобразили пример графа из главы 7 на рис. 4.4 справа.

Естественно, узлов у графа может быть и тысяча, и миллион, и миллиард…

Теория графов – это классическая область математики с огромным количеством приложений. В виде графа можно представить систему железных дорог, газопровод, последовательность операций на крупном производстве или слов в русской речи и многое другое.

У случайных графов есть еще одна особенность. Нам неизвестно заранее, какие узлы связаны линией, а какие – нет. Линии между узлами могут существовать или нет с определенной вероятностью. Именно эту ситуацию мы обсуждали в примере с мини-сетью. При наличии помех канал связи становится недоступным, линия между узлами исчезает.

Случайный граф – естественная модель во многих ситуациях. Например, дружба в социальных сетях возникает непредсказуемым образом. В телекоммуникациях или электрических сетях на линиях связи могут случаться сбои. Если попытаться смоделировать нейронную сеть мозга, то взаимодействия нейронов можно выявить только с определенной вероятностью.

В последнее время в связи с развитием интернета и социальных сетей и небывалой доступностью данных во всех областях – от энергоснабжения до биологии – интерес к теории случайных графов особенно вырос. Новые, очень сложные результаты появляются почти каждый день.

Что же говорит теория случайных графов об устойчивости сети?

Результат Эрдеша – Реньи

В связи с устойчивостью интернета нас интересует вопрос о связности случайного графа. Граф называется связным, если между двумя любыми его вершинами можно пройти по цепочке ребер, то есть все узлы связаны друг с другом. Оба графа на рис. 4.4 – связные. На рис. 4.5 мы сделали их несвязными, удалив по два ребра.

Рис. 4.5. Слева: мини-сеть в виде графа; каналы 1–2 и 1–3 недоступны; граф несвязный, из вершины 1 нельзя попасть в вершины 2 и 3. Справа: социальная сеть в виде графа; пользователь 1 не знаком с пользователями 5 и 6; граф несвязный; нет цепочки знакомых между пользователями 5, 6 и остальными

Эрдеш и Реньи задались вопросом: при какой вероятности помех сеть заданного размера остается связной? Результат получился поразительным! Оказывается, в больших сетях связность сохраняется даже при повышенной вероятности помех.

Например, возьмем сеть из 100 связанных между собой компьютеров. Получается, что каждый отдельный канал может быть недоступен с вероятностью аж 86 %, тем не менее сеть останется связной с вероятностью как минимум… 99 %! Эта ситуация изображена на рис. 4.6: 86 % из всех возможных линий отсутствует, однако сразу видно, что из любого узла можно добраться до любого другого.

Рис. 4.6. Сеть из 100 компьютеров в виде графа. Вероятность недоступности канала 86 %

А сеть из 1000 узлов – это и вовсе нечто фантастическое. Канал связи может быть недоступен с вероятностью 98 %, а связность сохраняется с вероятностью 99,9 %! Чем больше сеть, тем сильнее результат.

В табл. 4.2 мы приводим результаты для сетей разных размеров. Легко заметить, что число в самой правой колонке не что иное, как

Таблица 4.2. Результат Эрдеша – Реньи

Ниже во врезке приведена более общая математическая формулировка результата. Этот текст рассчитан на уровень средней школы, но если вы не хотите вдаваться в подробности, можете его пропустить.

Простейший вариант теоремы Эрдеша – Реньи

Символ ln(n) означает натуральный логарифм числа n. В данном случае нам важно только то, что если n увеличивается, то ln(n) тоже увеличивается, но очень медленно.

Теорема Эрдеша – Реньи. Допустим, сеть состоит из n узлов. Предположим, что связь между любыми двумя узлами недоступна с вероятностью q(n) независимо от других связей в сети. Если

то связность сети сохраняется с вероятностью не меньше, чем

В табл. 4.2 во втором и третьем столбце все значения умножены на 100 %. Во втором столбце указаны значения, полученные с помощью формулы (4.1). Поскольку ln(n) растет гораздо медленнее, чем n, то допустимая вероятность помех увеличивается. В третьем столбце – значения (4.2), то есть

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

Надежность сети, по сути, и есть та вероятность уничтожения отдельной связи в ней, начиная с которой общая связность маловероятна. Для описанной выше ситуации надежность исключительно высока, и это строго доказанный результат.

Фазовый переход

На самом деле теорема Эрдеша – Реньи несколько точнее и еще удивительнее, чем мы описали в предыдущем разделе. Эта теорема выявила интересное явление, которое физики называют фазовым переходом. Фазовый переход – это резкий скачок от одного состояния системы к совершенно другому[10].

Самый знаменитый фазовый переход – изменение состояния воды в зависимости от температуры. При 0° Цельсия вода превращается в лед, а при 100° – в пар. 0° и 100° – критические значения, при которых состояние резко меняется.

Нечто похожее происходит и с вероятностью связности сети, если изменять вероятность недоступности каналов. Оказывается, надежность сети меняется не постепенно, а очень резко. Если вероятность помехи меньше критического значения, то с подавляющей вероятностью связность сохраняется. Но стоит хотя бы немного пересечь критическую черту – и сеть почти наверняка распадется.

На рис. 4.7 показан пример сети из 100 компьютеров. Согласно результатам Эрдеша – Реньи, критическая вероятность помех в такой сети равна 95,4 %. Слева вероятность помехи 95 %, то есть меньше критического значения. Как видите, связность сети сохранилась. Мы неоднократно повторили эксперимент, но получить несвязную сеть нам так и не удалось. На рисунке справа вероятность помехи 96 %. И что же? Одна точка оторвалась от сети, связность потеряна. Опять же как мы ни старались повторить эксперимент, связной сети мы не получили ни разу. Результат впечатляет тем, насколько тонкой оказывается грань между связностью и несвязностью!

Рис. 4.7. Сеть из 100 компьютеров в виде графа. Слева: вероятность недоступности канала 95 %; связность сохраняется. Справа: вероятность недоступности канала 96 %; связность нарушена

Если вероятность помех в точности равна критической, то произойдет примерно то же самое, что и с водой и снегом при нуле градусов: может получиться и так и эдак. В нашем случае вероятность сохранения связности приблизительно составит 36,79 %.

Критическая вероятность недоступности канала для сети размера п вычисляется по формуле

Для примера мы приводим несколько значений в табл. 4.3.

Таблица 4.3. Результат Эрдеша – Реньи: критическая вероятность помех. Если вероятность помех меньше критической, связность сети сохраняется, а если больше – разрушается

Подобные фазовые переходы типичны для теории случайных графов. Эти результаты самые интересные, потому что многое говорят о природе сетей на практике. Состояние сети – это, как правило, две крайности. Социальная сеть либо становится популярной, либо умирает. Компьютерный вирус распространяется с огромной скоростью и размахом или сходит на нет в самом начале. И реальность, и математика подтверждают: среднего не дано. К сожалению, нам далеко не всегда известны критические значения и главное мы не знаем каким образом удержаться по правильную сторону от фазового перехода.

Как доказывается результат Эрдеша – Реньи

Глубокие математические доказательства часто строятся на очень простых интуитивных идеях. Результат Эрдеша – Реньи – блестящий пример данной закономерности[11].

Математики заметили, что наиболее вероятный способ разрушить связность сети – отрезать один узел от всех каналов связи. Группу узлов отрезать гораздо труднее, потому что число каналов, которые связывают ее и остальную часть сети, относительно большое. Маловероятно, что все эти каналы недоступны. Тогда изначально сложный вопрос:

С какой вероятностью разрушится связность сети?

сводится к гораздо более простому вопросу:

С какой вероятностью хотя бы один из узлов потеряет все свои каналы связи?

Чтобы доказать, что эти вероятности приблизительно равны, понадобятся длинные и нетривиальные математические выкладки. Но доказать это можно, и усилия оправдываются, потому что второй вопрос гораздо проще первого.

Например, если у нас 100 узлов и вероятность помехи 0,96, то каждый узел может оказаться оторванным от всех 99 других узлов с вероятностью

(0,96)99 (×100 %)

Это очень специфическое выражение: число, близкое к единице, возведенное в большую степень. Такие выражения хорошо известны в математике и относятся к так называемым замечательным пределам, из которых, по сути дела, и следует результат.

Что мы знаем и чего не знаем о надежности интернета

Результаты Эрдеша – Реньи полностью не решают проблемы устойчивости интернета. Их модель не очень похожа на реальный интернет. Например, в модели Эрдеша – Реньи число линий у разных узлов обычно близко к среднему. В интернете же разброс между серверами очень большой. У одних серверов сотни каналов связи, а у других – всего два-три.

В 2000 году журнал Nature опубликовал статью «Устойчивость к помехам и атакам в больших сетях»{11}. Авторы-физики, в том числе и весьма влиятельный и знаменитый ученый Ласло Барабаши, взяли данные небольшой части интернета и с помощью компьютерных экспериментов решили посмотреть, что произойдет, если по одному выводить из строя серверы.

Результаты получились нетривиальные. Если серверы выходят из строя случайным образом, например из-за помех, то связность сети долго сохраняется. Но если целенаправленно вывести из строя несколько серверов с самым большим количеством каналов связи, то сеть быстро распадется. Вывод звучал сенсационно: интернет надежный и в то же время довольно хрупкий. Он устойчив к помехам, но чувствителен к атакам!

Эта работа быстро приобрела широкую известность. Только инженеры, работающие в этой сфере, с недоумением пожимали плечами: «Не может быть, наши сети очень надежные!» Результаты Барабаши и соавторов вызвали волну критики, особенно резкая критика прозвучала в вышедшей в 2005 году статье специалистов по телекоммуникациям{12}.

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

Благодаря широкому взгляду физиков и специализированному анализу информатиков и инженеров мы знаем достаточно много об устойчивости интернета. Но вопрос пока не закрыт.

В идеале нам нужна строгая математическая модель, включающая в себя основные свойства интернета. И для этой модели необходимы результаты типа Эрдеша – Реньи, показывающие, что произойдет, если вывести из строя те или иные серверы или каналы связи. Только тогда у нас будут однозначно правильные, строго доказанные результаты. Продвижение в этих направлениях есть, но до точных ответов пока далеко. Работа продолжается.

Интернет в картинках

Если вы хотите посмотреть, как выглядит интернет, зайдите на сайт проекта Opte по адресу http://www.opte.org/.

Создатель проекта, программист и художник Баррет Лайон, задался целью, казалось бы, невыполнимой – нарисовать интернет! Причем именно в виде графа: серверы и каналы связи между ними.

Серверы принадлежат разным странам и компаниям. Собрать информацию обо всех каналах связи – колоссальная техническая задача. И это только начало. Не менее сложно изобразить все эти гигантские данные на одном понятном глазу рисунке.

Красочное изображение на черном фоне напоминает фейерверк. Линии разных цветов обозначают разные континенты, а плотные, белые, почти светящиеся магистрали между ними – опорная сеть. Рисунки Opte известны по всему миру. Они получили множество наград и выставляются в Музее современного искусства в Нью-Йорке. Смотрите, это интернет!

Приложения для подготовленного читателя к главе 4

Глава 5

Сила выбора из двух

Очереди, которых мы не видим

Всем нам хорошо знакомы самые разные очереди. Очередь в кассу супермаркета, очередь в приемной врача, очередь у лифта в большом здании, толкотня перед входом в метро и непереносимые очереди из машин – автомобильные пробки. Но кроме всех этих «живых» очередей, мы, сами того не замечая, стоим в огромном количестве «компьютерных» очередей. Например, это происходит практически каждый раз, когда мы подключаемся к интернету.

Допустим, вы хотите посмотреть какую-то веб-страницу, скажем главную страницу Московского физико-технического института (МФТИ), где работает Андрей. Вы вводите веб-адрес https://mipt.ru в своем браузере (например, Internet Explorer, Fire Fox или Google Chrome). Что же дальше?

Веб-страница – всего лишь файл, похожий на обычный вордовский документ, только в несколько ином формате. Этот файл включает в себя все, что есть на странице: тексты, рисунки, ссылки и тому подобное. Ваш браузер – это фактически интерфейс, который позволяет вам запросить файл с содержанием нужной страницы.

Отправка цифровой информации сравнима с отправкой обычной почты или грузов. Запрос с вашего браузера поступает на так называемый веб-сервер под именем mipt.ru, веб-сервер МФТИ. Веб-сервер – это специально выделенный компьютер, который отвечает за поиск нужного файла и его отправку в браузер пользователя. У каждого сайта, или домена – mipt.ru, rzd.ru, google.com и других, – свой веб-сервер, и часто не один.

Получив ваш запрос, веб-сервер МФТИ отправляет в ваш браузер файл с содержанием главной страницы. Дальше вы начинаете ее читать, кликаете на ссылки, загружаете документы. И каждый раз веб-сервер МФТИ отправляет вам новые странички, фотографии, тексты и все остальное. Кроме вас на сайт заходят другие пользователи, с другими запросами. У веб-сервера работы хватает! И когда ее слишком много, ваши запросы должны дожидаться своей очереди.

И это еще не все. Как и почтовая пересылка, информация попадает с одного компьютера на другой не напрямую, а через несколько промежуточных узлов. Каждый узел – это тоже серверы, и там тоже могут образоваться очереди на доставку и отправку. Это происходит при отправке любой цифровой информации, будь то имейл, фотографии на «Фейсбуке» или ваш голос по скайпу.

Насколько длинной будет очередь? Можно ли организовать сервис, например отправку веб-страниц или передачу голоса и видео, так, чтобы задержки были как можно меньше? Этими вопросами занимается специальная область математики под названием теория очередей, или теория массового обслуживания. Среди ее основателей крупные российские математики – Александр Яковлевич Хинчин и Борис Владимирович Гнеденко.

Теория очередей возникла из практики в начале XX века, когда датский математик Агнер Эрланг решил проанализировать работу телефонной станции. С появлением современных телекоммуникаций эта теория получила новое необъятное поле приложений и мощный толчок к развитию. В этой главе мы расскажем только об одной задаче, так называемой балансировке нагрузки, и об одном ее относительно недавнем и необыкновенно элегантном решении.

Параллельные серверы

Как вы уже поняли, запросов на веб-сервер поступает множество. Поэтому часто используется не один, а сразу несколько серверов, которые могут обрабатывать запросы одновременно. Серверов может быть очень много. Например, современные поисковые системы, такие как «Яндекс» и Google, получают миллиарды запросов в день. Поэтому они оснащены огромным количеством мощных серверов, занимающих внушительные территории.

Когда вы посылаете запрос, вас совершенно не волнует, какой из параллельных серверов будет его обрабатывать. Это внутренняя кухня веб-серверов. Но для того, чтобы наши запросы выполнялись быстро и эффективно, вопрос налаженной параллельной работы очень актуален.

Схематически мы изобразили параллельные серверы на рис. 5.1. Запросы на рисунке разной величины, потому что все они разного объема. Кому-то нужна страница с коротеньким текстом, а кому-то – годовой отчет на 100 страниц с графиками и фотографиями. Если информации больше, то и времени на ее отправку понадобится больше.

Рис. 5.1. Несколько параллельных серверов. В реальности серверов намного больше. Запросы разной величины содержат разное количество информации, и, соответственно, для их отправки требуется разное время