Первое применение: разрешение конфликтов - Рандомизированные алгоритмы

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

Темы рандомизация и вероятностного анализа проникают во многие области компьютерной науки, включая разработку алгоритмов, и когда речь заходит о случайных процессах в контексте вычислений, обычно имеется в виду одна из двух точек зрения. Первая рассматривает случайное поведение реального мира: здесь часто изучаются традиционные алгоритмы, сталкивающиеся со случайно сгенерированными входными данными. Такие методы часто называются анализом среднего случая, потому что поведение алгоритма изучается на “средних” входных данных (подвергнутых воздействию некоторого случайного процесса) вместо худшего случая.

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

Чем может быть полезен алгоритм, принимающий случайные решения? Во-первых, рандомизация расширяет возможности используемой модели. Эффективные детерминированные алгоритмы, которые всегда дают правильный ответ, могут рассматриваться как особый случай эффективных рандомизированных алгоритмов, которые дают правильный ответ с очень высокой вероятностью; они также являются особым случаем рандомизированных алгоритмов, которые всегда работают правильно и при этом, как ожидается, выполняются эффективно. Даже при получении худших входных данных алгоритм, выполняющий свою “внутреннюю” рандомизацию, может компенсировать некоторые нежелательные аспекты худшего случая. Следовательно, задачи, которые не решаются эффективными детерминированными алгоритмами, могут не устоять перед рандомизированными алгоритмами.

Но это еще не все. Мы рассмотрим рандомизированные алгоритмы для некоторых задач, для которых существуют сравнительно эффективные детерминированные алгоритмы. Даже в таких ситуациях рандомизация часто проявляет немалую мощь: например, она может быть концептуально проще или она может обеспечить функционирование алгоритма при минимальных потребностях в хранении внутреннего состояния или информации о прошлых событиях. Преимущества рандомизации расширяются при рассмотрении крупных компьютерных систем и сетей с множеством гибких взаимодействий между процессами, другими словами, в распределенных системах. Здесь случайное поведение части отдельных процессов может сократить объем необходимого обмена информации или синхронизации; рандомизация часто оказывается ценным инструментом для нарушения симметрии между процессами, снижающим вероятность конфликтов и появления “горячих точек”. Многие из примеров будут взяты из ситуаций такого рода: управление доступом к общему ресурсу, распределение нагрузки по нескольким процессорам, маршрутизация пакетов в сети и т. д. Даже небольшой опыт работы с рандомизированными эвристиками может сильно пригодиться при анализе больших систем.

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

13.1. Первое применение: разрешение конфликтов

Начнем с первого применения рандомизированных алгоритмов — разрешения конфликтов в распределенных системах. Этот пример демонстрирует общий стиль анализа, который будет использоваться во многих дальнейших алгоритмах. В частности, он дает возможность попрактиковаться в основных операциях, относящихся к событиям и их вероятностям, анализу пересечений событий с использованием независимости и объединений событий. Для полноты мы приведем краткую сводку основных концепций в завершающем разделе этой главы (раздел 13.15).

Задача

Допустим, имеется n процессов P₁, P₂, ..., P_n, конкурирующих за доступ к одной базе данных. Будем считать, что время делится на кванты. В одном кванте времени с базой данных может работать не более чем один процесс; если два и более процесса пытаются одновременно обратиться к базе данных, эти процессы “блокируются” до конца кванта. Следовательно, хотя каждый процесс хочет, как можно чаще обращаться к базе данных, пытаться обращаться к базе данных всем процессам в каждом кванте бессмысленно; в этом случае все процессы будут постоянно находиться в заблокированном состоянии. Нужен справедливый механизм распределения квантов между процессами, чтобы все процессы имели возможность регулярно работать с базой данных.

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

Разработка рандомизированного алгоритма

Рандомизация предоставляет естественный протокол для этой задачи, который определяется очень просто. Для некоторого числа p > 0, которое будет определено ниже, каждый процесс пытается обратиться к базе данных в каждом кванте с вероятностью p независимо от решений других процессов. Итак, если в каком-либо кванте ровно один процесс выдает такое обращение, его попытка завершается успешно; если обращения поступают от двух и более процессов, они блокируются; и если ни одной попытки не было, то квант “пропадает”. Такая стратегия, рандомизирующая поведение каждого процесса из множества одинаковых процессов, лежит в основе уже упоминавшейся парадигмы нарушения симметрии: если все процессы действуют синхронно, многократно пытаясь обратиться к базе данных в одно и то же время, никакого прогресса не будет; рандомизация же позволяет “сгладить” конкурентную борьбу.

