Модель
Предположим, что имеется распределенная система с n серверами (потоки управления (thread) считаются отдельными серверами), в которых реализуются разные уровни согласованности, описанные в разд. 3. Серверы кэшируют данные с использованием интервала кэширования (т.е. временем жизни) CI. В течение этого интервала данные категории C читаются из кэша без синхронизации. Кроме того, любые два обновления одного и того же элемента данных на разных серверах считаются конфликтом (при выполнении операций мы не используем семантическую информацию). Если мы дополнительно предположим, что все серверы ведут себя схожим образом (т.е. обновления равномерно распределены по серверам и не зависят одно от другого), то вероятность конфликтного обновления некоторой записи вычисляется по следующей формуле:
Здесь X – это случайная переменная, соответствующая числу обновлений одной и той же записи в течение интервала кэширования CI. P(X > 1) – это вероятность того, что в течение интервала кэширования CI произойдет более одного обновления одной и той же записи. Однако конфликт может возникнуть только в том случае, когда эти обновления производятся на разных серверах. Поэтому в части (ii) правой части соотношения вычисляется вероятность того, что обновления будут произведены в одном и том же сервере, и полученное значение вычитается из вероятности того, чтобы было произведено более чем одно обновление. В соотношении не учитывается вероятность возникновения двойного конфликта для одной и той же записи. Это связано с тем, что мы предполагаем наличие возможности распознавать и устранять конфликты (например, просто путем отбрасывания конфликтующих обновлений), а также считаем пренебрежимо малой вероятность возникновения двух конфликтов для одной и той же записи за время, которое требуется для обнаружения конфликта (например, время интервала кэширования).
Как и в , мы предполагаем, что поступление транзакций в систему является пуассоновским процессом, и это позволяет нам переписать соотношение (1) с использованием средней скорости потока (mean arrival rate) λ.
Для пуассоновского распределения функция плотности вероятности (probability density function, PDF) задается соотношением
Поэтому соотношение (1) можно переписать следующим образом:
Если n > 1, и вероятность возникновения конфликта считается достаточно малой (например, не больше 1%), то вторым элементом (iv) правой части этого соотношения можно пренебречь (моделирование показывает, что при k > 3 составляющие этого элемента принебрежимо малы). Следовательно, в качестве верхней границы вероятности конфликта можно использовать значение следующего выражения:
Если требуется большая точность, можно учесть первые одно или два слагаемых из (iv).
