<<
>>

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

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

Чтобы ответить на него, будем считать, что выполнение протокола привело к неудаче после t квантов, если какой-то процесс так и не смог обратиться к базе данных.

Обозначим Tt событие неудачи протокола после t квантов; наша цель — найти разумно малое значение t, для которого значение Рr[j^] мало.

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

Г)

р, = \Jт, Ί·

/=I

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

(13.2) (Граница объединения) Для заданных событий £2, ..., Sn выполняется

л »т

* U⅜ ⅞∑>⅜]·

jч| i-i

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

Для текущей задачи вспомните, что *i=IЛ,лu] , а следовательно,

Рт[⅜∑>⅛].

/--I

Выражение в правой части представляет собой сумму n слагаемых с одина- ковыми значениями; чтобы вероятность Т была достаточно малой, необходимо убедиться в том, что каждое слагаемое в правой части существенно меньше 1 /и.

Из предшествующего обсуждения мы видим, что выбор t = θ(w) недостаточно хорош, поскольку каждое слагаемое в правой части ограничивается только константой. Если выбрать t — \еп *(Ыпо}, то Рг|⅞'l]
<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. § 31 Понятие о безличных обязательствах. – Бумаги безыменные, или на предъявителя. – Облигации, акции и билеты. – Происхождение сих актов. – Выпуск их, изъятие из обращения, передача, свободное обращение, амортизация. – Потерянные бумаги. – Акты сего рода по русскому законодательству.
  2. Десять черт успешного человека
  3. Критерии успешности процедуры
  4. Успешное воспроизведение показаний на месте
  5. Психологические предпосылки успешного предпринимательства.
  6. ЧЕМ УСПЕШНЫЕ ЛЮДИ ОТЛИЧАЮТСЯ ОТ НЕУДАЧНИКОВ
  7. КАК УСПЕШНО АДАПТИРОВАТЬСЯ НА НАУЧНОЙ КОНФЕРЕНЦИИ В США
  8. Очерк 2: Берт «Процесс — вот мое достояние. Именно процесс создает успех»
  9. ТРЕВОГА ОЖИДАНИЯ
  10. ПОЧЕМУ ДЕЙСТВУЮТ ПОЗИТИВНЫЕ ОЖИДАНИЯ
  11. Еще один секрет успешной работы. О культуре рабочего места.
  12. Еще один секрет успешной работы. О культуре рабочего места.
  13. ЗАКОН ОЖИДАНИЯ
  14. 2. Сила позитивных ожиданий
  15. НЕЧУВСТВИТЕЛЬНОСТЬ К ОЖИДАНИЯМ