Анализ алгоритма

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

Определение основных событий

Анализ вероятностных систем такого рода полезно начать с определения основных событий и их вероятностей. Первое событие: для заданного процесса P_i и заданного кванта времени tсобытие A[i, t] обозначает попытку обращения P_i к базе данных в кванте t. Известно, что каждый процесс пытается обратиться к базе данных с вероятностью р, так что вероятность этого события для любых i и t равна Для каждого события также существует дополняющее событие, которое означает, что основное событие не произошло; в данном случае дополняющее событие означает, что процесс P_i не пытался обратиться к базе данных в кванте t, а его вероятность равна

Главный вопрос — удастся ли процессу обратиться к базе данных в заданном кванте. Обозначим это событие S[i, t]. Очевидно, процесс P_i должен хотя бы попытаться обратиться к базе данных в кванте t. Успешное обращение означает, что процесс P_i попытался обратиться к базе данных в кванте t, а все остальные процессы не пытались обращаться к базе данных в кванте t. Следовательно, S[i, t] равно пересечению события A[i, t] с дополняющими событиями для j ≠ i:

Все события в этом пересечении независимы по определению протокола разрешения конфликтов. Следовательно, вероятность S[i, t] вычисляется умножением вероятностей всех событий в пересечении:

Мы получили удобное выражение в замкнутой форме для вероятности того, что P_i успешно обратится к базе данных в кванте t; теперь уместно задаться вопросом, как выбрать р для максимизации вероятности успеха. Сначала заметим, что вероятность успеха равна 0 для крайних случаев р = 0 и р = 1 (в которых либо процессы вообще не пытаются обратиться к базе данных, либо каждый процесс пытается обратиться к базе данных в каждом кванте, так что в итоге все процессы блокируются). Функция f(p) = р(1 - р)^n-1 положительна для значений р из диапазона от 0 до 1, а ее производная равна нулю только в точке р = 1/n, где и достигается максимум. Таким образом, вероятность успеха максимизируется при выборе р = 1/n. (Стоит заметить, что 1/n — естественный и интуитивный вариант в том случае, если в каждом кванте попытка обращения должна исходить ровно от одного процесса.)

Выбирая р = 1/n, получаем Полезно примерно представить асимптотическое поведение этого выражения с помощью следующего факта из курса математического анализа.

(13.1) (а) Функция монотонно сходится от 1/4 к 1/e при увеличении n, начиная с 2.

(b) Функция монотонно сходится от 1/2 к 1/e при увеличении начиная с 2.

Из (13.1) следует, что а следовательно, значение Рr[S[i, t]] асимптотически равно Ө(1/n).

Ожидание успешного обращения со стороны конкретного процесса

Рассмотрим этот протокол с оптимальным значением вероятности обращения p = 1/n. Допустим, нас интересует, сколько времени должно пройти, чтобы процесс P_i успешно обратился к базе данных хотя бы один раз. Из предыдущих вычислений видно, что вероятность успеха в любом отдельном кванте не очень хороша при достаточно больших n. Но как насчет серии из нескольких квантов?

Обозначим F[i, t] “событие неудачи”, при котором процесс P_i не добивается успеха во всех квантах с 1 до t. Очевидно, оно представляет собой обычное пересечение дополняющих событий для r = 1, 2, ..., t. Кроме того, поскольку все эти события независимы, вероятность F[i, t] вычисляется умножением:

Эти вычисления дают значение искомой вероятности, но если и дальше так продолжать, придется иметь дело с чрезвычайно сложными выражениями, поэтому важно переходить на асимптотическое мышление. Вспомните, что вероятность успеха после одного кванта равна Ө(1/n), а точнее, она лежит в границах от 1/(еn) до 1/(2n). Используя приведенное выше выражение, имеем

Теперь заметим, что если задать t = en, то мы получим выражение, которое можно напрямую подставить в (13.1). Конечно, еn не будет целым числом, поэтому мы возьмем t = [en] и получим:

Это чрезвычайно компактное и полезное асимптотическое утверждение: вероятность того, что процесс Р_i не добьется успеха ни в одном из квантов с 1 по [еn], ограничивается сверху константой e^-1 независимо от n. Теперь при увеличении t с очень малым коэффициентом вероятность того, что Р_i не добьется успеха ни в одном из квантов с 1 по t, резко падает: если задать t= [еn] ∙ (с ln n), то получаем

Итак, асимптотически ситуацию можно рассматривать следующим образом: после Ө(n) квантов вероятность того, что процесс Р_i еще не смог обратиться к базе данных, ограничивается константой; а с этого момента до Ө(n ln n) эта вероятность падает до очень малой величины, ограничиваемой обратной полиномиальной зависимостью от n.

Ожидание успешного обращения всех процессов

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

Чтобы ответить на него, будем считать, что выполнение протокола привело к неудаче после t квантов, если какой-то процесс так и не смог обратиться к базе данных. Обозначим F_t событие неудачи протокола после t квантов; наша цель — найти разумно малое значение t, для которого значение Pr[F_t] мало.

Событие F_t происходит в том, и только в том случае, если происходит одно из событий F[i, t]; мы можем записать

Ранее мы рассматривали пересечения независимых событий, с которыми было очень просто работать; на этот раз речь идет об объединении событий, которые независимыми не являются. Точное вычисление вероятностей подобных объединений может быть очень сложным, и во многих случаях достаточно воспользоваться простой границей объединения, которая гласит, что вероятность объединения событий ограничивается сверху суммой их вероятностей:

(13.2) (Граница объединения) Для заданных событий E₁, E₂, ..., E_n выполняется

Обратите внимание: речь не идет о равенстве; однако верхняя граница достаточно хороша в подобных ситуациях, когда объединение в левой части представляет “плохое событие”, которого мы пытаемся избежать, и мы хотим ограничить его вероятность в контексте составляющих “плохих событий” в правой части.

Для текущей задачи вспомните, что а следовательно,

Выражение в правой части представляет собой сумму n слагаемых с одинаковыми значениями; чтобы вероятность F_t была достаточно малой, необходимо убедиться в том, что каждое слагаемое в правой части существенно меньше 1/n. Из предшествующего обсуждения мы видим, что выбор t = Ө(n) недостаточно хорош, поскольку каждое слагаемое в правой части ограничивается только константой. Если выбрать t = [еn] ∙ (c ln c), то Рr[F[i, t]] ≤ n^-c для всех i — именно то, что нужно.

А конкретно, выбор t = 2[en]ln n дает нам

Таким образом, нам удалось показать следующее:

(13.3) С вероятностью не менее 1 - n^-1 всем процессам удастся успешно обратиться к базе данных по крайней мере один раз за t = 2[en]ln n квантов.

Интересно заметить, что если бы мы выбрали значение t, равное qn ln n для очень малого значения q (вместо фактически использованного коэффициента 2e), тогда для Рr[F[i, t]] была бы получена верхняя граница, большая n^-1, а следовательно, соответствующая верхняя граница для общей вероятности неудачи Рr[F_i] была бы больше 1, — очевидно, такая верхняя граница полностью бесполезна. Однако, как мы видели, выбирая все большие и большие значения для коэффициента q, можно снизить верхнюю границу Рr[F_i] до n^-c для любой нужной константы с — это очень малая верхняя граница. Итак, в некотором смысле все “действие” в границе объединения быстро происходит в период, когда t = Ө(n ln n), с изменением скрытой константы внутри Ө(∙) граница объединения переходит от нулевой полезной информации до предоставления в высшей степени сильной границы вероятности.

Может, это просто артефакт применения границы объединения к нашей верхней границе, или данное свойство присуще наблюдаемому процессу? Мы не будем приводить (довольно громоздкие) вычисления, но при желании можно показать, что для t, равного малой константе, умноженной на n ln n, существует заметная вероятность того, что какому-то процессу так и не удалось обратиться к базе данных. Следовательно, быстрое падение значения Рr[F_i] действительно происходит в диапазоне t = Ө(n ln n). Для этой задачи, как и для многих задач такого типа, мы в действительности находим асимптотически “правильное” значение t, несмотря на использование слабой на первый взгляд границы объединения.